/**
   The LinkedQueue class implements the Queue interface by means of
   a linked list without dummy nodes.
 
   @author      Franck van Breugel
   @version     1.2    May 10, 2000
   @see Node
*/
public class LinkedQueue implements Queue 
{
    private Node head; // reference to first node of list
    private Node tail; // reference to last node of list
    private int size;  // size of queue

    /** 
     * Constructs an empty LinkedQueue. 
     */
    public LinkedQueue() 
    {
        head = null;
        tail = null;
        size = 0;
    }

    public int size() 
    {
        return size;
    }

    public boolean isEmpty() 
    {
        return (size == 0);
    }

    public Object front() throws QueueEmptyException 
    {
        if (isEmpty()) 
        {
            throw new QueueEmptyException("Queue is empty.");
        }
        return head.getElement();
    }

    public Object dequeue() throws QueueEmptyException 
    {
        if (isEmpty()) 
        {
            throw new QueueEmptyException("Queue is empty.");
        }
        Object temp = head.getElement();
        head = head.getNext();
        size--;
        if (size == 0) 
        {
            tail = null;
        }
        return temp;
    }  

    public void enqueue(Object element) 
    {
        Node node = new Node(element, null);
        if (size == 0) 
        {
            head = node;
        } 
        else 
        {
            tail.setNext(node);
        }
        tail = node;
        size++;
    } 

    /**
       Returns a string representation of this queue.
      
       @return A string representation of this queue.
    */
    public String toString() 
    {
        String rep = "";
        for (Node n = head; n != null; n = n.getNext()) 
        {
        /* rep = element contained in head + "\n" + ... + element contained in node before node n + "\n" */
            rep += n.getElement().toString();
            rep += "\n";
        }
        return rep;
    }
}