COSC6490A

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<Node> top;
 
  /**
   * Creates an empty stack.
   */
  public Stack3()
  {
    this.top = new AtomicReference<Node>();
  }
 
  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<Stack4, Node> 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));
  }
}