Java Reference
In-Depth Information
11.40
Reusing this implementation.
Once you have implemented the ADT deque, you can use it to
implement other ADTs such as the queue and the stack. These implementations are straightforward
and are left as exercises.
Note:
In a doubly linked chain, the first and last nodes each contain one
null
reference,
since the first node has no previous node and the last node has no node after it. In a
circular
doubly linked chain
, the first node references the last node, and the last node references the
first. Only one external reference is necessary—a reference to the first node—since you can
quickly get to the last node from the first node. You can use a circular doubly linked chain in
an implementation of the ADT deque. Project 8 asks you to do this.
11.41
We can use an array, a linked chain, or a vector to implement the ADT priority queue. In each of
these cases, we would maintain the entries in sorted order by their priorities. With an array, the
entry with the highest priority should occur at the end of the array, so removing it would leave the
other entries in their present places. Figure 11-20a illustrates this implementation.
If a linked chain contains the entries in a priority queue, the entry with the highest priority should
occur at the beginning of the chain, where it is easy to remove. Figure 11-20b shows such a chain.
The next chapter will introduce the ADT list, and Chapter 16 will discuss a kind of list called
the sorted list. A sorted list can maintain a priority queue's entries in priority order, doing much of
the work for us. Project 10 at the end of Chapter 16 asks you to complete such an implementation.
Chapter 23 describes a more efficient implementation of a priority queue that uses an ADT
called a heap.
FIGURE 11-20
Two possible implementations of a priority queue using (a) an array;
(b) a chain of linked nodes
(a)
0
1
2
3
4
5
49
3
lastIndex
2
5
6
9
Highest-priority entry
(b)
firstNode
6
9
5
2
Highest-priority entry
C
HAPTER
S
UMMARY
•
You can implement a queue by using a chain of linked nodes that has both a head reference and a tail refer-
ence. The first node in the chain represents the front of the queue, because you can remove or access a
chain's first node faster than any other node. The tail reference allows you to quickly add a node to the end
of the chain, which is the queue's back.
•
The queue operations are O(1) for a linked implementation.
