Stacks and queues - Data Structures and Problem Solving Using Java - page 604

Thus doubleQueue steps through the old array and copies each item to the
new part of the array at lines 11-12. Then we reset back at line 16. The dequeue
and getFront routines are shown in Figure 16.16; both are short. Finally, the
makeEmpty routine is shown in Figure 16.17. The queue routines clearly are
constant-time operations, so the cost of array doubling can be amortized over
the sequence of enqueue operations, as for the stack.
The circular array implementation of the queue can easily be done incor-
rectly when attempts to shorten the code are made. For instance, if you
attempt to avoid using the size member by using front and back to infer the
size, the array must be resized when the number of items in the queue is 1 less
than the array's size.

1 /**
2 * Insert a new item into the queue.
3 * @param x the item to insert.
4 */
5 public void enqueue( AnyType x )
6 {
7 if( currentSize == theArray.length )
8 doubleQueue( );
9 back = increment( back );
10 theArray[ back ] = x;
11 currentSize++;
12 }

figure 16.14
The enqueue routine
for the ArrayQueue
class

1 /**
2 * Internal method to expand theArray.
3 */
4 private void doubleQueue( )
5 {
6 AnyType [ ] newArray;
7
8 newArray = (AnyType []) new Object[ theArray.length * 2 ];
9
10 // Copy elements that are logically in the queue
11 for( int i = 0; i < currentSize; i++, front = increment( front ) )
12 newArray[ i ] = theArray[ front ];
13
14 theArray = newArray;
15 front = 0;
16 back = currentSize - 1;
17 }

figure 16.15
Dynamic expansion for the ArrayQueue class