Stacks and queues - Data Structures and Problem Solving Using Java - page 609

1 /**
2 * Get the most recently inserted item in the stack.
3 * Does not alter the stack.
4 * @return the most recently inserted item in the stack.
5 * @throws UnderflowException if the stack is empty.
6 */
7 public AnyType top( )
8 {
9 if( isEmpty( ) )
10 throw new UnderflowException( "ListStack top" );
11 return topOfStack.element;
12 }
13
14 /**
15 * Return and remove the most recently inserted item
16 * from the stack.
17 * @return the most recently inserted item in the stack.
18 * @throws UnderflowException if the stack is empty.
19 */
20 public AnyType topAndPop( )
21 {
22 if( isEmpty( ) )
23 throw new UnderflowException( "ListStack topAndPop" );
24
25 AnyType topItem = topOfStack.element;
26 topOfStack = topOfStack.next;
27 return topItem;
28 }

figure 16.21
The top and topAndPop
routines for the
ListStack class

Finally, top and topAndPop are straightforward routines and are imple-
mented as shown in Figure 16.21.

A linked list in which
we maintain a refer-
ence to the first and
last item can be
used to implement
the queue in con-
stant time per
operation.

16.2.2 queues

The queue can be implemented by a linked list, provided we keep references
to both the front and back of the list. Figure 16.22 shows the general idea.

figure 16.22
Linked list
implementation of the
queue class

front back

A B C D