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

11.30

Removing the front. The method dequeue returns the entry at the front of the queue. It then moves
the node at the front from the queue's part of the chain to the available part simply by advancing
queueNode . Parts c and d of Figure 11-14 show a chain before and after this step. Since the node
that contained the removed entry is not deallocated, it still references the removed entry. Thus, we
set the node's data portion to null .
Like getFront , dequeue is an O(1) operation:

public T dequeue()
{

T front = null ;
if (!isEmpty())
{

front = queueNode.getData();
queueNode.setData( null );
queueNode = queueNode.getNextNode();
} // end if
return front;
} // end dequeue

11.31

The rest of the class. The methods isEmpty and isChainFull follow from the discussion in
Segment 11.26:

public boolean isEmpty()
{

return queueNode == freeNode;
} // end isEmpty
private boolean isChainFull()
{

return queueNode == freeNode.getNextNode();
} // end isChainFull
The method clear sets queueNode equal to freeNode to make the queue appear empty. It
retains all nodes currently in the chain. However, unless you set the data portions of these nodes
to null , the objects in the queue are not deallocated. We leave the implementation of clear as an
exercise.

Question 7 Describe two different ways in which you could implement the method clear .

11.32

Choosing a linked implementation. So far, we have discussed several possible linked imple-
mentations of the ADT queue. You can use a linear chain with both head and tail references, as
shown in Figure 11-1, or an equivalent circular chain with one external reference, as shown in
Figure 11-12. In both of these implementations, removing an entry from the queue disconnects
and deallocates a node in the chain. If, after removing entries from the queue, you seldom add
entries, these implementations are fine. But if you frequently add an entry after removing one,
the two-part circular chain saves the time of deallocating and reallocating nodes.

Java Class Library: The Class AbstractQueue

11.33

The standard package java.util in the Java Class Library contains the abstract class AbstractQueue .
This class implements the interface java.util.Queue and does not allow null entries in the queue.
Recall from Segment 10.13 of the previous chapter the following methods in this interface: