Below we implement the following Stack interface in several different ways.
/**
* A Stack.
*/
public interface Stack
{
/**
* Removes the top element from this stack and returns it.
*
* @return the top element of this stack.
* @throw EmptyException if this stack is empty.
*/
public Integer pop() throws EmptyException;
/**
* Pushes the given element onto this stack.
*
* @param the element to be pushed onto this stack.
*/
public void push(Integer element);
}
In each implementation of the above interface we will exploit the class Node.
/**
* A node of a linked list. Each node contains an integer.
*/
public class Node
{
private Integer element;
private Node next;
/**
* Creates a new node with the given element and next node.
*
* @param element the element stored in the node.
* @pre. element != null
* @param next the next node in the list.
*/
public Node(Integer element, Node next)
{
this.element = element;
this.next = next;
}
/**
* Returns the element of this node.
*
* @return the element of this node.
*/
public Integer getElement()
{
return this.element;
}
/**
* Returns the next node.
*
* @return the next node.
*/
public Node getNext()
{
return this.next;
}
/**
* Sets the next node to the given node.
*
* @param node the new next node.
*/
public void setNext(Node next)
{
this.next = next;
}
}
In the first implementation, we simply lock the whole stack when we pop or push an element.
public class Stack1 implements Stack
{
private Node top;
/**
* Creates an empty stack.
*/
public Stack1()
{
this.top = null;
}
public synchronized Integer pop() throws EmptyException
{
if (this.top == null)
{
throw new EmptyException();
}
else
{
Integer element = this.top.getElement();
this.top = this.top.getNext();
return element;
}
}
public synchronized void push(Integer element)
{
this.top = new Node(element, this.top);
}
}
In the second implementation, we lock the top node when we pop or push an element.
public class Stack2 implements Stack
{
private Node top;
/**
* Creates an empty stack.
*/
public Stack2()
{
this.top = new Node(null, null);
}
public Integer pop() throws EmptyException
{
synchronized (this.top)
{
if (this.top.getNext() == null)
{
throw new EmptyException();
}
else
{
Integer element = this.top.getElement();
this.top = this.top.getNext();
return element;
}
}
}
public void push(Integer element)
{
Node node = new Node(element, null);
synchronized (this.top)
{
node.setNext(this.top);
this.top = node;
}
}
}
The third implementation does not use any locking. We exploit the class AtomicReference.
import java.util.concurrent.atomic.*;
public class Stack3 implements Stack
{
private volatile AtomicReference top;
/**
* Creates an empty stack.
*/
public Stack3()
{
this.top = new AtomicReference();
}
public Integer pop() throws EmptyException
{
Node node;
do
{
node = this.top.get();
if (node == null)
{
throw new EmptyException();
}
}
while (!this.top.compareAndSet(node, node.getNext()));
return node.getElement();
}
public void push(Integer element)
{
Node node = new Node(element, null);
do
{
node.setNext(this.top.get());
}
while (!this.top.compareAndSet(node.getNext(), node));
}
}
Also the fourth implementation does not use any locking. This time we exploit the class AtomicReferenceFieldUpdater.
import java.util.concurrent.atomic.*;
public class Stack4 implements Stack
{
private volatile Node top;
private static final AtomicReferenceFieldUpdater topUpdater = AtomicReferenceFieldUpdater.newUpdater(Stack\
4.class, Node.class, "top");
/**
* Creates an empty stack.
*/
public Stack4()
{
this.top = null;
}
public Integer pop() throws EmptyException
{
Node node;
do
{
node = this.top;
if (node == null)
{
throw new EmptyException();
}
} while (!Stack4.topUpdater.compareAndSet(this, node, node.getNext()));
return node.getElement();
}
public void push(Integer element)
{
Node node = new Node(element, null);
do
{
node.setNext(this.top);
}
while (!Stack4.topUpdater.compareAndSet(this, node.getNext(), node));
}
}