Java Reference
In-Depth Information
FIGURE 11-6
An array that represents a queue without moving any entries:
(a) initially; (b) after removing the entry at the front twice;
(c) after several more additions and removals; (d) after two
additions that wrap around to the beginning of the array
(a)
0
1
2
3
4
5
49
frontIndex
0
5
backIndex
Entry at front
of queue
Entry at back
of queue
(b)
0
1
2
3
5
4
49
2
frontIndex
backIndex
5
Entry at front
of queue
Entry at back
of queue
(c)
0
1
47
48
49
47
frontIndex
49
backIndex
Entry at front
of queue
Entry at back
of queue
(d)
0
1
48
49
47
47
frontIndex
backIndex
1
Entry at back
of queue
Entry at front
of queue
11.9
Complications. Using a circular array complicates the implementation somewhat. For example,
how can we detect when the array is full? Clearly the array in Figure 11-7a is full. This array is the
result of several additions to the queue pictured in Figure 11-6d. So it appears that the queue is full
when frontIndex is backIndex + 1.
 
Search WWH ::




Custom Search