CMPS 144L Lab Activity
Representing a Queue using a Circular Chain of Link1 Nodes

Background

In lecture we covered how to represent a queue using a chain of Link1 nodes, each of whose item fields represented one of the items in the queue. In such a chain, each node's next field points to the node that logically follows it in the queue (going from front to rear)...with the exception of the "rear node", the next field of which has value null.

Under this representation scheme (illustrated below using ASCII art), it makes the most sense for a Queue object to have not only an instance variable (called front, say) that points to the front node (containing Dog in the illustration) but also one (called rear, say) that points to the rear node (containing Cow in the illustration).

The pointer to the rear node is not essential, but without it the enqueue() operation would need to traverse the entire chain of Link1 nodes (via a loop) in order to "find" the rear node, whose next field must be changed to point to the new rear node that is being inserted at the end of the chain.

Figure 1: Representation of queue [Dog, Cat, ..., Elk, Cow] using a grounded chain of Link1 nodes

+----------+ item next item next item next | | +-----+---+ +-----+---+ +-----+---+ +-----+---+ | front *--+-->| Dog | *-+---->| Cat | *-+---> .... --->| Elk | *-+---->| Cow | *-+--|| | | +-----+---+ +-----+---+ +-----+---+ +-----+---+ | | ^ | rear *--+------------------------>----------------------------------------+ | | +----------+ Queue object

In this lab activity we explore a slightly different, and perhaps quirky, representation scheme in which a Queue object contains a rear instance variable but no front instance variable, and yet neither its enqueue() nor dequeue() method needs to include a loop.

How is this possible? Answer: By using a circular chain of Link1 nodes in which the rear node's next field —rather than being null— points to the front node! This applies even in the case that the queue has only one item on it, so that the rear and front nodes are one and the same node. (In that case, the node's next field points to the node itself.)

Using this approach, the equivalent to the illustration shown above is this:

Figure 2: Representation of queue [Dog, Cat, ..., Elk, Cow] using a circular chain of Link1 nodes

+----------+ item next item next item next | | +-----+---+ +-----+---+ +-----+---+ +-----+---+ | rear *---+-->| Cow | *-+---->| Dog | *-+--->| Cat | *-+---> .... --->| Elk | * | | | +-----+---+ +-----+---+ +-----+---+ +-----+-+-+ +----------+ ^ | Queue object | v +--------------------------------------------<--------------+

Task

There are only two blocks of code missing, one in the dequeue() method (to handle the case in which the queue already has at least one item in it) and the other in the enqueue() method (to handle the case in which the queue is not empty).

To figure out how to fill in the missing pieces of code, it may help to consider the example illustrated in Figure 2 above.

Suppose that dequeue() is applied to the queue represented there. That would mean that Dog is to be removed from the queue. The change needing to be made to the concrete representation is that the next field of the "Cow-node" should be changed to point to the "Cat-node". Ahh, but the Dog-node's next field already points to the Cat-node, so it is a matter of copying that pointer into the Cow-node's next field.

Now suppose that Bug is to be enqueued to the queue represented in Figure 2. The changes that need to be made within the concrete representation are these:

1. a new Bug-node must be created, with its next field set to point to the Dog-node.
2. Both the Cow-node's next field and the Queue object's rear field must be set to point to the new Bug-node.

Sample Dialog with QueueTester