// file:    SLQueue.java
// author:  Robert Keller
// purpose: Implement the Queue interface using linked lists.

/**
 * SLQueue is an implementation of Queue, a repository for Objects. 
 * Objects are inserted using enqueue and removed using dequeue. 
 * Objects are removed in the same order in which they are inserted.
 * A linked list is used to maintain the Queue.
 */

class SLQueue implements Queue
{
/**
 * the Cell containing the next Object to be removed
 */

protected Cell head;


/**
 * the Cell containing the most recent Object inserted
 */

protected Cell tail;


/**
 * Construct an empty SLQueue.
 */

public SLQueue()
  {
  head = tail = null;
  }


/**
 * Insert an Object in the queue.
 *
 * @param item the Object to be inserted
 */

public void enqueue(Object item)
  {
  if( head == null )
    {
    head = tail = new Cell(item, null);
    }
  else
    {
    tail = tail.Rest = new Cell(item, null);
    }
  }


/**
 * Remove an Object from the queue.
 *
 * @return the Object removed
 * @exception EmptyQueueException if the Queue is empty
 */

public Object dequeue() throws EmptyQueueException
  {
  if( head == null )
    {
    throw new EmptyQueueException();
    }

  Object result = head.First;
  head = head.Rest;
  return result;
  }


/**
 * Indicate whether or not the Queue is empty
 *
 * @return boolean indicating whether or not the Queue is empty
 */

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


/**
 * A Cell stores one Object in the Queue and points to the next newer Object
 * if any.
 */

class Cell
  {
  /**
   * the data in this Cell
   */

  Object First;


  /**
   * the next Cell in the Queue
   */

  Cell Rest;  


  /**
   * construct a Cell
   *
   * @param _First the Object in this Cell
   * @param _Rest the rest of the Queue after this Cell
   */

  Cell(Object _First, Cell _Rest)
    {
    First = _First;
    Rest = _Rest;
    }
  }
}