ISC Practicals and Theory - Stack (Array) (OOP)

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 OOP version: the capacity is passed to a parameterised constructor, push returns a boolean and pop returns the removed element, and main prints the 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 new Stack(c). The parameterised constructor 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). If it returns true, print that v was pushed; if false, print the overflow message.
   • Choice 2: if obj.isEmpty() is true, print the underflow message; otherwise call obj.pop(), store the returned element in x and print that x was popped.
   • Choice 3: if obj.isEmpty() is true, print that the stack is empty; otherwise 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 (boolean push(int v)):
   • If isFull() is true (top == cap - 1), return false.
   • Otherwise increase top by 1, store v in st[top] and return true.
5. Pop (int pop()):
   • If isEmpty() is true (top == -1), return -1.
   • Otherwise copy st[top] into v, decrease top by 1 and return v.
6. Display (display()): 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 and pop return their results, display prints the elements and main runs the menu and prints the messages.

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)

    // Parameterised constructor: creates the array and marks the stack empty
    // Parameter c: the capacity of the stack
    Stack(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
    // Parameter v: the element to be pushed
    // Returns true if the push was done, false if the stack is full (overflow)
    boolean push(int v)
    {
        if (isFull())
        {
            return false;
        }
        top++;           // move top up by one place
        st[top] = v;     // store the element at the new top
        return true;
    }

    // Removes the top element and returns it
    // Returns -1 if the stack is empty (underflow); the caller checks isEmpty() first
    int pop()
    {
        if (isEmpty())
        {
            return -1;   // sentinel value for underflow
        }
        int v = st[top]; // element being removed
        top--;           // move top down by one place
        return v;
    }

    // Displays the elements from the top to the bottom of the stack
    void display()
    {
        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(c);   // capacity passed to the parameterised constructor
        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
                    if (obj.push(v))
                    {
                        System.out.println(v + " pushed");
                    }
                    else
                    {
                        System.out.println("Stack Overflow! Cannot push " + v);
                    }
                    break;
                case 2:
                    if (obj.isEmpty())
                    {
                        System.out.println("Stack Underflow! The stack is empty");
                    }
                    else
                    {
                        int x = obj.pop();  // element removed from the stack
                        System.out.println(x + " popped");
                    }
                    break;
                case 3:
                    if (obj.isEmpty())
                    {
                        System.out.println("The stack is empty");
                    }
                    else
                    {
                        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): 25
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 is stopped by isEmpty() in main, which prints the underflow message, and the third push finds top == 1 == cap - 1, so push returns false and main 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."