package username.linear;

/**
 * Part of a linked implementation of queues.
 *
 * @author Samuel A. Rebelsky
 * @author Your Name Here
 * @version 0.6 of March 2006
 */

  // +-------+-------------------------------------------------------------
  // | Notes |
  // +-------+
/*
  We use a set of QueueNodes to implement queues.  Each node
  contains one value and a link to the next QueueNode.  (The
  links in the nodes lead to the name of the structure.)

  We keep track of two values: front, the node at the front of the
  queue, and back, the node at the back of the queue.  We delete
  nodes from the front of the queue and add nodes to the back.

  When the queue is empty, the front and back are set to null.
 */
public class LinkedQueue<T>
  implements Queue<T>
{
  // +--------+------------------------------------------------------------
  // | Fields |
  // +--------+

  /** The node at the front of the queue. */
  QueueNode<T> front;

  /** The node at the back of the queue. */
  QueueNode<T> back;


  // +-------------+-------------------------------------------------------
  // | Construtors |
  // +-------------+

  /**
   * Build a new queue.
   */
  public LinkedQueue()
  {
    // We explicitly set the front and the back to null for safety.
    // However, Java should do so by default.
    this.front = null;
    this.back = null;
  } // LinkedQueue()


  // +---------+-----------------------------------------------------------
  // | Methods |
  // +---------+

  /**
   * Add an element to the end of the queue.
   *
   * @param val
   *   The object that is to be added.
   * @post
   *   The queue now contains an additional copy of val.
   */
  public void put(T val)
  {
    // Create a new node for the end of the queue.
    QueueNode<T> newback = new QueueNode<T>(val);
    // Put this new node after the current back
    this.back.next = newback;
    // Update our knowledge of the back of the queue
    this.back = newback;
  } // put(T)

  /**
   * Remove the least-recently-added element that is still in the
   * queue.
   *
   * @return val
   *   An object in the queue.
   * @pre
   *   The queue is not empty.
   * @post
   *   The queue contains one fewer copy of val.
   * @post
   *   Every value in the queue was added more recently than val.
   */
  public T get()
  {
    // Extract the value from the front.
    T val = this.front.contents;
    // Eliminate the front node by advancing to the next node.
    this.front = this.front.next;
    // Return the extracted value.
    return val;
  } // get()

  /**
   * Determine which object will next be returned by get.
   *
   * @return val
   *   An object in the queue.
   * @pre
   *   The queue is not empty.
   * @post
   *   Every other value in the queue was added less recently than val.
   */
  public T peek()
  {
    // The value to be returned is the contents for the front.
    return this.front.contents;
  } // peek()

  /**
   * Determine if the queue is empty.
   */
  public boolean isEmpty()
  {
    // The queue is empty if and only if front is null.
    return front == null;
  } // isEmpty()

} // class LinkedQueue<T>