Stacks

You’ve already met a stack — every stack trace you read in How Java Actually Runs was a literal printout of one. The interviewer’s favorite warm-up (“are these brackets balanced?”), your editor’s undo, the browser back button, and the JVM running your code are all the same data structure wearing different clothes. This module makes you see it everywhere.

The Goal

By the end of this module you can:

• Explain LIFO and why “deal with the most recent unfinished thing first” shows up across computing
• Implement Valid Parentheses in Java with ArrayDeque, and say why java.util.Stack is the wrong class
• Connect the data structure to the JVM call stack you already know — and to recursion, before module 10 makes it formal
• Implement a monotonic stack for next-greater-element problems, the move that separates easy from medium
• Recognize stack problems from wording: nesting, matching, most-recent, “next greater”
• Build undo/redo from two stacks and explain why one stack isn’t enough

The Lesson

LIFO — last in, first out

A stack supports exactly two interesting moves: push (put on top) and pop (take from top). The last thing in is the first thing out. That’s it — the whole structure.

Why does something this dumb appear everywhere? Because an enormous number of processes have the shape “start a thing, get interrupted by an inner thing, finish the inner thing first, then resume.” Nesting. The most recent unfinished item is always the one you must deal with next — and “most recent” is exactly what the top of a stack hands you in O(1).

The right Java class — and why it’s not Stack

Java has a class literally named java.util.Stack. Don’t use it. It dates from Java 1.0, extends Vector (so every operation takes a synchronization lock you don’t need, and you can illegally poke elements in the middle by index — breaking the whole LIFO contract). Its own Javadoc tells you to use Deque instead. Interviewers notice this.

The modern choice is ArrayDeque:

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

Deque<Character> stack = new ArrayDeque<>();
stack.push('(');           // put on top
char top = stack.peek();   // look at top, leave it
char out = stack.pop();    // take top off
boolean empty = stack.isEmpty();

One trap to know now: pop() and peek() on an empty ArrayDeque throw NoSuchElementException. Always check isEmpty() before popping. Half of all stack bugs are exactly this.

The canonical problem — Valid Parentheses

“Given a string containing ()[]{}, is every bracket closed by the right type in the right order?”

The insight: when you hit a closer, the bracket it must match is the most recently opened, not-yet-closed one. Most recent unfinished thing — that sentence IS a stack:

flowchart LR
    A[Read next char] --> B{Opener or closer}
    B -->|opener| C[Push it]
    B -->|closer| D{Stack top matches}
    D -->|yes| E[Pop and continue]
    D -->|no or empty| F[Invalid]
    A --> G{Input done}
    G -->|stack empty| H[Valid]
    G -->|stack not empty| F

The full solution, runnable:

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

public class ValidBrackets {
    public static void main(String[] args) {
        System.out.println(isValid("{[()]}"));   // true
        System.out.println(isValid("([)]"));     // false - wrong order
        System.out.println(isValid("(("));       // false - unfinished openers
        System.out.println(isValid(")"));        // false - closer with no opener
    }

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

        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);                       // opener: a new unfinished thing
            } else {
                if (stack.isEmpty()) return false;    // closer with nothing open
                if (stack.pop() != pairs.get(c)) return false; // wrong type closed
            }
        }
        return stack.isEmpty();                       // leftovers = unclosed openers
    }
}

Walk "([)]" by hand: push (, push [, then ) arrives — the top is [, not (. Invalid. Notice the three distinct failure modes in the test cases; interviewers probe all three, and most candidates forget the final isEmpty() check.

Brute force comparison: repeatedly scanning the string deleting adjacent pairs is O(n²). The stack does it in one O(n) pass with O(n) space worst case.

You already run a stack — the call stack

In How Java Actually Runs you drew frames stacking up as main called printSummary. That’s not an analogy — the JVM’s call stack is a push/pop stack of frames. Calling a method pushes a frame; returning pops it. A stack trace is the stack printed top-first at the moment of death. StackOverflowError is literally “push failed — no room.”

Which means: recursion IS a stack. Every recursive call is a push; every return is a pop. Any recursive algorithm can be rewritten with an explicit ArrayDeque and a loop — same logic, your stack instead of the JVM’s. Hold that thought; Recursion & Backtracking builds on exactly this.

The advanced move — monotonic stack

This one upgrades you from easy to medium. The problem family: “for each element, find the next element to its right that is greater” — next greater element, daily temperatures, stock spans.

Brute force: for each element, scan rightward until something bigger appears. O(n²).

The trick: walk left to right keeping a stack of indices whose answer is still unknown, arranged so their values are decreasing from bottom to top. When a new value arrives, it is the answer for every stacked element it beats — pop them all, record answers, then push the newcomer.

Walk it on temperatures {30, 40, 35, 32, 38, 45} — “how many days until a warmer day?”:

Result: [1, 4, 2, 1, 1, 0] (index 5 never gets beaten — answer 0). Each index is pushed once and popped at most once, so the whole thing is O(n).

The template:

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

public class NextWarmerDay {
    public static void main(String[] args) {
        int[] temps = {30, 40, 35, 32, 38, 45};
        int[] wait = new int[temps.length];          // defaults to 0 = never

        Deque<Integer> stack = new ArrayDeque<>();   // indices, temps decreasing
        for (int i = 0; i < temps.length; i++) {
            while (!stack.isEmpty() && temps[i] > temps[stack.peek()]) {
                int beaten = stack.pop();            // i is its answer
                wait[beaten] = i - beaten;
            }
            stack.push(i);
        }

        for (int w : wait) System.out.print(w + " "); // 1 4 2 1 1 0
    }
}

The recognition rule: store indices, not values (you need positions to compute distances), and the stack stays monotonic (decreasing here) because anything the newcomer beats is resolved and removed.

Undo/redo — two stacks

One stack of edits gives you undo: pop the latest edit, reverse it. But where does redo come from? A second stack. Undo pops from the undo stack and pushes onto the redo stack; redo does the reverse. The moment you make a fresh edit after undoing, the redo stack is cleared — that abandoned future is gone, exactly like your editor behaves. Two stacks, four rules, and you’ve specified the undo system of every editor you’ve ever used.

See It Move

Watch the stack panel as each bracket arrives — openers pile up, closers must match the top or the whole string dies. Toggle to the broken example and catch the exact step where it fails.

Step through it and notice:

• The stack only ever grows by openers — closers never enter it; they cancel the top.
• At every step, the top of the stack is the most recent unclosed opener — the only one a closer is allowed to match.
• The broken example fails the instant the mismatch is read, not at the end — stacks give you early exit.
• A valid string always ends with an empty stack; leftovers mean unclosed openers.

Spot The Pattern

Where It Runs In Real Life

The JVM under your code. Every Java program you run is a stack machine in action: method call pushes a frame, return pops it, and a stack trace is the stack printed at the moment of the crash. When you debugged HelloBank by reading the trace top-down, you were reading a stack. StackOverflowError from runaway recursion is the stack physically filling up.

Undo in every editor. VS Code, IntelliJ, Google Docs, Photoshop — all keep your edits on a stack (plus a redo stack). The reason undo always reverses the most recent change first, and the reason redo dies when you type something new, are both direct consequences of the two-stack design you just learned.

Browser back button. Leaving a page pushes it onto the history stack; back pops it. Navigating somewhere new after going back throws away the “forward” stack — same rule as redo. You’ve been using paired stacks since you first opened a browser.

Parsers and compilers. javac checking that your braces balance, your calculator app evaluating 2 + 3 * 4, every JSON and HTML validator confirming tags nest correctly — all stack-driven, because syntax is nested and nesting is LIFO. The Valid Parentheses problem is a baby parser.

Monitoring and pricing systems. “For each stock price, when did it last get exceeded?” — stock span and next-greater queries in trading dashboards run the monotonic stack, because the O(n²) rescan version cannot keep up with live ticks.

Build This

You’re building BracketChecker — a terminal bracket validator — then breaking it and bolting on the monotonic template.

1. Create a folder bracketchecker, and inside it BracketChecker.java:

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

public class BracketChecker {

    public static void main(String[] args) {
        String input = args.length > 0 ? args[0] : "{[()]}";
        System.out.println("\"" + input + "\" -> " + (isValid(input) ? "VALID" : "INVALID"));
    }

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

        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else if (pairs.containsKey(c)) {
                if (stack.isEmpty() || stack.pop() != pairs.get(c)) {
                    return false;
                }
            }
            // any other char (letters, digits) is ignored - code has brackets AND content
        }
        return stack.isEmpty();
    }
}

2. Compile and run it against all three failure families:

javac BracketChecker.java
java BracketChecker "{[()]}"
java BracketChecker "([)]"
java BracketChecker "((("
java BracketChecker ")"

Confirm: VALID, INVALID, INVALID, INVALID — and say out loud which rule each invalid one broke.

3. Break it — remove the empty check. Delete stack.isEmpty() || from the closer branch. Recompile, run java BracketChecker ")". Read the exception name and the stack trace like you learned in How Java Actually Runs. That crash is the number one stack bug in real code. Fix it back.

4. Break it — return true unconditionally at the end. Replace return stack.isEmpty(); with return true;. Run java BracketChecker "(((". It now blesses unclosed openers. This is the bug interviewers fish for. Fix it back.

5. Extend it — monotonic. Add a method nextGreater(int[] nums) that returns, for each element, the next value to its right that is greater (or -1). Use the NextWarmerDay template but store values via indices. Test with {2, 1, 2, 4, 3} — expected {4, 2, 4, -1, -1}. Trace one run on paper with the table format from the lesson before you run it.

6. Extend it — undo. Add a tiny loop that reads words from args, pushing each onto an undo stack; when the word is literally undo, pop and print what was undone. You’ve built the skeleton of every editor’s history feature.

Problems To Solve

The rule: solve until you can write both templates from memory. If stuck 25 minutes, read the approach, close it, re-solve from scratch.

Check Yourself

1. What does LIFO mean, and what kind of real-world process naturally has that shape?
2. Why is ArrayDeque preferred over java.util.Stack in modern Java? Two reasons.
3. In Valid Parentheses, what are the three distinct ways a string can be invalid?
4. What happens if you pop() an empty ArrayDeque, and how do you guard against it?
5. How is a stack trace related to the stack data structure?
6. In a monotonic stack for next-greater-element, why do you store indices instead of values?
7. Why is the monotonic stack O(n) even though there’s a while-loop inside the for-loop?
8. In undo/redo, why does making a fresh edit clear the redo stack?

Explain it out loud: Face the empty chair and walk through validating "([)]" character by character, narrating the stack after each step and naming the exact moment it fails. Then explain in two sentences why a recursive method and this bracket checker are running the same machinery. If the second part feels vague, re-read the call stack section.

Still Unclear?

Copy-paste any of these into Claude — they’re built to deepen understanding, not to do the work for you:

I'm learning stacks in Java. Give me 6 short strings of mixed brackets,
one at a time. For each, I will tell you VALID or INVALID and which of the
three failure modes applies. Check my reasoning, not just my answer.
Don't show me any code.

Walk me through the monotonic stack on temperatures [73, 74, 75, 71, 69,
72, 76, 73] as a step-by-step table: index, stack contents, what gets
popped, what answer is recorded. Pause after row 3 and make me predict
the next row before showing it.

Explain how the JVM call stack, a recursive method, and an explicit
ArrayDeque-with-a-loop version of the same algorithm relate to each other.
Use a tiny factorial example, but make ME write the explicit version and
critique it instead of writing it yourself.

Why AI Can’t Do This For You

AI writes a perfect Valid Parentheses in one second — the problem is famous and the answer is memorized. But “the import job dies whenever vendor XML has self-closing tags inside comments” doesn’t say stack anywhere. Seeing the nesting shape inside a messy production ticket — and knowing the fix is a matching stack, not a pile of regexes — is recognition, and recognition only comes from having pushed and popped these things with your own hands.

There’s a second layer: stacks are how your runtime thinks. When a StackOverflowError or a 40-line stack trace lands at 2 a.m., the engineer who understands frames-push-frames reads it like a map. AI can summarize the trace; it can’t be the person in the room who knows, instantly, which frame is the lie.

Module done? Add it to today’s tracker