Java Reference
In-Depth Information
private int frontIndex;
private int backIndex;
private static final int DEFAULT_INITIAL_CAPACITY = 50;
public ArrayQueue()
{
this (DEFAULT_INITIAL_CAPACITY);
} // end default constructor
public ArrayQueue( int initialCapacity)
{
// the cast is safe because the new array contains null entries
@SuppressWarnings("unchecked")
T[] tempQueue = (T[]) new Object[initialCapacity + 1];
queue = tempQueue;
frontIndex = 0;
backIndex = initialCapacity;
} // end constructor
< Implementations of the queue operations go here. >
. . .
} // end ArrayQueue
11.12
Adding to the back. The method enqueue first calls the private method ensureCapacity , which
doubles the size of the array if it is full, and then places the new entry immediately after the last
occupied location in the array. To determine the index of this location, we increment backIndex .
But since the array is circular, we use the operator % to make backIndex zero after reaching its
maximum value.
public void enqueue(T newEntry)
{
ensureCapacity();
backIndex = (backIndex + 1) % queue.length;
queue[backIndex] = newEntry;
} // end enqueue
The implementation of ensureCapacity differs from the one given in Chapter 6 because the
array here is circular. We will see how to implement it shortly.
The performance of enqueue when it does not resize the array is independent of the number
of entries in the queue. Thus, it is O(1) in this case. However, its performance degrades to O( n )
when the array is full, because resizing the array is an O( n ) operation. If this happens, however,
the very next enqueue is O(1) again. As we mentioned in Segment 6.9, we could amortize the
cost of doubling the array over all additions to the queue. That is, we let all enqueue operations
share the cost of resizing the array. Unless the array is resized many times, each enqueue is
almost O(1).
11.13
Retrieving the front entry. The method getFront returns either the array element at frontIndex
or null if the queue is empty:
public T getFront()
{
T front = null ;
 
Search WWH ::




Custom Search