Java Reference
In-Depth Information
FIGURE 11-7
A circular array that represents a queue: (a) when full; (b) after
removing two entries; (c) after removing three more entries; (d) after
removing all but one entry; (e) after removing the remaining entry
(a)
0
1
46
47
48
49
frontIndex
47
46
backIndex
Full queue
(b)
0
46
48
1
47
49
49
frontIndex
backIndex
46
(c)
0
1
2
46
47
48
49
2
frontIndex
46
backIndex
(d)
0
1
47
49
46
48
frontIndex
46
46
backIndex
(e)
0
1
46
47
48
49
47
frontIndex
46
backIndex
Empty queue
Now remove some entries from the queue. Figure 11-7b shows the array after executing
dequeue
twice. Notice that
frontIndex
advances to 49. If we continue to remove items from the
queue,
frontIndex
will wrap around to zero and beyond. Figure 11-7c shows the array after three
more items are removed. As we remove more items from the queue,
frontIndex
advances.
Figure 11-7d shows the array after all but one item is removed from the queue. Now let's remove
that one item. In Figure 11-7e, we see that this last removal has caused
frontIndex
to advance so
that it is 1 more than
backIndex
. Although the queue is empty,
frontIndex
is
backIndex
+
1. This
is exactly the same condition we encountered in Figure 11-7a when the queue was full.
Note:
With a circular array,
frontIndex
equals
backIndex
+
1 both when the queue is
empty and when it is full.
As you can see, we cannot test whether the queue is empty or full by using
frontIndex
and
backIndex
. One solution is to maintain a count of queue items. If the count is zero, the queue is
empty; if the count equals the array's capacity, the queue is full. When the queue is full, the next
enqueue
operation can double the array's size before adding a new entry.
