Stack Data Structure Explained — How It Works, Why It Exists, and When to Use It

package io.thecodeforge.ds;

import java.util.ArrayDeque;
import java.util.Deque;

public class StackConceptDemo {
    public static void main(String[] args) {

        // Think of this as a physical stack of plates
        Deque<String> browserHistory = new ArrayDeque<>();

        // PUSH — visiting pages, each one goes on top
        browserHistory.push("google.com");     // bottom of the stack
        browserHistory.push("wikipedia.org");  // sits on top of google
        browserHistory.push("java-docs.com");  // sits on top of wikipedia

        System.out.println("Current page (top of stack): " + browserHistory.peek());
        // peek() reads the top item WITHOUT removing it

        System.out.println("\n--- Hitting the back button 3 times ---");

        // POP — removes and returns the top item each time
        System.out.println("Back: " + browserHistory.pop()); // java-docs.com leaves first
        System.out.println("Back: " + browserHistory.pop()); // wikipedia.org leaves next
        System.out.println("Back: " + browserHistory.pop()); // google.com leaves last

        // Stack is now empty — checking before popping prevents a crash
        System.out.println("\nIs history empty? " + browserHistory.isEmpty());
    }
}

package io.thecodeforge.ds;

/**
 * Array-backed stack with explicit overflow/underflow handling.
 * Demonstrates the internal mechanics that java.util.Stack hides.
 */
public class CustomStack {

    private final int[] elements;  // The underlying array that holds our data
    private int topIndex;          // Points to the index of the current top element
    private final int capacity;    // Maximum number of elements this stack can hold

    // Constructor — sets up an empty stack with a fixed maximum size
    public CustomStack(int capacity) {
        if (capacity <= 0) {
            throw new IllegalArgumentException("Capacity must be positive, got: " + capacity);
        }
        this.capacity = capacity;
        this.elements = new int[capacity];
        this.topIndex = -1;  // -1 means the stack is empty (no valid index yet)
    }

    // PUSH — adds a new value on top of the stack
    public void push(int value) {
        if (topIndex == capacity - 1) {
            // topIndex has reached the last array index — no more room
            throw new RuntimeException("Stack Overflow: stack is full, cannot push " + value);
        }
        topIndex++;                    // Move the pointer up one slot
        elements[topIndex] = value;    // Place the value in that slot
        System.out.println("Pushed: " + value + "  (topIndex is now " + topIndex + ")");
    }

    // POP — removes and returns the top value
    public int pop() {
        if (topIndex == -1) {
            // topIndex is -1, meaning there's nothing to remove
            throw new RuntimeException("Stack Underflow: stack is empty, nothing to pop");
        }
        int removedValue = elements[topIndex];  // Grab the top value before we move the pointer
        topIndex--;                              // Move the pointer down — the old slot is now 'forgotten'
        System.out.println("Popped: " + removedValue + "  (topIndex is now " + topIndex + ")");
        return removedValue;
    }

    // PEEK — returns the top value WITHOUT removing it
    public int peek() {
        if (topIndex == -1) {
            throw new RuntimeException("Stack is empty, nothing to peek at");
        }
        return elements[topIndex];  // Just read it — don't touch topIndex
    }

    // isEmpty — returns true if the stack has no elements
    public boolean isEmpty() {
        return topIndex == -1;
    }

    // size — returns how many elements are currently in the stack
    public int size() {
        return topIndex + 1;  // topIndex is zero-based, so size is always one more
    }

    // --- DEMO ---
    public static void main(String[] args) {
        CustomStack stack = new CustomStack(5);  // A stack that fits 5 integers

        System.out.println("=== Pushing three values ===");
        stack.push(10);
        stack.push(25);
        stack.push(47);

        System.out.println("\nTop element right now: " + stack.peek());
        System.out.println("Stack size: " + stack.size());

        System.out.println("\n=== Popping all values ===");
        stack.pop();
        stack.pop();
        stack.pop();

        System.out.println("\nIs the stack empty? " + stack.isEmpty());

        // Uncomment this to see the underflow exception in action:
        // stack.pop();
    }
}

package io.thecodeforge.ds;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * Validates balanced brackets using a stack.
 * Used in compilers, JSON parsers, HTML validators, and IDEs.
 */
public class BracketBalanceChecker {

    public static boolean isBalanced(String expression) {
        Deque<Character> openBrackets = new ArrayDeque<>();

        for (int i = 0; i < expression.length(); i++) {
            char currentChar = expression.charAt(i);

            // If it's an opening bracket, push it — we'll need to match it later
            if (currentChar == '(' || currentChar == '[' || currentChar == '{') {
                openBrackets.push(currentChar);
            }

            // If it's a closing bracket, check whether it matches the last opener
            else if (currentChar == ')' || currentChar == ']' || currentChar == '}') {

                // A closing bracket with nothing to match it — immediately invalid
                if (openBrackets.isEmpty()) {
                    return false;
                }

                char lastOpener = openBrackets.pop();  // Grab and remove the most recent opener

                // Check for a mismatch — the wrong type of closing bracket appeared
                if (currentChar == ')' && lastOpener != '(') return false;
                if (currentChar == ']' && lastOpener != '[') return false;
                if (currentChar == '}' && lastOpener != '{') return false;
            }
            // Any other character (letters, digits, operators) — just skip it
        }

        // If the stack is empty, every opener was matched correctly
        // If the stack still has items, some openers were never closed
        return openBrackets.isEmpty();
    }

    public static void main(String[] args) {
        String[] testCases = {
            "{[()]}",      // balanced — all pairs match correctly
            "{[(])}",      // NOT balanced — ] closes before )
            "(((",         // NOT balanced — three openers, no closers
            "",            // empty string — trivially balanced
            "[{()}]()",   // balanced — multiple groups, all correct
            "}{",          // NOT balanced — closer appears before opener
        };

        for (String expression : testCases) {
            String result = isBalanced(expression) ? "BALANCED" : "NOT BALANCED";
            System.out.printf("%-20s -> %s%n", "\"".concat(expression).concat("\""), result);
        }
    }
}

package io.thecodeforge.ds;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

public class StackVsDequeDemo {

    public static void main(String[] args) {

        // --- Using the legacy java.util.Stack ---
        System.out.println("=== java.util.Stack ===");
        Stack<Integer> legacyStack = new Stack<>();
        legacyStack.push(100);
        legacyStack.push(200);
        legacyStack.push(300);
        System.out.println("Top (peek): " + legacyStack.peek());   // 300
        System.out.println("Popped: "   + legacyStack.pop());      // 300
        System.out.println("Size: "     + legacyStack.size());     // 2

        // --- Using the recommended ArrayDeque as a stack ---
        // Declare as Deque<Integer> — this is the interface, not the implementation
        System.out.println("\n=== ArrayDeque (recommended) ===");
        Deque<Integer> modernStack = new ArrayDeque<>();
        modernStack.push(100);  // push() adds to the FRONT of the deque — mimicking a stack top
        modernStack.push(200);
        modernStack.push(300);
        System.out.println("Top (peek): " + modernStack.peek());   // 300
        System.out.println("Popped: "    + modernStack.pop());     // 300
        System.out.println("Size: "      + modernStack.size());    // 2

        // Performance test — pushing 1 million integers
        System.out.println("\n=== Performance Comparison ===");
        int iterations = 1_000_000;

        long legacyStart = System.currentTimeMillis();
        Stack<Integer> perfLegacy = new Stack<>();
        for (int i = 0; i < iterations; i++) {
            perfLegacy.push(i);
        }
        long legacyTime = System.currentTimeMillis() - legacyStart;

        long modernStart = System.currentTimeMillis();
        Deque<Integer> perfModern = new ArrayDeque<>();
        for (int i = 0; i < iterations; i++) {
            perfModern.push(i);
        }
        long modernTime = System.currentTimeMillis() - modernStart;

        System.out.println("Stack (1M pushes):     " + legacyTime + "ms");
        System.out.println("ArrayDeque (1M pushes): " + modernTime + "ms");
        System.out.println("ArrayDeque is faster because it avoids synchronization overhead.");
    }
}