Stack

A stack is a linear data structure that follows the LIFO principle — Last In, First Out. The only element you're ever allowed to touch is the one that was added most recently, sitting on "top" of the stack. Think of a stack of plates: you place new plates on top, and you take plates off the top too. You'd never pull one from the middle without disturbing everything above it. This one restriction is what makes stacks so useful — undo history, function call stacks, expression evaluation, and backtracking algorithms all rely on exactly this "reverse the order you added things" behavior.

Core Operations

Array-Based Stack Implementation

The most direct implementation backs the stack with a plain array and tracks a single top index. Pushing means incrementing top and writing into that slot; popping means reading that slot and decrementing. No shifting of other elements is ever needed, which is exactly why every operation is O(1).

public class ArrayStack {
    private int[] data;
    private int top;       // index of the top element; -1 means empty
    private int capacity;

    public ArrayStack(int capacity) {
        this.capacity = capacity;
        this.data = new int[capacity];
        this.top = -1;
    }

    public void push(int value) {
        if (top == capacity - 1) {
            throw new RuntimeException("Stack overflow");
        }
        data[++top] = value;
    }

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack underflow");
        }
        return data[top--];
    }

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return data[top];
    }

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

Time complexity: O(1) for push, pop, peek, and isEmpty — each touches only the top index, never scans the array. Space complexity: O(n) — the backing array holds up to capacity elements.

Linked-List-Based Stack Implementation

A singly linked list is an equally natural fit: keep a reference to the head node and treat it as the top of the stack. Pushing means creating a new node that points at the current head and making it the new head; popping means reading the head's value and moving the head pointer to head.next. No resizing concerns at all, at the cost of one object allocation per push.

public class LinkedStack {
    private static class Node {
        int value;
        Node next;
        Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

    private Node top;    // head of the list doubles as the top of the stack
    private int size;

    public void push(int value) {
        top = new Node(value, top);
        size++;
    }

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack underflow");
        }
        int value = top.value;
        top = top.next;
        size--;
        return value;
    }

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return top.value;
    }

    public boolean isEmpty() {
        return top == null;
    }
}

Time complexity: O(1) for push, pop, peek, and isEmpty — every operation only reads or rewrites the head pointer. Space complexity: O(n) for n elements, plus a small per-node overhead for the next reference that the array version doesn't pay.

Java's Deque: The Recommended Stack

Java ships a legacy java.util.Stack class, but you should avoid it in new code. It extends Vector, which means every method is synchronized — you pay a locking cost even in single-threaded code — and it also exposes Vector's index-based methods, which don't respect LIFO discipline at all. The Deque interface, typically backed by ArrayDeque, is the modern, officially recommended replacement for stack usage.

Deque<Integer> stack = new ArrayDeque<>();

stack.push(10);
stack.push(20);
stack.push(30);

System.out.println(stack.peek());  // 30 — last one in
System.out.println(stack.pop());   // 30
System.out.println(stack.pop());   // 20
System.out.println(stack.isEmpty()); // false — 10 remains

Time complexity: O(1) amortized for push, pop, and peek — ArrayDeque is backed by a resizable circular array, so occasional resizing is spread across many calls. Space complexity: O(n) for n elements.

Worked Problem: Balanced Parentheses Checker

A classic use of a stack: given a string containing (){}[], determine whether every opening bracket has a matching closing bracket in the correct order. The idea — push every opening bracket you see. When you hit a closing bracket, it must match whatever is currently on top of the stack; if it doesn't (or the stack is empty), the string is unbalanced. At the end, the stack must be empty too — otherwise some opening bracket was never closed.

public static boolean isBalanced(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');

    for (char ch : s.toCharArray()) {
        if (ch == '(' || ch == '[' || ch == '{') {
            stack.push(ch);                       // opening bracket — remember it
        } else if (pairs.containsKey(ch)) {
            if (stack.isEmpty() || stack.pop() != pairs.get(ch)) {
                return false;                    // mismatch or nothing to match against
            }
        }
    }
    return stack.isEmpty();                       // every opener must have been closed
}

Trace on "{[()]}": push {, push [, push (. Next char is ) — pop gives (, which matches. Next is ] — pop gives [, matches. Next is } — pop gives {, matches. Stack is empty at the end, so the string is balanced.

Time complexity: O(n) — one pass over the string, each character pushed or popped at most once. Space complexity: O(n) worst case — a string of all opening brackets pushes every character onto the stack before the loop ends.