Java Reference
In-Depth Information
FRONT
REAR
20
5
12
17
(A)
FRONT
REAR
12
17
3
30
4
(B)
Figure4.25
After repeated use, elements in the array-based queue will drift to
the back of the array. (a) The queue after the initial four numbers 20, 5, 12, and 17
have been inserted. (b) The queue after elements 20 and 5 are deleted, following
which 3, 30, and 4 are inserted.
Assume that there are n elements in the queue. By analogy to the array-based
list implementation, we could require that all elements of the queue be stored in the
first n positions of the array. If we choose the rear element of the queue to be in
position 0, then
dequeue
operations require only (1) time because the front ele-
ment of the queue (the one being removed) is the last element in the array. However,
enqueue
operations will require (n) time, because the n elements currently in
the queue must each be shifted one position in the array. If instead we chose the
rear element of the queue to be in position n 1, then an
enqueue
operation is
equivalent to an
append
operation on a list. This requires only (1) time. But
now, a
dequeue
operation requires (n) time, because all of the elements must
be shifted down by one position to retain the property that the remaining n 1
queue elements reside in the first n 1 positions of the array.
A far more efficient implementation can be obtained by relaxing the require-
ment that all elements of the queue must be in the first n positions of the array.
We will still require that the queue be stored be in contiguous array positions, but
the contents of the queue will be permitted to drift within the array, as illustrated
by Figure 4.25. Now, both the
enqueue
and the
dequeue
operations can be
performed in (1) time because no other elements in the queue need be moved.
This implementation raises a new problem. Assume that the front element of
the queue is initially at position 0, and that elements are added to successively
higher-numbered positions in the array. When elements are removed from the
queue, the front index increases. Over time, the entire queue will drift toward
the higher-numbered positions in the array. Once an element is inserted into the
highest-numbered position in the array, the queue has run out of space. This hap-
pens despite the fact that there might be free positions at the low end of the array
where elements have previously been removed from the queue.
The “drifting queue” problem can be solved by pretending that the array is
circular and so allow the queue to continue directly from the highest-numbered
