Java Reference
In-Depth Information
You can use the method
System.arraycopy
to copy the array. However, since the array is cir-
cular, you will need two calls to this method. Exercise 1 at the end of this chapter asks you to revise
ensureCapacity
in this way.
11.16
The rest of the class.
The public method
isEmpty
has the following implementation, based on our
comments at the end of Segment 11.10:
public boolean
isEmpty()
{
return
frontIndex == ((backIndex + 1) % queue.length);
}
// end isEmpty
The method
clear
could simply set
frontIndex
to 0 and
backIndex
to
queue.length
-
1. The
other queue methods would behave as expected for an empty queue. However, the objects that were in
the queue would then remain allocated. To deallocate them,
clear
should set to
null
each array location
that was used for the queue. Alternatively,
clear
could call
dequeue
repeatedly until the queue is empty,
if
dequeue
sets
queue[frontIndex]
to
null
. We leave the implementation of
clear
as an exercise.
Question 3
Write an implementation of
clear
that sets to
null
each array location that
was used for the queue.
Question 4
Write an implementation of
clear
that repeatedly calls
dequeue
until the queue is
empty. How does this implementation compare to the one you wrote for Question 3?
Question 5
If
queue
is an array that contains the entries in a queue, and
queue
is not treated as
a circular array, what is a disadvantage of maintaining the back of the queue at
queue[0]
?
Note:
In some languages other than Java, leaving an array location empty wastes memory
because the location contains an object instead of a reference to an object. Project 3 at the end
of this chapter considers an array-based implementation of a queue that does not have an
unused location and does not maintain a counter.
11.17
Using a vector to represent a queue's entries is relatively easy. We maintain the front of the queue at
the beginning of the vector, as Figure 11-11 illustrates. We can use
Vector
's method
add
to add an
entry to the back of the queue. When we remove the queue's front entry from the vector, the vector's
elements move so that the new front entry in the queue will be at the beginning of the vector. Thus, we
do not need to maintain indices to the front and back of the queue. Also, the vector expands as neces-
sary, so we do not have to worry about this detail.
FIGURE 11-11
A vector that represents a queue
0
1
2
3
49
Entry at front
of queue
Entry at back
of queue