Java Reference
In-Depth Information
Q
head
0
3
tail
QA
36
15
52
0
1
2
3
4
5
Figure 4-6. State of the queue after adding 36, 15, and 52
Note that head points “just in front of ” the item, which is actually at the head of the queue, and tail points at the
last item in the queue.
Now consider taking something off the queue. The item to be taken off is the one at the head. To remove it, we
must first increment head and then return the value pointed to by head .
For example, if we remove 36 , head will become 1 , and it points “just in front of ” 15 , the item now at the head.
Note that 36 still remains in the array, but, to all intents and purposes, it is not in the queue.
Suppose we now add 23 to the queue. It will be placed in location 4 with tail being 4 and head being 1 .
The picture now looks like Figure 4-7 .
Q
head
1
3
tail
QA
36
15
52
23
0
1
2
3
4
5
Figure 4-7. State of the queue after removing 36 and adding 23
There are three items in the queue; 15 is at the head, and 23 is at the tail.
Consider what happens if we continuously add items to the queue without taking off any. The value of tail
will keep increasing until it reaches MaxQ-1 , the last valid subscript of QA . What do we do if another item needs to be
added?
We could say that the queue is full and stop the program. However, there are two free locations, 0 and 1 . It would
be better to try to use one of these. This leads us to the idea of a circular queue . Here, we think of the locations in the
array as arranged in a circle: location MaxQ-1 is followed by location 0 .
So, if tail has the value MaxQ-1 , incrementing it will set it to 0 .
Suppose we had not taken off any item from the queue. The value of head will still be 0 . Now, what if, in
attempting to add an item, tail is incremented from MaxQ-1 to 0 ? It now has the same value as head . In this situation,
we declare that the queue is full.
We do this even though nothing is stored in location 0 , which is, therefore, available to hold another item. The
reason for taking this approach is that it simplifies our code for detecting when the queue is empty and when it is full.
This is also the reason why we set both head and tail to 0 initially. It enables us to easily detect when the queue is full
if items are inserted continuously.
To emphasize, when the queue is declared full, it contains MaxQ-1 items .
 
Search WWH ::




Custom Search