Learn Stack Data Structure with a Simple Java Program

Introduction

Are you a high school student looking to master data structures in Java? One of the fundamental structures in computer science is a stack, which follows the Last In, First Out (LIFO) principle. In this blog, we will implement a stack using arrays in Java, understand its algorithm, and analyze its time and space complexity.

If you’re looking for a computer science tutor to help you with Java programming, do not hesitate to contact us!

What Is a Stack in Java?

A stack is a linear data structure that allows elements to be added and removed only from the top. It has two main operations:

1. Push – Add an element to the top of the stack.
2. Pop – Remove and return the top element from the stack.

Stacks are used in function calls, recursion, undo/redo operations, and expression evaluation.

Algorithm to Implement a Stack Using an Array

To implement a stack using an array, we need:

• A fixed-size array to store stack elements.
• A top pointer to track the last inserted element.
• Functions to perform push, pop, peek, and isEmpty operations.

Steps to Implement:

1. Initialize an empty array with a fixed size.
2. Define a variable top, which points to the top of the stack. Initially, set top = -1 (indicating an empty stack).
3. Push Operation:
   • Check if the stack is full (top == size - 1).
   • If not, increase top and insert the new element at stack[top].
4. Pop Operation:
   • Check if the stack is empty (top == -1).
   • If not, return the element at stack[top] and decrease top.
5. Peek Operation: Return the element at stack[top] without removing it.
6. isEmpty Operation: Check if top == -1.

class Stack {
    private int[] stackArray; // Array to store stack elements
    private int top; // Pointer to the top element
    private int size; // Maximum stack size

    // Constructor
    public Stack(int size) {
        this.size = size;
        stackArray = new int[size];
        top = -1; // Stack is initially empty
    }

    // Push operation
    public void push(int value) {
        if (top == size - 1) {
            System.out.println("Stack Overflow! Cannot push " + value);
            return;
        }
        stackArray[++top] = value;
        System.out.println("Pushed: " + value);
    }

    // Pop operation
    public int pop() {
        if (top == -1) {
            System.out.println("Stack Underflow! No elements to pop.");
            return -1;
        }
        return stackArray[top--];
    }

    // Peek operation
    public int peek() {
        if (top == -1) {
            System.out.println("Stack is empty!");
            return -1;
        }
        return stackArray[top];
    }

    // Check if stack is empty
    public boolean isEmpty() {
        return top == -1;
    }

    // Main method to test the Stack implementation
    public static void main(String[] args) {
        Stack stack = new Stack(5);
        
        stack.push(10);
        stack.push(20);
        stack.push(30);
        
        System.out.println("Top element: " + stack.peek()); // Should print 30
        
        System.out.println("Popped element: " + stack.pop()); // Should print 30
        
        System.out.println("Is stack empty? " + stack.isEmpty()); // Should print false
    }
}

Time and Space Complexity Analysis

Understanding the efficiency of our stack implementation is essential in computer science tutoring.

Space Complexity:

• O(N) where N is the maximum size of the stack (as we allocate an array of size N).