/**
  * LinkedListQueue
  * realizza l'interfaccia Queue usando internamente un array riempito parzialmente.
  * @author Adriano Luchetta
  * @version 3-Dic-2005
 */
 
 public class LinkedListQueue implements Queue
{
   // parte privata
   private ListNode head, tail;
   private int size;
   
   public LinkedListQueue()
   {
      makeEmpty();
   }
   
   public void makeEmpty()
   {
      head = tail = new ListNode();
      size = 0;
   }
   
   public boolean isEmpty()
   {
      return head == tail;
   }
   
   public int size()
   {
      return size;
   }
   
   public void enqueue(Object x)
   {
      tail.next = new ListNode(x, null);
      tail = tail.next;
      size++;
   }
   
   public Object getFront()
   {
      if (isEmpty())
         throw new EmptyQueueException();

      return head.next.element;
   }
   
   public Object dequeue()
   {
      Object tmp = getFront();
      
      head = head.next;
      head.element = null;
      size--;

      return tmp;
   }

   class ListNode
   {
      Object element;
      ListNode next;
      
      public ListNode(Object o, ListNode n)
      {
         element = o;
         next = n;
      }
      
      public ListNode()
      {
         this(null, null);
      }
   }
}