CSC152 2005F, Class 41: Queues

Admin:
* Exams due!
* Reading to be assigned over weekend.
* Sam will be reviewing grant proposals for NSF on Monday.  Eryn
  will run lab.
  * NSF writes: "Your panel will run until 5:30 or whenever you finish."
    If we run late, I won't make my plane, and you won't have class on
    Tuesday.

Overview:
* Questions on stacks?
* PAMI of Queues
* Implementation strategy one: Arrays
* Implementation strategy two: Nodes (pairs)

Stacks:
* Linear structure with LIFO policy
* We implement stacks with arrays (or Vectors)
* We put things at the "end" (larger indices)
* We get things at the "end" (larger indices)

Queues:
* Philosophy: Linear Structures with a FIFO policy
* Applications: 
  * Models the line at a grocery store
  * Many copmuter things should follow the same policy (printing queue)
  * Fairer for "to do lists"
* Methods
  * Same as linear structures
  * Queues were designed before linear structures
    * enqueue and dequeue (sometimes enque and deque)
      (sometimes nq dq)

Implementing Queues with Arrays/Vectors
* Add at the front and take off the back
  * Interpretation: Adding at the front requires shifting
  * Critique: Shifting is expensive (it's a lot of shifting)
* Another idea?
* Add to the end, remove from the front
  * When we remove, remember that we've shifted the front
  * Critique: Lots of blank space
  * Response to critique (from critic)
    * Wrap around
  * Critique of response to critique
    * But we must make sure we never have more things than are in the Vector
* In general, any strategy we choose will be a PITN

An alternate strategy: Use pairs/nodes

  +---+---+
  |   |   |
  +---+---+

car and cdr
The first part stores a 'value'
The second part stores the 'next node'
  +---+---+   +---+---+   +---+---+
  | * | *---> | * | *---> | * | / |
  +-|-+---+   +-|-+---+   +-|-+---+
    a           c           q

* If we keep track of the front of this structure (the first node),
  that gives us the front of the queue

  FRONT                             BACK
  +---+---+   +---+---+           +---+---+
  | * | *---> | * | *---> ... --> | * | / |
  +-|-+---+   +-|-+---+           +-|-+---+
    a           c                   q

after get
              FRONT                 BACK
              +---+---+           +---+---+
              | * | *---> ... --> | * | / |
              +-|-+---+           +-|-+---+
                c                   q

How do we add things?  keep track of the back
from
  FRONT                             BACK
  +---+---+   +---+---+           +---+---+
  | * | *---> | * | *---> ... --> | * | / |
  +-|-+---+   +-|-+---+           +-|-+---+
    a           c                   q
 to

  FRONT                                        BACK
  +---+---+   +---+---+           +---+---+   +---+---+
  | * | *---> | * | *---> ... --> | * | ----> | * | / |
  +-|-+---+   +-|-+---+           +-|-+---+   +-|-+---+
    a           c                   q           n

Turning strategy into code.

(1) Create a class, Node<T> that defines these node things.
  Two fields:
     T value
     Node next
(2) Create a class, NodeBasedQueue<T> (or LinkedQueue<T>), with at least two fields
     Node<T> front
     Node<T> back