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

Now if we remove the entry at the front of the queue, we advance queueNode so the chain is as
pictured in Figure 11-14d. The node that was at the front of the queue is not deallocated. A subse-
quent addition—since it is at the back of the queue—uses the node that freeNode references. We
then advance freeNode . Figure 11-14e shows the chain at this point. Notice that we did not allocate
a new node for the additional entry in this case.
How can we tell whether we must allocate a new node when we add to the queue? We must
do so if we want to add to the queue shown in Figure 11-14e. At this point, queueNode equals
freeNode.getNextNode() . That was not the case when we added an entry to the queue in
Figure 11-14d; a node was available without allocating a new one. But notice in Figure 11-14a that
queueNode also equals freeNode.getNextNode() when the queue is empty. This makes sense,
because to add to an empty queue, we need to allocate a new node.

Note: In a two-part circular linked implementation of a queue, one node is unused. Two
external references partition the chain into two parts: queueNode references the front node of
the queue and freeNode references the node that follows the queue. The queue is empty if
queueNode equals freeNode . You use the node at freeNode for a new entry. This node is
either the first available node or the unused node. You must allocate a new unused node if
queueNode equals freeNode.getNextNode() .

11.27

An outline of the class. The class that implements the queue by using a two-part circular linked chain
has the references queueNode and freeNode as data fields. Since the chain must always contain at least
one node, the default constructor allocates a node, makes the node reference itself, and sets queueNode
and freeNode to reference this new node. Thus, the class appears as outlined in Listing 11-4.

LISTING 11-4

An outline of a two-part circular linked implementation of the
ADT queue

/**

A class that implements a queue of objects by using
a two-part circular chain of linked nodes
@author Frank M. Carrano

*/
public class TwoPartCircularLinkedQueue<T> implements QueueInterface<T>
{

private Node queueNode; // references first node in queue
private Node freeNode; // references node after back of queue

public TwoPartCircularLinkedQueue()
{

freeNode = new Node( null , null );
freeNode.setNextNode(freeNode);
queueNode = freeNode;
} // end default constructor

< Implementations of the queue operations go here. >
. . .