Java Reference
In-Depth Information
11.21
Removing the front entry.
We can retrieve and remove the entry at the front of the queue by using
Vector
's method
remove
with an argument of zero. This method returns the removed entry, which
is just what
dequeue
needs to do:
public
T dequeue()
{
T front =
null
;
if
(!isEmpty())
front = queue.remove(0);
return
front;
}
// end dequeue
11.22
The rest of the class.
The remaining public methods
isEmpty
and
clear
invoke analogous
Vector
methods:
public boolean
isEmpty()
{
return
queue.isEmpty();
}
// end isEmpty
public void
clear()
{
queue.clear();
}
// end clear
11.23
Efficiency.
The implementation of
Vector
is based on an array that expands dynamically, but not
one that is circular. Since we add entries to one end of a queue and remove them from the other
end, the vector implementation inherently moves its entries after each removal. Thus,
dequeue
is
O(
n
), while the other operations are O(1). However, expanding the vector degrades the perfor-
mance of
enqueue
. The efficiency of this implementation is not as good as that of the one that
uses a circular array.
11.24
Figure 11-1 in Segment 11.1 shows a chain of linked nodes that implements the ADT queue. This
chain has two external references—one to the first node and one to the last node in the chain. Recall
that these references are particularly useful for a queue implementation, since a queue's operations
affect both of its ends. Like the chains you have seen before, the last node in this chain contains
null
. Such chains are sometimes called
linear linked chains
,
regardless of whether they have a tail
reference in addition to a head reference.
In a
circular linked chain
, the last node references the first node, so no node contains
null
in its
next
field. Despite the fact that each node references the next node, a circular linked chain
has a beginning and an end. We could have an external reference to the chain's first node, but
then a traversal of the chain would be necessary to locate the last node. Having both a reference
to the first node and a reference to the last node is usually more than is necessary. Since the
chain's last node references its first node, we can have a solitary reference to the last node and
still locate the first node quickly. Figure 11-12 illustrates such a chain.
When a class uses a circular linked chain to represent a queue, its only data field is the refer-
ence
lastNode
to the chain's last node. The implementation therefore does not have the overhead
of maintaining a data field that references the first node. Any time such a reference is needed, the
expression
lastNode.getNextNode()
provides it. Despite this simplification, this approach is not
necessarily better than the one used in the first section of this chapter. It is mostly just different, as
you will see if you complete Project 4 at the end of this chapter.
We now investigate another way to use a circular linked chain to represent a queue.
VideoNote
Other queue implementations
