ISC Practicals and Theory - Stack (Array)

A stack is a linear data structure in which elements are added and removed at one end only, called the top, so the element pushed last is the first to be popped. This note implements a stack of integers using an array, with a menu to push, pop and display. This is the Classic version: a default constructor, an init method that sets the capacity, and methods that print their own messages.

Definition

A stack follows the LIFO (Last In, First Out) rule. The two basic operations are:

• Push: add an element on the top of the stack.
• Pop: remove the element on the top of the stack.

When the stack is implemented with an array, an integer top holds the index of the topmost element. In this program top = -1 means that the stack is empty, and top = cap - 1 means that it is full.

• Overflow: trying to push when the stack is full (top == cap - 1).
• Underflow: trying to pop when the stack is empty (top == -1).

For example, if 10, 20 and 30 are pushed in that order into a stack of capacity 3, the stack is full with top = 2. The first pop removes 30, then 20, then 10.

Algorithm

1. In main, read the capacity c. If it is less than 1 or more than 20, print an error message and stop.
2. Create the object obj with the default constructor Stack() (it sets cap = 0 and top = -1), then call obj.init(c), which sets cap, creates the array st of size cap and sets top = -1.
3. Repeat the menu (1 Push, 2 Pop, 3 Display, 4 Exit) and read choice until choice is 4:
   • Choice 1: read the element v and call obj.push(v).
   • Choice 2: call obj.pop().
   • Choice 3: call obj.display().
   • Choice 4: print a message and leave the loop.
   • Any other value: print an invalid choice message and show the menu again.
4. Push (push(int v)):
   • If isFull() is true (top == cap - 1), print the overflow message.
   • Otherwise increase top by 1, store v in st[top] and print that it was pushed.
5. Pop (pop()):
   • If isEmpty() is true (top == -1), print the underflow message.
   • Otherwise copy st[top] into v, decrease top by 1 and print that v was popped.
6. Display (display()):
   • If the stack is empty, print that it is empty.
   • Otherwise run i from top down to 0 and print st[i], so the top element is printed first.

A popped value is not erased from the array. It stays in the old position but lies above top, so it is ignored and is overwritten by the next push.

Program

isEmpty and isFull test the two end conditions, push, pop and display carry out the operations and print their messages, and main runs the menu.

import java.util.Scanner;

// Class Stack: implements a stack of integers using an array
public class Stack
{
    int st[];     // array that stores the stack elements
    int cap;      // capacity: maximum number of elements the stack can hold
    int top;      // index of the topmost element (-1 when the stack is empty)

    // Default constructor: no array yet, the stack is marked empty
    Stack()
    {
        cap = 0;
        top = -1;
    }

    // Sets the capacity, creates the array and marks the stack empty
    // Parameter c: the capacity entered by the user
    void init(int c)
    {
        cap = c;
        st = new int[cap];
        top = -1;
    }

    // Returns true if the stack has no element
    boolean isEmpty()
    {
        return top == -1;
    }

    // Returns true if the stack is full (top is at the last index)
    boolean isFull()
    {
        return top == cap - 1;
    }

    // Pushes the value v on the top of the stack; prints a message on overflow
    // Parameter v: the element to be pushed
    void push(int v)
    {
        if (isFull())
        {
            System.out.println("Stack Overflow! Cannot push " + v);
        }
        else
        {
            top++;           // move top up by one place
            st[top] = v;     // store the element at the new top
            System.out.println(v + " pushed");
        }
    }

    // Removes the top element and prints it; prints a message on underflow
    void pop()
    {
        if (isEmpty())
        {
            System.out.println("Stack Underflow! The stack is empty");
        }
        else
        {
            int v = st[top]; // element being removed
            top--;           // move top down by one place
            System.out.println(v + " popped");
        }
    }

    // Displays the elements from the top to the bottom of the stack
    void display()
    {
        if (isEmpty())
        {
            System.out.println("The stack is empty");
        }
        else
        {
            System.out.println("Stack (top to bottom):");
            for (int i = top; i >= 0; i--)
            {
                System.out.println(st[i]);
            }
        }
    }

    // main: reads the capacity, then runs the menu until the user chooses 4
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);   // single Scanner used for all input
        System.out.print("Enter the capacity of the stack (1 to 20): ");
        int c = sc.nextInt();
        if (c < 1 || c > 20)
        {
            System.out.println("Invalid capacity. It must be from 1 to 20.");
            return;
        }
        Stack obj = new Stack();   // object created with the default constructor
        obj.init(c);               // capacity is set by init
        int choice;                // menu choice entered by the user
        do
        {
            System.out.println();
            System.out.println("1. Push");
            System.out.println("2. Pop");
            System.out.println("3. Display");
            System.out.println("4. Exit");
            System.out.print("Enter your choice: ");
            choice = sc.nextInt();
            switch (choice)
            {
                case 1:
                    System.out.print("Enter the element to push: ");
                    int v = sc.nextInt();   // element to be pushed
                    obj.push(v);
                    break;
                case 2:
                    obj.pop();
                    break;
                case 3:
                    obj.display();
                    break;
                case 4:
                    System.out.println("Exiting the program");
                    break;
                default:
                    System.out.println("Invalid choice. Enter a number from 1 to 4.");
            }
        } while (choice != 4);
    }
}

Variable description table

Sample input and output

Enter the capacity of the stack (1 to 20): 3

1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 1
Enter the element to push: 10
10 pushed

1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 1
Enter the element to push: 20
20 pushed

1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 1
Enter the element to push: 30
30 pushed

1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 3
Stack (top to bottom):
30
20
10

1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 2
30 popped

1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 2
20 popped

1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 3
Stack (top to bottom):
10

1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 4
Exiting the program

Enter the capacity of the stack (1 to 20): 2

1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 2
Stack Underflow! The stack is empty

1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 3
The stack is empty

1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 1
Enter the element to push: 5
5 pushed

1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 1
Enter the element to push: 6
6 pushed

1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 1
Enter the element to push: 7
Stack Overflow! Cannot push 7

1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 3
Stack (top to bottom):
6
5

1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 9
Invalid choice. Enter a number from 1 to 4.

1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 4
Exiting the program

Enter the capacity of the stack (1 to 20): 0
Invalid capacity. It must be from 1 to 20.

Dry run

Take the first sample: capacity 3, then push 10, push 20, push 30, display, pop, pop, display, exit. Unused places are shown as _. A place above top still holds an old value after a pop, but it is ignored, so it is shown as _ here.

The stack finally holds only 10, which matches the last display in the first sample run. In the second sample (capacity 2) the first pop finds top == -1 and prints the underflow message, and the third push finds top == 1 == cap - 1 and prints the overflow message.

Variations

1. Stack of characters or strings "Write a program to implement a stack of characters (or names) using an array."
2. Peek operation "Add a method to display the top element of the stack without removing it."
3. Reverse a string using a stack "Push the characters of a word on a stack and pop them to print the word reversed."
4. Infix to postfix conversion "Convert an infix expression to postfix using a stack of operators."