CSC148H lab -- week 4

This document contains the instructions for the week 4 CSC148H lab. To earn your lab mark, you must actively participate in the lab.

As always, you will work as a pair, taking turns being the driver and the navigator. The driver types, and the navigator watches for mistakes, thinking ahead. At the end of each exercise, switch roles.

This week's exercises are on the topic of queues.

Getting started

When it's your first turn as driver, both of you will need to begin by making a new folder "lab4". In this new folder you should save the files that we've provided for you: Queue.java, ArrayQueue.java, CircularQueue.java, and Driver.java.

At the end of each exercise, show your TA what you've done.

Exercise 1: Filling a Queue

Modify the contents of the main() method in the Driver class so that it creates an ArrayQueue with a capacity of 10 elements. Have it read lines of input from the user, stopping when the line "end" is read. Notice that our Queue doesn't use Java generics, so you can just put Strings into it without specifying what type you're storing.

Then modify Driver so that after the input is finished, it empties the Queue, printing each item as it is dequeued.

Exercise 2: Emptying a Queue recursively

Since you've just switched roles, have the new (human) driver re-enter the (Java) Driver code. (Omit the part about emptying the Queue, since you'll be redoing that in a moment.) Make sure that the Queue is declared like this:

Queue q = new ArrayQueue(10);

Notice that although it's aggravating to rewrite your programming, there are parts of it that go quicker and are done better.

Rewrite the queue-emptying part of Driver from Exercise 1 so that it uses recursion instead of iteration.

Exercise 3: Trying a different Queue implementation

This exercise and the next one are a little tricky. They should be good practice in thinking hard about code.

Before going on to the next step, make sure you've tried overfilling your ArrayQueue with too many items. For example, if you created it with a capacity for 10 items, try putting in 11 or 12. This is easier if you have the main loop in Driver print the size of the queue as part of the prompt when you're entering data.

Now modify Driver so that it uses a CircularQueue instead of an ArrayQueue. Make sure it works by enqueueing and dequeueing objects into queues of varying initial fullness.

Try overfilling your CircularQueue, just as you did with the ArrayQueue. Because of the precondition on the enqueue() method, any form of failure is acceptable, but the two implementations fail in quite different ways. Why is that?

Exercise 4: Modifying the implementation

Read the code for CircularQueue again. Notice that it uses three instance variables to keep track of which parts of its array are in use by the queue: head, tail and size.

Really, if you know where the head and tail of the queue are, you ought to be able to figure out the size -- the number of elements currently in the queue. Therefore, the goal of this exercise is to get rid of the size instance variable. You're still allowed to use head and tail, but you can't add another variable to get around the lack of size.

Essentially, this change is straightforward, but there are a couple of tricky cases that make it harder than you'd expect. To understand what you're doing, it helps to draw pictures of the array that stores the queue:

• First, draw the case where there's a queue of three items stored in an array of, say, five elements. Let head be 2, and tail be 4; the size of the queue is then 3. This is a simple case that should let you see the basic idea.
• What if the queue wraps around the end of the array? Try letting head be 4 and tail be 1. What is the queue size now? This is a slightly tricky case that you'll need to be aware of when writing the size() method.
• When there is one element in the queue, head and tail are the same. What happens when you remove that element, so that the queue is empty? This tells you the second tricky case: the representation of the empty queue.

Because of the last case -- the empty-queue case -- it will turn out that you need one extra array element, so that if the queue is not empty, there is always at least one unusued array element between the tail and the head of the queue.

Obviously, you need to try out your new CircularQueue with an empty queue, a partly filled one, and a full one. Besides fullness, what else do you need to vary in your testing?