Differences

This shows you the differences between two versions of the page.

--- stack [2007/10/28 16:43] – external edit 127.0.0.1
+++ stack [2009/05/06 19:58] (current) – franck
@@ Line 1: / Line 1: @@
-Below we implement the following Stack interface in several different ways.
 <code java>
 /**
  * A Stack.
  */
-public interface Stack
+public interface Stack<T>
 {
   /**
@@ Line 11: / Line 9: @@
    *
    * @return the top element of this stack.
-   * @throw EmptyException if this stack is empty.
+   * @throw Exception if this stack is empty.
    */
-  public Integer pop() throws EmptyException;
+  public T pop() throws Exception;
   /**
    * Pushes the given element onto this stack.
@@ Line 20: / Line 18: @@
    * @param the element to be pushed onto this stack.
    */
-  public void push(Integer element);
+  public void push(T element);
 }
 </code>
 In each implementation of the above interface we will exploit the class Node.
 <code java>
 /**
- * A node of a linked list.  Each node contains an integer.
+ * A node of a linked list.
  */
-public class Node
+public class Node<T>
 {
-  private Integer element;
+  private T element;
-  private Node next;
+  private Node<T> next;
   /**
-   * Creates a new node with the given element and next node.
+   * Initializes this node with the given element and next node.
    *
    * @param element the element stored in the node.
@@ Line 42: / Line 40: @@
    * @param next the next node in the list.
    */
-  public Node(Integer element, Node next)
+  public Node(T element, Node<T> next)
   {
     this.element = element;
     this.next = next;
   }
   /**
    * Returns the element of this node.
@@ Line 53: / Line 51: @@
    * @return the element of this node.
    */
-  public Integer getElement()
+  public T getElement()
   {
     return this.element;
   }
   /**
    * Returns the next node.
@@ Line 63: / Line 61: @@
    * @return the next node.
    */
-  public Node getNext()
+  public Node<T> getNext()
   {
     return this.next;
   }
   /**
    * Sets the next node to the given node.
@@ Line 73: / Line 71: @@
    * @param node the new next node.
    */
-  public void setNext(Node next)
+  public void setNext(Node<T> next)
   {
     this.next = next;
@@ Line 80: / Line 78: @@
 </code>
 In the first implementation, we simply lock the whole stack when we pop or push an element.
 <code java>
-public class Stack1 implements Stack
+public class First<T> implements Stack<T>
 {
-  private Node top;
+  private Node<T> top;
-  /**
+  public First()
-   * Creates an empty stack.
-   */
-  public Stack1()
   {
     this.top = null;
   }
-  public synchronized Integer pop() throws EmptyException
+  public synchronized T pop() throws Exception
   {
     if (this.top == null)
     {
-      throw new EmptyException();
+      throw new Exception();
     }
     else
     {
-      Integer element = this.top.getElement();
+      T element = this.top.getElement();
       this.top = this.top.getNext();
       return element;
     }
   }
-  public synchronized void push(Integer element)
+  public synchronized void push(T element)
   {
-    this.top = new Node(element, this.top);
+    this.top = new Node<T>(element, this.top);
   }
 }
 </code>
 In the second implementation, we lock the top node when we pop or push an element.
 <code java>
-public class Stack2 implements Stack
+public class Second<T> implements Stack<T>
 {
-  private Node top;
+  private Node<T> top;
-  /**
+  public Second()
-   * Creates an empty stack.
-   */
-  public Stack2()
   {
-    this.top = new Node(null, null);
+    this.top = null;
   }
-  public Integer pop() throws EmptyException
+  public T pop() throws Exception
   {
+    Node<T> node;
     synchronized (this.top)
     {
-      if (this.top.getNext() == null)
+      if (this.top == null)
       {
-        throw new EmptyException();
+        throw new Exception();
       }
       else
       {
-        Integer element = this.top.getElement();
+        node = this.top;
         this.top = this.top.getNext();
-        return element;
       }
     }
+    return node.getElement();
   }
-  public void push(Integer element)
+  public void push(T element)
   {
-    Node node = new Node(element, null);
+    Node<T> node = new Node<T>(element, null);
     synchronized (this.top)
     {
@@ Line 160: / Line 153: @@
 </code>
-The third implementation does not use any locking.  We exploit the class AtomicReference.
+The third implementation does not use any locking. We exploit the class AtomicReference.
 <code java>
 import java.util.concurrent.atomic.*;
-public class Stack3 implements Stack
+public class Third<T> implements Stack<T>
 {
-  private volatile AtomicReference<Node> top;
+  private volatile AtomicReference<Node<T>> top;
-  /**
+  public Third()
-   * Creates an empty stack.
-   */
-  public Stack3()
   {
-    this.top = new AtomicReference<Node>();
+    this.top = new AtomicReference<Node<T>>();
   }
-  public Integer pop() throws EmptyException
+  public T pop() throws Exception
   {
-    Node node;
+    Node<T> node;
     do
     {
@@ Line 185: / Line 175: @@
       if (node == null)
       {
-        throw new EmptyException();
+        throw new Exception();
       }
     }
@@ Line 191: / Line 181: @@
     return node.getElement();
   }
-  public void push(Integer element)
+  public void push(T element)
   {
-    Node node = new Node(element, null);
+    Node<T> node = new Node<T>(element, null);
     do
     {
@@ Line 204: / Line 194: @@
 </code>
-Also the fourth implementation does not use any locking.  This time we exploit the class AtomicReferenceFieldUpdater.
+Also the fourth implementation does not use any locking. This time we exploit the class AtomicReferenceFieldUpdater.
 <code java>
 import java.util.concurrent.atomic.*;
-public class Stack4 implements Stack
+public class Fourth<T> implements Stack<T>
 {
-  private volatile Node top;
+  private volatile Node<T> top;
-  private static final AtomicReferenceFieldUpdater<Stack4, Node> topUpdater = AtomicReferenceFieldUpdater.newUpdater(Stack\
+  private static final AtomicReferenceFieldUpdater<Fourth, Node> topUpdater
-.class, Node.class, "top");
+    = AtomicReferenceFieldUpdater.newUpdater(Fourth.class, Node.class, "top");
-  /**
+  public Fourth()
-   * Creates an empty stack.
-   */
-  public Stack4()
   {
     this.top = null;
   }
-  public Integer pop() throws EmptyException
+  public T pop() throws Exception
   {
-    Node node;
+    Node<T> node;
     do
     {
@@ Line 232: / Line 219: @@
       if (node == null)
       {
-        throw new EmptyException();
+        throw new Exception();
       }
-    } while (!Stack4.topUpdater.compareAndSet(this, node, node.getNext()));
+    }
+    while (Fourth.topUpdater.compareAndSet(this, node, node.getNext()));
     return node.getElement();
   }
-  public void push(Integer element)
+  public void push(T element)
   {
-    Node node = new Node(element, null);
+    Node<T> node = new Node<T>(element, null);
     do
     {
         node.setNext(this.top);
     }
-    while (!Stack4.topUpdater.compareAndSet(this, node.getNext(), node));
+    while (Fourth.topUpdater.compareAndSet(this, node.getNext(), node));
   }
 }
 </code>