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?