/**
   usa come struttura dati una doppia catena.
   FIFO: elementi inseriti in testa ed estratti in coda
   LIFO: elementi inseriti ed estratti in testa
   
   Tutti i metodi della classe hanno complessita' temporale O(1).
*/
public class MySQ implements StackAndQueue
{
   private ListNode head;
   private ListNode tail;
   private int size;
   
   public MySQ()
   {
      makeEmpty();
   }
   
   /** O(1) */
   public void pushAndEnqueue(Object obj)
   {
      ListNode tmpHead = new ListNode(null, head, null);
      head.element = obj;
      head.previous = tmpHead;
      head = tmpHead;

      size++;
   }

   /** O(1) */
   public Object pop() throws EmptyStackException
   {
      Object tmpObj = top();
      head.next.element = null;
      head.next.previous = null;
      head = head.next;
      size--;

      return tmpObj;
   }
   
   /** O(1) */
   public Object dequeue() throws EmptyQueueException
   {
      Object tmpObj = getFront();
      tail.previous.element = null;
      tail.previous.next = null;
      tail = tail.previous;
      size--;

      return tmpObj;
   }
   
   /** O(1) */
   public Object top() throws EmptyStackException
   {
      if (isEmpty())
        throw new EmptyStackException();

      return head.next.element;
   }
   
   /** O(1) */
   public Object getFront() throws EmptyQueueException
   {
      if (isEmpty())
        throw new EmptyQueueException();

      return tail.previous.element;
   }
   
   /** O(1) */
   public void makeEmpty()
   {
      head = new ListNode();
      tail = new ListNode();
      head.next = tail;
      tail.previous = head;
      size = 0;
   }
   
   /** O(1) */
   public boolean isEmpty()
   {
      return head.next == tail;
   }
   
   /** O(1) */
   public int size()
   {
      return size;
   }

   private class ListNode
   {
      Object element;
      ListNode next;
      ListNode previous;

      public ListNode(Object e, ListNode n, ListNode p)
      {
         element = e;
         next = n;
         previous = p;
      }
      
      public ListNode()
      {
         this(null, null, null);
      }
   }
}