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
 
Search WWH ::




Custom Search