Java Reference
In-Depth Information
FIGURE 11-16
(a) A chain with nodes available for additions to a queue;
(b) the chain after one addition; (c) the chain after another addition
(a)
(b)
(c)
queueNode
queueNode
queueNode
Unused
node
Unused
node
Unused
node
freeNode
The new entry
is in this node
The new entry
is in this node
freeNode
freeNode
The following implementation of
enqueue
is an O(1) operation:
public void
enqueue(T newEntry)
{
freeNode.setData(newEntry);
if
(isChainFull())
{
// allocate a new node and insert it after the node that
// freeNode references
Node newNode =
new
Node(
null
, freeNode.getNextNode());
freeNode.setNextNode(newNode);
}
// end if
freeNode = freeNode.getNextNode();
}
// end enqueue
Question 6
Adding an entry to the queue pictured in Figure 11-16c requires the creation
of a new node. Where in the chain would you insert the new node? Which node would con-
tain the new entry?
11.29
Retrieving the front.
If the queue is not empty,
queueNode
references its front node. The method
getFront
is therefore straightforward:
public
T getFront()
{
T front =
null
;
if
(!isEmpty())
front = queueNode.getData();
return
front;
}
// end getFront
This method is O(1).
