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
;