Java Reference
In-Depth Information
private class
Node
{
private
T data;
// queue entry
private
Node next;
// link to next node
< Constructors and the methods
getData
,
setData
,
getNextNode
, and
setNextNode
are here. >
. . .
}
// end Node
}
// end TwoPartCircularLinkedQueue
Programming Tip:
When a circular linked chain has one node, the node must reference
itself. Forgetting this step is easy to do and leads to an error during execution.
11.28
Adding to the back.
Before adding an entry to the queue, we see whether a node is available in the
chain. If one is not, we must allocate a new one and link it into the chain. We insert a new node into
the chain
after
the node that
freeNode
references, as we are about to do in Figure 11-15a. We do
not insert it before this node, because we would need a reference to the previous node to do so. Get-
ting such a reference would take time. The node that
freeNode
references joins the queue and will
contain the new entry. The new node becomes the unused node, and we make
freeNode
reference
it, as Figure 11-15b shows.
FIGURE 11-15
A chain that requires a new node for an addition to a queue:
(a) before the addition; (b) after the addition
(a)
(b)
queueNode
queueNode
The new node
newNode
freeNode
The new entry is
in this node
freeNode
If a node is available in the chain, we use the node that
freeNode
references for the new entry.
Figure 11-16 shows the chain before and after two existing nodes become part of the queue. After
each addition,
freeNode
references the node that follows the back of the queue. In Figure 11-16b,
this node is available for another addition, but in Figure 11-16c, it is unused.
The method
enqueue
is easier to write and to understand if we hide the detail of seeing whether
to allocate a new node within the private method
isChainFull
. It returns
true
if the chain has no
nodes available for use in the queue. The implementation of
isChainFull
is not difficult and
appears later in Segment 11.31.
