/**
  realizza l'interfaccia Stack usando una lista concatenata come struttura dati
*/

public class MyStack implements Stack
{
   private ListNode head;
   private ListNode tail;
   private int size;

   public MyStack()
   {
      makeEmpty();
   }

   /** O(1) */
   public void push(Object obj)
   {
      head.element = obj;
      head = new ListNode( null, head);
      size++;
   }
   
   /** O(1) */
   public Object pop() throws EmptyStackException
   {
      if (isEmpty())
         throw new EmptyStackException();
         
      Object tmp = head.next.element;
      head.next.element = null;
      head = head.next;
      size--;
      return tmp;
   }
   
   /** O(1) */
   public Object top() throws EmptyStackException
   {
      if (isEmpty())
         throw new EmptyStackException();

      return head.next.element;
   }
   
   public int size() { return size; }
   public boolean isEmpty() { return head == tail; }
   public void makeEmpty()
   {
      head = tail = new ListNode();
      size = 0;
   }
   
   private class ListNode
   {
      Object element;
      ListNode next;
      
      public ListNode(Object el, ListNode n)
      {
         element = el;
         next = n;
      }

      public ListNode()
      {
         this(null, null);
      }
   }
}