Stacks

A stack is an array or linked list with a restriction: you can only add and remove elements from one end. That restriction — Last In, First Out (LIFO) — sounds limiting until you realize how many problems it unlocks. Expression parsing, undo systems, function call management, depth-first traversal, and an entire family of “next greater element” problems all collapse into clean implementations once you reach for a stack.

Interviewers use stack problems to test whether you can identify hidden LIFO patterns in problems that do not explicitly mention stacks. The balanced parentheses problem is the warm-up. Monotonic stacks and expression evaluation are where candidates differentiate themselves.

LIFO Semantics: Push, Pop, Peek

A stack supports three core operations:

Operation	Description	Time
push(e)	Add element e to the top	O(1)
pop()	Remove and return the top element	O(1)
peek()	Return the top element without removing it	O(1)

All three operations are O(1). A stack promises nothing about accessing elements below the top — and that constraint is the source of its power. By limiting what you can do, a stack forces a processing order that solves specific problem categories with elegant efficiency.

Array-Based Stack Implementation

An array-based stack uses a dynamic array with a top index tracking the current stack height:

public class ArrayStack<T> {
    private Object[] data;
    private int top;

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

    public ArrayStack() {
        this(16);
    }

    public void push(T element) {
        if (top == data.length - 1) {
            resize(data.length + (data.length >> 1));
        }
        data[++top] = element;
    }

    @SuppressWarnings("unchecked")
    public T pop() {
        if (top == -1) throw new java.util.NoSuchElementException("Stack is empty");
        T element = (T) data[top];
        data[top--] = null; // Prevent memory leak
        return element;
    }

    @SuppressWarnings("unchecked")
    public T peek() {
        if (top == -1) throw new java.util.NoSuchElementException("Stack is empty");
        return (T) data[top];
    }

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

    public int size() {
        return top + 1;
    }

    private void resize(int newCapacity) {
        var newData = new Object[newCapacity];
        System.arraycopy(data, 0, newData, 0, top + 1);
        data = newData;
    }
}

Critical detail: Setting data[top] = null after popping prevents a subtle memory leak. Without it, the stack holds a reference to the popped object, preventing garbage collection even though the object is logically removed. This is one of the items Josh Bloch highlights in Effective Java and interviewers do ask about it.

Linked-List-Based Stack Implementation

A linked list stack pushes and pops at the head — no traversal needed:

public class LinkedStack<T> {
    private record Node<T>(T val, Node<T> next) {}

    private Node<T> top;
    private int size;

    public void push(T element) {
        top = new Node<>(element, top);
        size++;
    }

    public T pop() {
        if (top == null) throw new java.util.NoSuchElementException("Stack is empty");
        T val = top.val();
        top = top.next();
        size--;
        return val;
    }

    public T peek() {
        if (top == null) throw new java.util.NoSuchElementException("Stack is empty");
        return top.val();
    }

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

    public int size() {
        return size;
    }
}

Notice the use of a Java 25 record for the Node. Since each node is created once and never mutated, the record’s immutability is a perfect fit. The push operation creates a new record whose next field points to the previous top — a clean, functional-style operation.

Array vs. Linked List: Which to Use?

Array-based (use ArrayDeque in production):

• Better cache locality for sequential operations
• Lower memory overhead (no per-node object headers)
• Amortized O(1) push with occasional resize

Linked-list-based:

• Guaranteed O(1) push (no resize pauses)
• Each node is a separate heap allocation (higher GC pressure)
• Worse cache behavior

In interviews: Use ArrayDeque<T> as your stack. Tell the interviewer: “I use ArrayDeque instead of Stack because Stack extends Vector, which adds synchronization overhead and allows index-based access that violates stack semantics.” This single sentence demonstrates three things: you know the JDK, you understand performance, and you respect interface contracts.

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
int top = stack.pop(); // Returns 2

Classic Problem: Valid Parentheses

Problem: Given a string containing (, ), {, }, [, ], determine if the input string has valid (balanced and properly nested) brackets.

Examples:

• "({[]})" → true
• "([)]" → false
• "(((" → false

public boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();

    for (char c : s.toCharArray()) {
        switch (c) {
            case '(' -> stack.push(')');
            case '{' -> stack.push('}');
            case '[' -> stack.push(']');
            default -> {
                if (stack.isEmpty() || stack.pop() != c) {
                    return false;
                }
            }
        }
    }

    return stack.isEmpty();
}

The trick: Instead of pushing the opening bracket and then matching it later, push the expected closing bracket. When you encounter a closing bracket, pop the stack and check if it matches. This eliminates a mapping step and reads more cleanly.

Complexity: O(n) time, O(n) space in the worst case (all opening brackets).

Classic Problem: Min Stack — O(1) getMin

Problem: Design a stack that supports push, pop, peek, and retrieving the minimum element, all in O(1) time.

The challenge: when you pop the current minimum, you need the previous minimum instantly. An auxiliary stack tracks the minimum at each level:

public class MinStack {
    private record Entry(int val, int min) {}

    private final Deque<Entry> stack = new ArrayDeque<>();

    public void push(int val) {
        int newMin = stack.isEmpty() ? val : Math.min(val, stack.peek().min());
        stack.push(new Entry(val, newMin));
    }

    public void pop() {
        stack.pop();
    }

    public int top() {
        return stack.peek().val();
    }

    public int getMin() {
        return stack.peek().min();
    }
}

Each Entry record pairs a value with the minimum of all elements at that point in the stack’s history. When you pop, the minimum automatically reverts to the correct value because it was recorded when each element was pushed.

Alternative approach: Use two separate stacks — one for values and one for minimums. Push to the min stack only when the new value is ≤ the current minimum. Both approaches achieve O(1) for all operations.

Complexity: O(1) time for all operations, O(n) space total.

Classic Problem: Next Greater Element — Monotonic Stack

Problem: Given an array, for each element, find the next element that is greater than it. If no such element exists, the answer is -1.

Example: [4, 2, 6, 1, 3] → [6, 6, -1, 3, -1]

The brute force approach scans right from each element — O(n²). A monotonic stack solves this in O(n):

public int[] nextGreaterElement(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    java.util.Arrays.fill(result, -1);

    // Stack stores indices of elements waiting for their next greater element
    Deque<Integer> stack = new ArrayDeque<>();

    for (int i = 0; i < n; i++) {
        // While current element is greater than elements represented by stack top
        while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
            int idx = stack.pop();
            result[idx] = nums[i];
        }
        stack.push(i);
    }

    return result;
}

How the monotonic stack works: The stack maintains indices in decreasing order of their corresponding values. When you encounter a value greater than the stack’s top, that value is the “next greater element” for the top. You keep popping until the stack’s top represents a value ≥ the current value, then push the current index.

Each element is pushed once and popped once — total operations: 2n = O(n).

The monotonic stack pattern appears in many interview problems:

• Next Greater Element (I, II, III)
• Daily Temperatures
• Largest Rectangle in Histogram
• Trapping Rain Water (stack-based approach)

Whenever a problem asks “for each element, find the next/previous element satisfying a comparison condition,” reach for a monotonic stack.

Classic Problem: Evaluate Reverse Polish Notation

Problem: Evaluate an arithmetic expression in Reverse Polish Notation (postfix). Valid operators are +, -, *, /. Each operand is an integer.

Example: ["4", "13", "5", "/", "+"] → 4 + (13 / 5) = 6

Java 25’s sealed interfaces and pattern matching create an exceptionally clean solution:

public sealed interface Token {
    record Operand(int value) implements Token {}
    record Operator(String symbol) implements Token {}
}

public int evalRPN(String[] tokens) {
    Deque<Integer> stack = new ArrayDeque<>();

    for (String raw : tokens) {
        Token token = parseToken(raw);

        switch (token) {
            case Token.Operand(var value) -> stack.push(value);
            case Token.Operator(var symbol) -> {
                int right = stack.pop();
                int left = stack.pop();
                int result = applyOperator(symbol, left, right);
                stack.push(result);
            }
        }
    }

    return stack.pop();
}

private Token parseToken(String raw) {
    return switch (raw) {
        case "+", "-", "*", "/" -> new Token.Operator(raw);
        default -> new Token.Operand(Integer.parseInt(raw));
    };
}

private int applyOperator(String op, int left, int right) {
    return switch (op) {
        case "+" -> left + right;
        case "-" -> left - right;
        case "*" -> left * right;
        case "/" -> left / right; // Integer division truncates toward zero
        default -> throw new IllegalArgumentException("Unknown operator: " + op);
    };
}

Why sealed interfaces here? The Token sealed interface guarantees that every token is either an Operand or an Operator — no other variants exist. The compiler enforces exhaustive pattern matching in the switch expression. If you added a third variant later, every switch on Token would produce a compile error until updated. This is type safety that prevents runtime bugs.

Complexity: O(n) time, O(n) space where n is the number of tokens.

Classic Problem: Daily Temperatures

Problem: Given an array of daily temperatures, return an array where answer[i] is the number of days you have to wait after day i to get a warmer temperature. If no warmer day exists, answer[i] = 0.

Example: [73, 74, 75, 71, 69, 72, 76, 73] → [1, 1, 4, 2, 1, 1, 0, 0]

This is a direct application of the monotonic stack:

public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] answer = new int[n];

    Deque<Integer> stack = new ArrayDeque<>(); // Stores indices

    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int prevDay = stack.pop();
            answer[prevDay] = i - prevDay;
        }
        stack.push(i);
    }

    return answer;
}

The difference from “Next Greater Element” is that you store the distance (number of days) rather than the value. The stack mechanics are identical.

Complexity: O(n) time, O(n) space.

Call Stack and Recursion: The Hidden Stack

Every recursive function call pushes a frame onto the call stack — a stack managed by the runtime. Understanding this connection is vital for two reasons:

1. Any recursive algorithm can be converted to an iterative one using an explicit stack. When interviewers ask for an iterative DFS on a tree or graph, you replace the implicit call stack with a Deque<> and simulate the recursion manually.

2. Stack overflow risk. Java’s default thread stack size is typically 512KB–1MB. Each stack frame for a recursive call consumes space for local variables, parameters, and return addresses. A recursive function processing a linked list of 100,000 nodes can exhaust the stack. Iterative solutions using an explicit stack on the heap do not have this limitation.

// Recursive DFS — uses call stack
public void dfsRecursive(TreeNode node) {
    if (node == null) return;
    process(node);
    dfsRecursive(node.left);
    dfsRecursive(node.right);
}

// Iterative DFS — explicit stack on the heap
public void dfsIterative(TreeNode root) {
    if (root == null) return;

    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        var node = stack.pop();
        process(node);

        // Push right first so left is processed first (LIFO)
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
}

When an interviewer asks “Can you do this without recursion?” — the answer is always “Yes, with an explicit stack.” Demonstrate this conversion fluently.

Edge Cases and Interviewer Tips

Edge cases to check:

• Empty input — Empty string for parentheses, empty array for temperatures.
• Single element — A single token in RPN, a single temperature.
• All same elements — No “next greater” exists for any element.
• Strictly increasing/decreasing — Tests whether your stack drains or fills completely.
• Integer overflow — In expression evaluation, intermediate results can overflow int. Ask the interviewer whether to use long.

Interviewer tips:

• Name your Deque variable stack, not deque — it communicates intent.
• When explaining the monotonic stack, trace through a small example on paper. Interviewers want to see your reasoning, not a memorized template.
• If a problem smells like “find the nearest X for each element,” think monotonic stack immediately.
• For parentheses problems, propose the “push the expected closing bracket” trick — it shows a polished solution rather than a brute-force mapping approach.
• Always clarify: “Should I use the JDK Deque interface, or implement the stack from scratch?” Most interviewers want you to use ArrayDeque and focus on the algorithm, but some want the implementation for data structure interviews.

The stack’s LIFO constraint turns out to be one of the most powerful tools in your interview toolkit. The monotonic stack pattern alone handles at least five common interview problems. Combined with expression evaluation and parentheses matching, you have a pattern vocabulary that covers the majority of stack-related questions interviewers ask. Next, you move to the stack’s complement: the queue, where FIFO ordering unlocks BFS and an entirely different problem category.