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