Java Reference
In-Depth Information
You can implement a queue by using an array. Once a queue entry is added to the array, it does not move.
After many additions, the last array location will be used. Removals, however, will free locations at the
beginning of the array. Thus, the array can appear full even when it is not. To solve this problem, you treat
the array as if it were circular.
The queue operations are O(1) for an array-based implementation. However, when the array is full, enqueue
doubles the size of the array. In that case, enqueue is O( n ). Typically, we amortize the cost of resizing the
array over all additions to the queue. If the array is resized occasionally, each enqueue is almost O(1).
You can implement a queue by using a vector. Since the entry at the front of the queue is always first in the
vector, and since the implementation of Vector is based on an array that is expanded as necessary, entries in
the vector move. Thus, the vector-based implementation is less efficient than our array-based implementa-
tion. However, it is easier to write.
In a circular linked chain, every node references the next node in the chain. No node contains null in its next field.
A circular linked chain can have a beginning and an end. Since the last node references the first node in the chain,
one external reference to the last node provides convenient access to both the chain's last node and its first node.
You can use a circular linked chain to implement a queue in much the same way that you use a linear linked chain
that has both head and tail references. With both kinds of chain, dequeue removes a node and deallocates it.
Another implementation of a queue uses a circular linked chain that has two parts. One part is used for the
queue and the other part contains one unused node and any nodes that are available for use. In this imple-
mentation, dequeue removes an entry from the queue but does not remove a node from the chain. Instead,
the node joins the available part of the chain.
Since a deque has operations that add and remove entries at both ends, you can use a doubly linked chain
whose nodes reference both the next node and the previous node. A doubly linked chain with head and tail
references provides O(1) implementations of the deque operations.
In a circular doubly linked chain, every node references the next node as well as the previous node in the
chain. No node contains null in its next and previous fields. One external reference to the first node pro-
vides fast access to both the chain's last node and its first node. You can use a circular doubly linked chain in
the implementation of a deque.
You can use an array or a chain to implement a priority queue, but a more efficient implementation is possible
by using a heap.
P ROGRAMMING T IP
When a circular linked chain has one node, the node must reference itself. Forgetting this step is easy to do
and leads to an error during execution.
E XERCISES
1.
Segment 11.15 defines the private method ensureCapacity for an array-based implementation of the ADT queue.
Revise that method to use the method System.arraycopy to copy the old array to a new expanded array.
2.
Segment 11.31 describes an implementation of the queue's method clear when a two-part circular linked chain
represents the queue. Write two different implementations of clear . One version should repeatedly invoke
dequeue . The other version should set the data portion of each node in the queue to null .
3.
Suppose that we want to add a method to a class of queues that will splice two queues together. This method adds
to the end of a queue all items that are in a second queue. The header of the method could be as follows:
public void splice(QueueInterface<T> anotherQueue)
Write this method in such a way that it will work in any class that implements QueueInterface<T> .
 
Search WWH ::




Custom Search