COSC6490A

/**
 * A Stack.
 */
public interface Stack<T>
{
  /**
   * Removes the top element from this stack and returns it.
   *
   * @return the top element of this stack.
   * @throw Exception if this stack is empty.
   */
  public T pop() throws Exception;
 
  /**
   * Pushes the given element onto this stack.
   *
   * @param the element to be pushed onto this stack.
   */
  public void push(T element);
}

In each implementation of the above interface we will exploit the class Node.

/**
 * A node of a linked list.
 */
public class Node<T>
{
  private T element;
  private Node<T> next;
 
  /**
   * Initializes this 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(T element, Node<T> next)
  {
    this.element = element;
    this.next = next;
  }
 
  /**
   * Returns the element of this node.
   *
   * @return the element of this node.
   */
  public T getElement()
  {
    return this.element;
  }
 
  /**
   * Returns the next node.
   *
   * @return the next node.
   */
  public Node<T> getNext()
  {
    return this.next;
  }
 
  /**
   * Sets the next node to the given node.
   *
   * @param node the new next node.
   */
  public void setNext(Node<T> next)
  {
    this.next = next;
  }
}

In the first implementation, we simply lock the whole stack when we pop or push an element.

public class First<T> implements Stack<T>
{
  private Node<T> top;
 
  public First()
  {
    this.top = null;
  }
 
  public synchronized T pop() throws Exception
  {
    if (this.top == null)
    {
      throw new Exception();
    }
    else
    {
      T element = this.top.getElement();
      this.top = this.top.getNext();
      return element;
    }
  }
 
  public synchronized void push(T element)
  {
    this.top = new Node<T>(element, this.top);
  }
}

In the second implementation, we lock the top node when we pop or push an element.

public class Second<T> implements Stack<T>
{
  private Node<T> top;
 
  public Second()
  {
    this.top = null;
  }
 
  public T pop() throws Exception
  {
    Node<T> node;
    synchronized (this.top)
    {
      if (this.top == null)
      {
        throw new Exception();
      }
      else
      {
        node = this.top;
        this.top = this.top.getNext();
      }
    }
    return node.getElement();
  }
 
  public void push(T element)
  {
    Node<T> node = new Node<T>(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 Third<T> implements Stack<T>
{
  private volatile AtomicReference<Node<T>> top;
 
  public Third()
  {
    this.top = new AtomicReference<Node<T>>();
  }
 
  public T pop() throws Exception
  {
    Node<T> node;
    do
    {
      node = this.top.get();
      if (node == null)
      {
        throw new Exception();
      }
    }
    while (!this.top.compareAndSet(node, node.getNext()));
    return node.getElement();
  }
 
  public void push(T element)
  {
    Node<T> node = new Node<T>(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 Fourth<T> implements Stack<T>
{
  private volatile Node<T> top;
 
  private static final AtomicReferenceFieldUpdater<Fourth, Node> topUpdater
    = AtomicReferenceFieldUpdater.newUpdater(Fourth.class, Node.class, "top");
 
  public Fourth()
  {
    this.top = null;
  }
 
  public T pop() throws Exception
  {
    Node<T> node;
    do
    {
      node = this.top;
      if (node == null)
      {
        throw new Exception();
      }
    }
    while (Fourth.topUpdater.compareAndSet(this, node, node.getNext()));
    return node.getElement();
  }
 
  public void push(T element)
  {
    Node<T> node = new Node<T>(element, null);
    do
    {
        node.setNext(this.top);
    }
    while (Fourth.topUpdater.compareAndSet(this, node.getNext(), node));
  }
}