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

We begin our definition of the class Stack as follows:

public class Stack {
final static int MaxStack = 100;
int top = -1;
int[] ST = new int[MaxStack];
//the rest of the class goes here
} //end class Stack

Valid values for top will range from 0 to MaxStack-1 . When we initialize a stack, we will set top to the invalid
subscript -1 .
We can now declare a stack variable, S , with this statement:

Stack S = new Stack();

When this statement is executed, the situation in memory can be represented by that shown in Figure 4-1 .

S

-1

top

ST

0 1 2 3 4 5

Figure 4-1. Array representation of stack in memory

This represents an empty stack. We will need a function that tells us whether a stack is empty. We can add the
following instance method to the Stack class:

public boolean empty() {
return top == -1;
}

This simply checks whether top has the value -1 .
The major operations on a stack are push and pop . To push an item, n , onto a stack, we must store it in ST and
update top to point to it. The basic idea is as follows:

add 1 to top
set ST[top] to n

However, we must guard against trying to add something to the stack when it is already full. The stack is full when
top has the value MaxStack - 1 , the subscript of the last element. In this case, we will report that the stack is full and
halt the program. Here is the instance method, push , in the Stack class: