CPSC 170 Lab 10: Queues

In class we discussed the Queue data structure. Save the following files to your directory:

• QueueADT.java -- The Queue ADT interface.
• LinkedQueue.java -- A skeleton for a linked implementation of a queue.
• LinearNode.java -- The usual LinearNode class.
• ArrayQueue.java -- A skeleton for an array implementation of a queue.
• ArrayIterator.java -- The ArrayIterator class that we discussed in class.
• TestQueue.java -- A simple program that creates and manipulates some queues.

Now proceed as follows:

1. Complete the method definitions in LinkedQueue.java. Remember that in enqueue and dequeue you have to maintain both the front and back pointers -- this takes a little extra thought. Also, you will need a LinkedIterator for the iterator method, but you can use the one from your Bag class -- just copy it to your lab10 directory. You should not need to modify it.

2. Study the code in TestQueue so you know what it is doing, then compile and run it. Correct any problems in your LinkedQueue class.

3. Complete the method definitions in ArrayQueue.java. Be sure that you use a circular implementation of the queue -- don't move everything down when you enqueue or dequeue. This means that whenever you increment an index, you have to do it mod the arraysize (use the % operator). As for the linked case, remember to maintain both the front and back indices when you modify the queue. You also have to initialize them, which can take some thought. One possibility is to initialize front to 0 and back to -1. This may look odd, but it works nicely -- when you enqueue the first item, back will increase to 0, which is just what you want. Just be sure to use the number of elements, not the values of front and back, to determine whether the queue is empty.

   The trickiest parts of the array implementation are increaseSize() and iterator(). (Remember that increaseSize is a private method that is called from enqueue when the array is already full. I did not put it in the skeleton, so you'll need to add it.) The front of the queue may not be at location 0 in the old array, but when you increase the size you may as well put it at location 0 in the new array (it's even more complicated if you don't). So your loop that copies needs to keep track of two sets of indices -- the index in the old array, which will need to wrap around, and the index in the new array, which will start at 0. You will need to do something similar in the iterator, since ArrayIterator assumes that the array elements start at location 0. Here you don't need to increase the size of the array, but you do need to create a new array and copy the elements to it starting at location 0 before passing the array to the ArrayIterator constructor. You do not need to modify the ArrayIterator class.

4. Modify TestQueue.java so that it creates an ArrayQueue instead of a LinkedQueue. Don't change anything else in the file! Compile and run it, and be sure that it works as before.

5. Modify TestQueue.java so that just before it dequeues everything in the queue, it reverses the order of the elements in the queue. There is no Queue method to do this, so you'll have to figure out a way to do it yourself. Do NOT modify ArrayQueue or LinkedQueue. (Hint: Use a stack -- we didn't write one, but you can use the Stack class in java.util, which has the usual push and pop operations.) Print a message saying that you're reversing the queue, but you don't need to print the queue again -- when you print the elements as you dequeue them they'll just come out in reverse order.

What to turn in