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