Java Reference
In-Depth Information
Having a counter as a data field leads to a reasonable implementation, but each
enqueue
and
dequeue
must update the count. We can avoid this extra work by leaving one array location unused.
We develop this approach next.
Not using one array location allows us to distinguish between an empty queue and a full queue by
examining only
frontIndex
and
backIndex
. In Java, each array location contains only a reference, so
we waste little memory by having an unused location. Here we will leave unused the array location
that follows the back of the queue. Project 2 at the end of this chapter considers a different location.
Figure 11-8 illustrates a seven-element circular array that represents a queue of at most six
entries. As we add and remove entries, you should observe the effect on the indices
frontIndex
and
backIndex
. Part
a
of the figure shows the array initially, when the queue is empty. Notice that
frontIndex
is zero and
backIndex
contains the index of the array's last location. Adding an entry
to this queue increments the initial value of
backIndex
so that it becomes zero, as shown in Part
b
.
Part
c
illustrates the queue after five more additions, making it full. Now remove the front entry and
add an entry to the back, as Parts
d
and
e
show. The queue is full once again. Repeating this pair of
operations leads to the queues shown in Parts
f
and
g
. Now repeatedly remove the entry at the front
until the queue is empty. Part
h
shows the queue after the first of these
dequeue
operations, Part
i
shows it after all but one entry is removed, and Part
j
shows the empty queue.
To summarize, the queue is full in Parts
c
,
e
, and
g
of this figure. In each of these examples, the
index of the unused location is 1 more than
backIndex
and 1 less than
frontIndex
, if we treat the
array as circular. That is,
frontIndex
is 2 more than
backIndex
. Thus, the queue is full when
frontIndex
equals
(backIndex + 2) % queue.length
The queue is empty in Parts
a
and
j
. In those cases,
frontIndex
is 1 more than
backIndex
. Thus,
the queue is empty when
frontIndex
equals
(backIndex + 1) % queue.length
Admittedly, these criteria are more involved than checking a counter of the number of entries in the
queue. However, once we have them, the rest of the implementation is simpler and more efficient
because there is no counter to maintain.
VideoNote
The class
ArrayQueue
11.11
An outline of the class.
This array-based implementation of a queue begins with four data fields
and two constructors. The fields are the array of queue entries, indices to the front and back of the
queue, and an initial capacity for the queue that the default constructor creates. Another constructor
lets the client choose the initial queue capacity. The initial size of the array is one more than the
queue's initial capacity. Listing 11-2 outlines the class.
LISTING 11-2
An outline of an array-based implementation of the ADT queue
/**
A class that implements a queue of objects by using an array.
@author Frank M. Carrano
*/
public class
ArrayQueue<T>
implements
QueueInterface<T>
{
private
T[] queue;
// circular array of queue entries and one unused
// location
