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

S

top

Figure 4-3. Empty stack

The method push simply adds an item at the head of the stack and can be written as follows:

public void push(int n) {
Node p = new Node(n);
p.next = top;
top = p;
} //end push

After 36 , 15 , 52 , and 23 (in that order) have been pushed onto a stack, S , we can picture it as shown in Figure 4-4 .
S is a pointer to top , which is a pointer to the linked list of stack elements.

S

top

23 52 15 36

Figure 4-4. Stack view after pushing 36, 15, 52, and 23

To pop an item from the stack, we first check whether the stack is empty. If it is, a rogue value is returned. If not,
the item at the head of the list is returned, and the node containing the item is deleted from the list. Here is pop :

public int pop() {
if (this.empty()) return RogueValue; //a symbolic constant
int hold = top.data;
top = top.next;
return hold;
} //end pop

We rewrite Program P4.1 as Program P4.2. The class StackTest remains the same as before, but the class Stack
uses our new definitions of empty , push , and pop . We emphasize again that even though our implementation of the
stack has changed from using an array to using a linked list, the code that uses the stack ( main ) remains the same.

Program P4.2

import java.util.*;
public class StackTest {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
Stack S = new Stack();
System.out.printf("Enter some integers ending with 0\n");
int n = in.nextInt();