Java Reference
In-Depth Information
FRONT
FRONT
20
5
12
12
17
17
REAR
3
30
4
REAR
(A)
(B)
Figure4.26
The circular queue with array positions increasing in the clockwise
direction. (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.
position in the array to the lowest-numbered position. This is easily implemented
through use of the modulus operator (denoted by
%
in Java). In this way, positions
in the array are numbered from 0 through
size
1, and position
size
1 is de-
fined to immediately precede position 0 (which is equivalent to position
size%
size
). Figure 4.26 illustrates this solution.
There remains one more serious, though subtle, problem to the array-based
queue implementation. How can we recognize when the queue is empty or full?
Assume that
front
stores the array index for the front element in the queue, and
rear
stores the array index for the rear element. If both
front
and
rear
have the
same position, then with this scheme there must be one element in the queue. Thus,
an empty queue would be recognized by having
rear
be one less than
front
(tak-
ing into account the fact that the queue is circular, so position
size
1 is actually
considered to be one less than position 0). But what if the queue is completely full?
In other words, what is the situation when a queue with n array positions available
contains n elements? In this case, if the front element is in position 0, then the
rear element is in position
size
1. But this means that the value for
rear
is one
less than the value for
front
when the circular nature of the queue is taken into
account. In other words, the full queue is indistinguishable from the empty queue!
You might think that the problem is in the assumption about
front
and
rear
being defined to store the array indices of the front and rear elements, respectively,
and that some modification in this definition will allow a solution. Unfortunately,
the problem cannot be remedied by a simple change to the definition for
front
and
rear
, because of the number of conditions or states that the queue can be in.
Ignoring the actual position of the first element, and ignoring the actual values of
the elements stored in the queue, how many different states are there? There can
be no elements in the queue, one element, two, and so on. At most there can be
