CSC152 2004F, Class 32: Queues

Admin:
* Exam to be distributed Friday (may be available via email sooner)
* New assignment: Think about priority queues
* Homework due!

Overview:
* Discussion of homework
* Queues, reviewed
* The Billups implementation, explored
* An alternate implementation
* Priority queues

/Homework: Fix ArrayBasedStack so that it expands appropriately/

* We will look at Louisa's *incorrect* solution, which I've called LABS
* Problem one: She used too complex a solution.  Use the normal array methods.
* Problem two: Inelegant.  Duplicated code need only appear once.
* Problem three: Doesn't seem to do the copying.  Loop should have used < contents.length as the test (rather than >= contents.length)

/Queues/

* A queue is a linear structure with a FIFO policy
* A queue is like a line (at a store); clearly named by a brit.
* You put something at the end; You remove from the front
* You remove things from the line in the order that you add them to the line

/How Can We Implement Queues?/

* Like Stacks!  
  * Use an array.
  * Keep track of first and last.
  * Copy stuff "left" when last gets too big and first is nonzero
* Question:
  * How do I decide if the queue is empty?
    * Inefficient: Look at each cell and see if it contains null.
    * Check what's at last: If it's null, then it's empty
    * If first > last
* Design: Instead of copying left, why not "wrap around" to the beginning?
  * It's a good idea, but fraught with peril.  Exam question!
* Another problem with this idea: Inefficiency.  Assume N is the array length.
	for (int i = 0; i < N; i++) {	// N repetitions
		q.put("value " + i);	// O(1)
	}

	The "initialization" about took O(N)

	for (int i = 0; i < N; i++) {	// N repetitions
		pen.println(q.get());	// O(1)
		q.put("value2 "  + i);  // O(N)
	}

	The puts should be O(1) but end up being O(N)
* Solution one: Use Kevin's idea.

/Another Solution: Linked Queues/

* Key idea: We're barely taking advantage of the key ideas of the array (indexed access to data); We might find a "simpler" way to implement queues.
* Use an idea from Scheme: The Pair (QueueNodes for this instance)
* A QueueNode stores two values:
  * An element in the Queue
  * The rest of the queue
* A Queue stores 
  * A reference to the QueueNode at the front
  * A reference to the QueueNode at the back
  * Lenght (maybe)
* To get an element
  * Get the value stored in the front QueueNode
  * Move front to the ntext QueueNode
* To add to the queue
  * Build a new QueueNode
  * Make the back QueueNode refer to that as "rest"
  * Update back
* Problem: What if the back is empty?