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)); } }