Java Reference
In-Depth Information
11.14
Removing the front entry.
The method
dequeue
, like
getFront
, retrieves the entry at the front of
the queue, but then it removes it. To remove the front entry of the queue shown in Figure 11-9a, we
could simply increment
frontIndex
, as Figure 11-9b illustrates. This step would suffice because
the other methods would behave correctly. For example,
getFront
would return the item that
queue[6]
references. However, the object that previously was the front of the queue and is returned
to the client would still be referenced by the array. This fact is of no real concern if our implemen-
tation is correct. To be safe,
dequeue
can set
queue[frontIndex]
to
null
before incrementing
frontIndex
. Figure 11-9c illustrates the queue in this case.
FIGURE 11-9
An array-based queue: (a) initially; (b) after removing its
front entry by incrementing
frontIndex
; (c) after removing
its front entry by setting
queue[frontIndex]
to
null
and then
incrementing
frontIndex
(a)
5
6
7
0
49
5
frontIndex
7
backIndex
Entry at back
of queue
Entry at front
of queue
(b)
5
7
0
6
49
6
frontIndex
backIndex
7
front
Entry at back
of queue
Returned
to client
Entry at front
of queue
(c)
5
6
7
0
49
6
frontIndex
null
7
backIndex
front
Entry at back
of queue
Returned
to client
Entry at front
of queue
The following implementation of
dequeue
reflects these comments:
public
T dequeue()
{
T front =
null
;
if
(!isEmpty())
{
front = queue[frontIndex];
queue[frontIndex] =
null
;
frontIndex = (frontIndex + 1) % queue.length;
}
// end if
