Java Reference
In-Depth Information
is called if an enqueue requires a doubling of the array. It is slightly more com-
plex than the usual expansion because the queue items are not necessarily
stored in an array starting at location 0. Thus items must be copied carefully.
We discuss doubleQueue along with enqueue .
Many of the public methods resemble their stack counterparts, including
the constructor shown in Figure 16.12 and isEmpty , shown in Figure 16.13.
This constructor is not particularly special, except that we must be sure that
we have the correct initial values for both front and back . This is done by call-
ing makeEmpty .
The enqueue routine is shown in Figure 16.14. The basic strategy is simple
enough, as illustrated by lines 9-11 in the enqueue routine. The doubleQueue
routine, shown in Figure 16.15, begins by resizing the array. We must move
items starting at position front , rather than 0.
When we double
the queue array, we
cannot simply copy
the entire array
directly.
1 /**
2 * Internal method to increment with wraparound.
3 * @param x any index in theArray's range.
4 * @return x+1, or 0 if x is at the end of theArray.
5 */
6 private int increment( int x )
7 {
8 if( ++x == theArray.length )
9 x = 0;
10 return x;
11 }
figure 16.11
The wraparound
routine
1 /**
2 * Construct the queue.
3 */
4 public ArrayQueue( )
5 {
6 theArray = (AnyType []) new Object[ DEFAULT_CAPACITY ];
7 makeEmpty( );
8 }
figure 16.12
The constructor for
the ArrayQueue class
1 /**
2 * Test if the queue is logically empty.
3 * @return true if empty, false otherwise.
4 */
5 public boolean isEmpty( )
6 {
7 return currentSize == 0;
8 }
figure 16.13
The isEmpty routine
for the ArrayQueue
class
 
Search WWH ::




Custom Search