Java Reference
In-Depth Information
return
front;
}
// end dequeue
Like
getFront
,
dequeue
is an O(1) operation.
11.15
The private method
ensureCapacity
.
As you saw in Segment 2.32 of Chapter 2, when we increase the
size of an array, we must copy its entries into the newly allocated space. We need to be careful, though,
because here the array is circular. We must copy entries in the order in which they appear in the queue.
For example, the seven-element array in Figure 11-8g is full and appears again in Figure 11-10.
Call this array
oldQueue
. After allocating a new array
queue
of 14 locations, we copy the front of the
queue from
oldQueue[frontIndex]
to
queue[0]
. We continue copying elements from the old array
to the new array, proceeding to the end of the old array and wrapping around to its beginning, as the
figure shows. In addition, we must set
frontIndex
and
backIndex
to reflect the reorganized array.
FIGURE 11-10
Doubling the size of an array-based queue
oldQueue
is full
0
1
2
3
4
5
6
frontIndex
2
0
backIndex
frontIndex
0
backIndex
5
0
1
2
3
4
5
6
7
8
9
10
11
12
13
queue
has a larger capacity
The following definition of
ensureCapacity
detects when the array is full by using the criterion
given in Segment 11.10:
// Doubles the size of the array queue if it is full
private void
ensureCapacity()
{
if
(frontIndex == ((backIndex + 2) % queue.length))
// if array is full,
{
// double size of array
T[] oldQueue = queue;
int
oldSize = oldQueue.length;
// the cast is safe because the new array contains null entries
@SuppressWarnings("unchecked")
T[] tempQueue = (T[])
new
Object[2 * oldSize];
queue = tempQueue;
for
(
int
index = 0; index < oldSize - 1; index++)
{
queue[index] = oldQueue[frontIndex];
frontIndex = (frontIndex + 1) % oldSize;
}
// end for
frontIndex = 0;
backIndex = oldSize - 2;
}
// end if
}
// end ensureCapacity