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

element stores the item and next stores a reference to the next ListNode in the
linked list. We provide constructors for ListNode that can be used to execute
both

ListNode<AnyType> p1 = new ListNode<AnyType>( x );

and

ListNode<AnyType> p2 = new ListNode<AnyType>( x, ptr2 );

One option is to nest ListNode in the Stack class. We use the slightly inferior
alternative of making it a top-level class that is only package-visible, thus
enabling reuse of the class for the queue implementation. The stack itself is
represented by a single data member, topOfStack , which is a reference to the
first ListNode in the linked list.
The constructor is not explicitly written, since by default we obtain an
empty stack by setting topOfStack to NULL . makeEmpty and isEmpty are thus triv-
ial and are shown at lines 19-22.

The ListNode dec-
laration is package-
visible but can be
used by the queue
implementation in
the same package.

Two routines are shown in Figure 16.20. The push operation is essentially
one line of code, in which we allocate a new ListNode whose data member con-
tains the item x to be pushed. The next reference for this new node is the original
topOfStack . This node then becomes the new topOfStack . We do all this at line 7.
The pop operation also is simple. After the obligatory test for emptiness,
we reset topOfStack to the second node in the list.

The stack routines
are essentially one-
liners.

1 /**
2 * Insert a new item into the stack.
3 * @param x the item to insert.
4 */
5 public void push( AnyType x )
6 {
7 topOfStack = new ListNode<AnyType>( x, topOfStack );
8 }
9
10 /**
11 * Remove the most recently inserted item from the stack.
12 * @throws UnderflowException if the stack is empty.
13 */
14 public void pop( )
15 {
16 if( isEmpty( ) )
17 throw new UnderflowException( "ListStack pop" );
18 topOfStack = topOfStack.next;
19 }

figure 16.20
The push and pop
routines for the
ListStack class