CPSC 170 Lab 10: Queues
As usual, create a lab10 subdirectory for today's lab, open this
document in Mozilla, and start emacs.
In class we discussed the Queue data structure. Save the following
files to your directory:
Now proceed as follows:
- 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.
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.
- Study the code in TestQueue so you know what it is doing,
then compile and run it. Correct any problems in your LinkedQueue class.
- 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.
- 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.
- 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
Turn in hardcopy of LinkedQueue.java, ArrayQueue.java and TestQueue.java.
Tar your lab10 directory and e-mail it to me with cpsc170 lab10 in
the Subject line.