Stacks

Three operations: push, pop, peek

A stack supports three core operations, all O(1), meaning each takes constant time regardless of how many items are stored. Push places a new item on top. Pop removes and returns the top item. Peek looks at the top item without removing it. That is the whole interface. There is deliberately no way to reach into the middle.

In Java, the recommended implementation is ArrayDeque. Ignore the legacy Stack class; it dates from 1995, carries synchronization overhead you do not need, and even Java's own documentation steers you to Deque instead. With ArrayDeque, push adds to the front, pop removes from the front, and peek reads it. One caution: pop and peek throw an exception on an empty stack, so check isEmpty() first.

Deque<Integer> stack = new ArrayDeque<>();
stack.push(10);
stack.push(20);
stack.push(30);

System.out.println(stack.peek()); // 30
System.out.println(stack.pop());  // 30
System.out.println(stack.pop());  // 20
System.out.println(stack.isEmpty()); // false

The classic use: matching brackets

Here is the problem every stack tutorial earns its keep on: given a string like ([]{}), decide whether the brackets are balanced. The insight is that a closing bracket must match the most recently opened bracket that is still waiting, and most recent is exactly what a stack tracks.

Walk the string left to right. When you see an opening bracket, push it. When you see a closing bracket, the top of the stack must be its partner; pop it and continue, or fail if it is the wrong kind or the stack is empty. At the end, the stack must be empty. Leftover openers mean something was never closed. Every character is pushed and popped at most once, so the whole check runs in O(n) time.

boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } else {
            if (stack.isEmpty()) return false;
            char open = stack.pop();
            if (c == ')' && open != '(') return false;
            if (c == ']' && open != '[') return false;
            if (c == '}' && open != '{') return false;
        }
    }
    return stack.isEmpty();
}

The call stack: the stack you use every day

Every time a Java method calls another method, the runtime pushes a frame (a record of the caller's local variables and where to resume) onto a built-in stack called the call stack. When the inner method returns, its frame is popped and the caller picks up exactly where it left off. Last called, first finished: LIFO again.

This is why recursion works at all. A recursive method like factorial(5) pushes frames for factorial(4), factorial(3), and so on down to the base case, then pops them back in reverse order as each result returns. It is also why runaway recursion crashes with a StackOverflowError: the call stack has finite room, and infinite recursion keeps pushing frames until it runs out. A useful consequence for problem solving: any recursive algorithm can be rewritten with an explicit stack of your own, which is exactly how iterative depth-first search works.

Recognizing stack problems

Stack problems share a smell: the current item interacts with the most recent unfinished thing. Matching and nesting problems (brackets, HTML tags, directory paths) are the purest form. Undo and history features are stacks by definition. Expression evaluation (turning 3 + 4 * 2 into an answer) uses one stack for numbers and one for operators. A more advanced family, monotonic stack problems like Next Greater Element and Largest Rectangle in Histogram, keeps the stack sorted so that each push pops everything it makes irrelevant.

When you spot phrases like most recent, nested, undo, or reverse the order, reach for a stack. And once you are comfortable with last in, first out, the natural next question is: what happens if the first one in should come out first instead? That structure is the queue, and it is up next.

Frequently asked