Java Reference
In-Depth Information
We also present a linked implementation of the double-ended queue, or deque. Since the deque
allows access to both its front and its back, an ordinary chain of linked nodes is not sufficient. For
example, deleting the last node in a chain is not possible without a reference to the preceding node.
Thus, we use a new kind of chain, one that links its nodes in both directions. That is, a node in this
chain references both the next node and the one that precedes it. Such a chain provides an efficient
implementation of the deque.
Finally, we suggest some implementations of the ADT priority queue. We note, however,
that a more efficient implementation will be possible when we encounter the ADT heap in
Chapters 23 and 26.
A Linked Implementation of a Queue
11.1
If we use a chain of linked nodes to implement a queue, the two ends of the queue will be at oppo-
site ends of the chain. If we have only a head reference to the chain, accessing the chain's last node
will be inefficient. Adding a tail reference —an external reference to the last node in the chain—is
one approach to this problem and is the one we will take here.
With both head and tail references, which node should be the front of the queue and which
node should be the back? We must be able to remove the entry at the front of the queue. If it is at
the beginning of the chain, we will be able to remove it easily. If it is at the end of the chain,
however, removing it requires a reference to the preceding node. To get such a reference, we
must traverse the chain. Thus, we reject this option and make the chain's first node contain the
queue's front entry.
Placing the front of the queue at the beginning of the chain obviously forces the back of the
queue to the chain's end. Since we add entries only to the back of the queue, and since we have a
tail reference for the chain, this arrangement will work.
Figure 11-1 illustrates a chain of linked nodes with both head and tail references. The chain
contains one node for each entry in the queue. Nodes are allocated only when needed for a new
entry and are deallocated when an entry is removed.
VideoNote
The class LinkedQueue
FIGURE 11-1
A chain of linked nodes that implements a queue
firstNode
lastNode
Entry at front
of queue
Entry at back
of queue
11.2
An outline of the class. The linked implementation of the queue has two data fields. The field
firstNode references the chain's first node, which contains the queue's front entry. And lastNode
references the chain's last node, which contains the entry at the back of the queue. Since both of
these fields are null when the queue is empty, the default constructor sets them to null . An outline
of our class appears in Listing 11-1.
The class also contains the private class Node , like the one you saw in Listing 3-4 of Chapter 3.
We also used this class in Chapter 6 for an implementation of the ADT stack.
 
 
Search WWH ::




Custom Search