Queue, Deque, and Priority Queue Implementations - Data Structures and Abstractions with Java - page 291

public boolean add(T newEntry)
public boolean offer(T newEntry)
public T remove()
public T poll()
public T element()
public T peek()
public boolean isEmpty()
public void clear()
public int size()

AbstractQueue provides implementations of the methods add , remove , and element that invoke
offer , poll , and peek , respectively.
You can define a class of queues by using inheritance to extend AbstractQueue . Your class
must override at least the following methods: offer , poll , peek , and size . Note that the class
java.util.PriorityQueue , which we mentioned in the previous chapter, extends AbstractQueue
and, thereby, implements the methods declared in the interface java.util.Queue .
To learn more about AbstractQueue , consult the online documentation for the Java Class Library.

A Doubly Linked Implementation of a Deque

11.34

Earlier, in Segment 11.1, we planned the linked implementation of the queue and noticed that the front
of the queue should not be at the tail of the chain of linked nodes. If it were, we would have to traverse
the chain to get a reference to the preceding node so that we could remove the queue's front entry.
Although placing the front of the queue at the head of the chain solved our problem, such is not
the case for a deque. We must be able to remove both the front and the back of a deque. So even if
the deque's front is at the head of the chain, the deque's back will be at the chain's tail—and therein
lies the problem.
Each node in a chain references only the next node. Thus, a chain, with its head reference, per-
mits us to begin at the first node and move ahead from node to node. Having a tail reference lets us
access the last node in the chain, but not the next-to-last node. That is, we cannot move backward
from a node, and this is just what we need to do to remove the back of a deque.

11.35

What we need is a node that can reference the previous node as well as the next node in a chain. We
call a chain of such nodes a doubly linked chain . We sometimes will call an ordinary chain a singly
linked chain when a distinction is necessary. Figure 11-17 illustrates a doubly linked chain with its
head and tail references. While an interior node references both the next node and the previous node,
the first and last nodes each contain one null reference. Thus, when traversing the chain from the first
node to the last, we will encounter null when we reach the last node. Likewise, when traversing the
chain from the last node to the first, we will encounter null when we reach the first node.

FIGURE 11-17

A doubly linked chain with head and tail references

lastNode

firstNode

The node in a doubly linked chain is an instance of an inner class similar to the class Node . We
will call this inner class DLNode and give it three data fields: next and previous are references to
two other nodes, and data is a reference to the node's data. DLNode also has the methods getData ,
setData , getNextNode , setNextNode , getPreviousNode , and setPreviousNode .