Java Reference
In-Depth Information
Figure 16.25 implements both
enqueue
and
dequeue
. The
dequeue
routine is
logically identical to a stack
pop
(actually
popAndTop
)
. The
enqueue
routine has
two cases. If the queue is empty, we create a one-element queue by calling
new
and having both
front
and
back
reference the single node. Otherwise, we create a
new node with data value
x
, attach it at the end of the list, and then reset the end of
the list to this new node, as illustrated in Figure 16.26. Note that enqueueing the
first element is a special case because there is no
next
reference to which a new
node can be attached. We do all this at line 10 in Figure 16.25.
The remaining methods for the
ListQueue
class are identical to the corre-
sponding
ListStack
routines. They are shown in Figure 16.27.
Enqueueing the
first element is a
special case
because there is no
next
reference to
which a new node
can be attached.
1
/**
2
* Insert a new item into the queue.
3
* @param x the item to insert.
4
*/
5
public void enqueue( AnyType x )
6
{
7
if( isEmpty( ) ) // Make a queue of one element
8
back = front = new ListNode<AnyType>( x );
9
else // Regular case
10
back = back.next = new ListNode<AnyType>( x );
11
}
12
13
/**
14
* Return and remove the least recently inserted item
15
* from the queue.
16
* @return the least recently inserted item in the queue.
17
* @throws UnderflowException if the queue is empty.
18
*/
19
public AnyType dequeue( )
20
{
21
if( isEmpty( ) )
22
throw new UnderflowException( "ListQueue dequeue" );
23
24
AnyType returnValue = front.element;
25
front = front.next;
26
return returnValue;
27
}
figure 16.25
The
enqueue
and
dequeue
routines for
the
ListQueue
class
Search WWH ::
Custom Search