Stacks in Java

A stack is a last in, first out (LIFO) collection: the last element added is the first one removed, like a stack of plates. It supports three main operations, all O(1):

push: add an element on top
pop: remove and return the top element
peek: look at the top element without removing it

graph TB
    subgraph s["stack after push 1, push 2, push 3"]
        direction TB
        t["3  (top: next pop returns this)"] --- m["2"] --- b["1  (bottom)"]
    end

`ArrayDeque` is the stack

Java has a legacy Stack class, but the standard choice is ArrayDeque, a resizable array used as a double-ended queue (deque). Its push, pop, and peek work at the head of the deque, so the head is the top of the stack. These calls are O(1) amortized. ArrayDeque rejects null elements, so peek and poll can use null to mean "empty" without ambiguity.

Stack operation	`ArrayDeque` method	Returns
push	`push(x)`	nothing
pop	`pop()`	the top element, throws `NoSuchElementException` when empty
pop (no exception)	`poll()`	the top element, `null` when empty
peek	`peek()`	the top element, `null` when empty
change the top	`pop()` then `push(y)`	no in-place edit
is empty	`isEmpty()`	`boolean`
size	`size()`	`int`

Java

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

public class Main {
    public static void main(String[] args) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println("top = " + stack.peek() + ", size = " + stack.size());

        int top = stack.pop();
        stack.push(top * 10); // change the top element: pop it, push the new value

        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop()).append(' ');
        }
        System.out.println(sb.toString().trim());
        System.out.println("pop on empty = " + stack.poll());
        try {
            stack.pop();
        } catch (java.util.NoSuchElementException e) {
            System.out.println("pop throws NoSuchElementException");
        }
    }
}

Output

top = 3, size = 3
30 2 1
pop on empty = null
pop throws NoSuchElementException

while (!stack.isEmpty()) is the standard loop that processes a stack until it is empty. Popping an empty stack with pop() throws NoSuchElementException. This is the "stack underflow" case. poll() and peek() return null instead, so check isEmpty() or the returned value before using it. Assigning that null to an int throws NullPointerException.

The five stack patterns

1. Matching pairs

When items must be closed in reverse order of opening (brackets, HTML tags, function calls), push each opener and pop it when its closer arrives.

Java

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

public class Main {
    static int maxDepth(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        int deepest = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(c);
                deepest = Math.max(deepest, stack.size());
            } else if (c == ')') {
                stack.poll(); // no exception if the stack is empty
            }
        }
        return deepest;
    }

    public static void main(String[] args) {
        System.out.println(maxDepth("(1+(2*3)+((8)/4))+1"));
    }
}

Output

Used in: Valid Parentheses.

2. Evaluate as you go

Operands wait on the stack until an operator needs them. Used in: Evaluate a Postfix Expression.

3. Monotonic stack

The stack keeps its elements in increasing or decreasing order. Before pushing a new element, pop everything that breaks the order. Each popped element has found its "next greater" (or "next smaller") element. Every element is pushed and popped at most once, so the whole pass is O(n).

Java

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

public class Main {
    // For each day, how many days until a warmer temperature? (LeetCode 739)
    static int[] dailyTemperatures(int[] temps) {
        int[] answer = new int[temps.length];
        Deque<Integer> waiting = new ArrayDeque<>(); // indices, temperatures decreasing
        for (int i = 0; i < temps.length; i++) {
            while (!waiting.isEmpty() && temps[waiting.peek()] < temps[i]) {
                int j = waiting.pop();
                answer[j] = i - j;
            }
            waiting.push(i);
        }
        return answer;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(dailyTemperatures(new int[]{73, 74, 75, 71, 69, 72, 76, 73})));
    }
}

Output

[1, 1, 4, 2, 1, 1, 0, 0]

Used in: Next Greater Element.

4. An auxiliary stack for extra information

Store extra information alongside each element, or in a second stack, so that questions like "what's the minimum?" are O(1). Used in: Min Stack, Sort a Stack.

5. Elimination

Pop two candidates, compare them, and push back only the one that could still be the answer. Used in: Find the Celebrity.

Replacing recursion with a stack

Every recursive function uses the call stack. Any recursion can be rewritten as a loop over an explicit ArrayDeque, which avoids a StackOverflowError on deep input. The call stack is limited by the thread stack size, while the deque grows on the heap. Here's a depth-first traversal written both ways:

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Main {
    static void dfsRecursive(List<List<Integer>> adj, int v, boolean[] seen, List<Integer> out) {
        seen[v] = true;
        out.add(v);
        for (int w : adj.get(v)) {
            if (!seen[w]) {
                dfsRecursive(adj, w, seen, out);
            }
        }
    }

    static List<Integer> dfsIterative(List<List<Integer>> adj, int start) {
        boolean[] seen = new boolean[adj.size()];
        List<Integer> out = new ArrayList<>();
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(start);
        while (!stack.isEmpty()) {
            int v = stack.pop();
            if (seen[v]) {
                continue;
            }
            seen[v] = true;
            out.add(v);
            List<Integer> next = adj.get(v);
            for (int k = next.size() - 1; k >= 0; k--) { // reversed so the first neighbor is popped first
                stack.push(next.get(k));
            }
        }
        return out;
    }

    public static void main(String[] args) {
        List<List<Integer>> adj = List.of(List.of(1, 2), List.of(3), List.of(3), List.<Integer>of());
        List<Integer> out = new ArrayList<>();
        dfsRecursive(adj, 0, new boolean[4], out);
        System.out.println(out + " " + dfsIterative(adj, 0));
    }
}

Output

[0, 1, 3, 2] [0, 1, 3, 2]

Complexity

Operation	`ArrayDeque` as a stack
`push`	`O(1)` amortized
`pop`, `poll`, `peek`, `isEmpty`, `size`	`O(1)`
search for a value (`contains`)	`O(n)`

ArrayDeque is the stack

The five stack patterns

1. Matching pairs

2. Evaluate as you go

3. Monotonic stack

4. An auxiliary stack for extra information

5. Elimination

Replacing recursion with a stack

Complexity

`ArrayDeque` is the stack