/*  Queue Linked-List class
 *  
 *  Class Name:     QueueLi
 *  Description:    Linked-list-based implementation of the queue 
 *  Author:         Ng Woon Liam
 *  Language:       Java
 *  Date:           10/1/2001
 *
 *  Public Methods: isEmpty()       Return true if empty; else false
 *                  goFront()       Return least recently inserted item;
 *                                  access item at the front of the line
 *                  outQueue        Return and remove least recent item;
 *                                  remove item from the front of the line     
 *                  inQueue()       Insert x; insert item at the back of the line 
 *                  makeEmpty()     Remove all items
 */

public class QueueLi implements Queue
{
    /**
     * Construct the queue.
     */
    public QueueLi( )
    {
	makeEmpty( );
    }

    public boolean isEmpty( )
    {
        return front == null;
    }

    public void makeEmpty( )
    {
        front = null;
        back = null;
    }

    public Object goFront( ) throws Exception
    {
        if( isEmpty( ) )
            throw new Exception( "QueueLi goFront" );
        return front.element;
    }

    public Object outQueue( ) throws Exception
    {
        if( isEmpty( ) )
            throw new Exception( "QueueLi outQueue" );

        Object returnValue = front.element;
        front = front.next;
        return returnValue;
    }

    public void inQueue( Object x )
    {
        if( isEmpty( ) )    // Make queue of one element
            back = front = new ListNode( x );
        else                // Regular case
            back = back.next = new ListNode( x );
    }

    private ListNode front;
    private ListNode back;
}