Stacks and Queues - Advanced Topics in Java: Core Concepts in Data Structures - page 114

The following shows a sample run of Program P4.1:
Enter some integers ending with 0
1 2 3 4 5 6 7 8 9 0
Numbers in reverse order
9 8 7 6 5 4 3 2 1
It is important to observe that the code in main that uses the stack does so via the functions push , pop , and empty
and makes no assumption about how the stack elements are stored. This is the hallmark of an abstract data type—it
can be used without the user needing to know how it is implemented.
Next, we will implement the stack using a linked list, but main will remain the same for solving the problem of
printing the numbers in reverse order.
4.2.2 Implementing a Stack Using a Linked List
The array implementation of a stack has the advantages of simplicity and efficiency. However, one major disadvantage
is the need to know what size to declare the array. Some reasonable guess has to be made, but this may turn out to be
too small (and the program has to halt) or too big (and storage is wasted).
To overcome this disadvantage, a linked list can be used. Now, we will allocate storage for an element only when
it is needed.
The stack is implemented as a linked list with new items added at the head of the list. When we need to pop the
stack, the item at the head is removed.
Again, we illustrate the principles using a stack of integers. First, we will need to define a Node class that will be
used to create nodes for the list. We will use the following declarations:
class Node {
int data;
Node next;
public Node(int d) {
data = d;
next = null;
}
} //end class Node
Next, we will write the class, Stack , which begins as follows:
class Stack {
Node top = null;
public boolean empty() {
return top == null;
}
...
There is one instance variable— top of type Node . It is initialized to null to denote the empty stack. The function
empty simply checks whether top is null . The empty stack, S , is depicted as in Figure 4-3 .