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