//
// COMP102
// Example 12: Queues
//
// Paul E. Dunne 20/11/99
//
public class Queue
  {
  //*****************************************************
  // A Queue is implemented as a linked sequence of     *
  // QCell. A QCell comprising 2 fields: one the item   *
  // in the Queue (QItem); the other a link to the next *
  // Queue cell.                                        *
  //*****************************************************
  // QCell class only known to the Queue class itself.  *
  //*****************************************************
  private class QCell
    {
    //
    // QCell Fields
    //
    private Object QItem;
    private QCell  QLink;
    //
    // QCell Constructor
    //
    private QCell(Object head, QCell NextInQ)
      {
      QItem = head; QLink=NextInQ; 
      }
    }
  //******************************************************
  // Queue Fields                                        *
  //******************************************************
  //  First:  The QCell that contains the item at the    *
  //          head of the Queue.                         *
  //                                                     *
  //  Rest:   Indicates the Queue following the first    *
  //          Queue member.                              *
  //  Last:   The most recently added Queue Item         *
  //  Waiting:  The number of items in this Queue        *
  //******************************************************
  private QCell First;         
  private QCell Rest;         
  private QCell Last;
  private int Waiting; 
  //******************************************************
  // Queue Constructor - Initiates the Empty Queue       *
  //******************************************************
  public Queue()
    {
    First = null;
    Rest = null; 
    Last = null;
    Waiting=0;
    }
  //******************************************************
  // Queue Instance Methods                              *
  //******************************************************
  //
  // Test if this Queue Is Empty
  //
  public boolean QIsEmpty()
    {
    return (Waiting==0);       
    };
  //*****************************************************
  // Return the length of this Queue                    *
  //*****************************************************
  public int GetWaiting()
    {
    return Waiting;
    }
  //************************************************************
  //  Add a new Object to the end of this Queue;               *
  // The new item is added in such a way that in traversing    *
  // this Queue, the item will be the Last one found. Further  *
  // additions will be appended after this.                    *
  //************************************************************
  public void AddToQ ( Object EndofQ )
    {
    QCell temp;
    //**********************************************************
    // If this Queue is empty then the First and Last Queue    *
    // Cells are identical.                                    *
    //**********************************************************
    if (QIsEmpty())            
      {
      Last = new QCell(EndofQ,Last);   
      First = Last;
      Rest = First.QLink;;                      
      Waiting=1;                     
      }
    else                              
      {
      Last.QLink = new QCell(EndofQ,Last.QLink);  // The last item is the one being added.
      Last = Last.QLink;
      Waiting++;                                  // Increase Length of this Queue.
      };
    }
  //***************************************************************
  // Remove the First item (the item at the head of) this Queue   *
  //***************************************************************
  public void TakeOffQ()
    {
    if (Waiting<=1)                                // Will leave the empty Queue
      {                                            // after removal.
      First = null; Last=null; Rest=null;
      Waiting=0;
      }
    else
      {
      First = First.QLink;                         // Find the `new' head of the Queue.
      Waiting--;                                   // One fewer item in Queue.
      if (Waiting==1)                              // Deal with the case that there's
        {                                          // exactly one item left in this Queue.
        Last = First;
        Rest = null;      
        }
      else
        Rest = First.QLink;                        // If more than one; reset Rest of Queue
      };                                           // indicator.
    }
  //****************************************************************
  // Return the First item (the item at the head of) this Queue    *
  // The Queue structure is left unchanged.                        *
  //****************************************************************
  public Object GetFirstInQ()
    {
    if (!(Waiting==0))                // If there's anything to return
      return First.QItem;             // then return it.
    else
      return null;                    // otherwise return a null reference.
    }
  //*****************************************************************
  // Return the remainder  (all but the first item) of this Queue   *
  // The Queue structure is left unchanged.                         *
  //*****************************************************************
  public Queue GetRestOfQ()
    {
    Queue temporary= new Queue();
    temporary.First=First; temporary.Rest=Rest;
    temporary.Last=Last;
    temporary.Waiting = Waiting;
    temporary.TakeOffQ();
    return temporary;
    };
  //***********************************************************
  // Return a String representing the contents of this Queue  *
  // in a form that is suitable to print out.                 *
  //***********************************************************
  public String toString()
    {
    String res = new String();
    Queue temporary = new Queue();
    temporary.First = First; 
    temporary.Rest = Rest; 
    temporary.Last = Last;
    temporary.Waiting=Waiting;
    while (!temporary.QIsEmpty())
      {
      res = res+(temporary.GetFirstInQ()).toString()+"\n";
      temporary = temporary.GetRestOfQ();
      };
    return res;
    }     
  }