The Stack: Undo, Recursion, and the O(n) Trick Interviewers Love

You typo a whole paragraph, hit Ctrl+Z, and the last thing you did vanishes. Hit it again — the thing before that, gone too. You open six links in a row, then tap the back button four times and walk back out through the exact doors you came in.

You never think about it, but both of those are the same tiny machine at work: a pile where the only thing you can touch is whatever you put down last. That machine is called a stack, and once you see its shape you’ll notice it running half the software you touch — including, as we’ll see, the language your program is written in. By the end of this article you and I will have built one from scratch, watched recursion secretly use one, and cracked an interview favourite that turns an obvious O(n²) problem into a single O(n) sweep.

Let’s start nowhere near a computer

Walk into any cafeteria and you’ll find a spring-loaded plate dispenser: a metal tube with a stack of clean plates, held up by a spring so the top one always sits flush with the opening.

You take a plate — you take the top one. You can’t take the third plate down without lifting the two above it first. And when the dishwasher slides clean plates back in, they go on top, pressing the spring down.

That’s the whole idea, and it has a name: LIFO — last in, first out. The plate that went in most recently is the one that comes out next. There’s no line, no fairness, no reaching into the middle. Two moves and two moves only: put one on top, take one off the top.

Hold onto the dispenser image, because every single thing we build in this article is just that tube in disguise.

The same trick, all over your day

Once the shape clicks, you’ll spot stacks everywhere — and they’re always solving the same problem: "what did I most recently do, and how do I undo it?"

• Undo / redo. Every edit you make gets pushed onto an undo stack. Ctrl+Z pops the last one and reverses it. Redo is a second stack catching whatever you undo.
• The browser back button. Each page you visit is pushed; back pops the top and returns you to the previous one, in perfect reverse order.
• Balanced brackets. Compilers, linters, and your editor’s rainbow parentheses all check that every ( has a matching ) using a stack — we’ll write that check ourselves below.
• Backtracking. Solving a maze, a sudoku, or a phone-unlock pattern means pushing each choice, and popping it to step back the moment it leads to a dead end.
• Evaluating expressions. Calculators turn 3 + 4 × 2 into an answer by pushing numbers and operators and popping them in the right order.

But the deepest example isn’t something you use — it’s something you’re standing inside right now. Every running program keeps a stack of half-finished function calls, and that stack is so fundamental that when a beginner writes a recursion with no exit, the error they get is named after it: stack overflow. We’ll open that one up properly later.

What a stack actually looks like

Before any code, here’s the mental picture we’re coding toward. The simplest way to store a stack is one plain block of slots — an array — plus a single number, top, that remembers how many plates are in and where the next one goes.

Read that top marker carefully, because it does double duty. It’s the count of elements (four of them here), and it’s the index of the next free slot — the exact spot the next push will write to. When top is 0, the stack is empty. Nudge one number up or down and the whole structure updates. That’s why every core operation is going to cost O(1): there’s no shifting, no searching, no walking — just a single index doing one step of arithmetic.

Let’s build one, step by step

We’ll assemble the class in small pieces, and at the end I’ll hand you the whole thing.

Step 1: the two fields

A stack needs almost nothing: the block of slots, and the marker.

public final class ArrayStack<E> {
    private E[] data;   // the block of slots
    private int top;    // how many are in — and the index the next push writes to
 
    @SuppressWarnings("unchecked")
    public ArrayStack() {
        data = (E[]) new Object[8];   // start small; we'll grow as needed
        top = 0;                      // empty
    }
}

That’s it. Two fields. Everything else is moving top.

Step 2: push — but watch the array run out of room

Pushing looks trivial: write the value at slot top, then bump top.

// BROKEN: assumes there is always room
public void push(E value) {
    data[top++] = value;   // throws once the array fills up
}

Run that and it’s happy — until the eighth push. On the ninth, top is 8, the array only has slots 0..7, and you get an ArrayIndexOutOfBoundsException. Our tube ran out of height.

The fix is the same one dynamic arrays use: when the block is full, allocate a bigger block, copy everything over, and keep going. Doubling the size each time is the classic move.

public void push(E value) {
    if (top == data.length) {
        grow();                 // out of room → make room
    }
    data[top++] = value;        // write at the top, then move top up
}
 
@SuppressWarnings("unchecked")
private void grow() {
    E[] bigger = (E[]) new Object[data.length * 2];
    System.arraycopy(data, 0, bigger, 0, data.length);
    data = bigger;
}

Copying the whole array sounds expensive, and one push can be. But because we double each time, those costly copies get rarer and rarer as the stack grows — so spread across all your pushes, each one still averages O(1). (That "average over many operations" is called amortized cost, and it’s exactly why appending to a growable array is considered constant time.)

Step 3: pop — and the empty-stack trap

Popping is push in reverse: step top down, hand back what’s there. The naive version forgets one thing:

// BROKEN: no empty check
public E pop() {
    return data[--top];   // if the stack is empty, top goes to -1 → boom
}

Pop an empty stack and top drops to -1, and data[-1] throws. Worse, in a version that reused old slots you could hand back a stale plate — a value you already popped, still sitting in the array. So we guard the empty case explicitly, and null out the slot we vacate so the garbage collector can reclaim it.

public E pop() {
    if (top == 0) {
        throw new NoSuchElementException("pop from an empty stack");
    }
    E value = data[--top];   // step down, then read
    data[top] = null;        // let the garbage collector reclaim it
    return value;
}

Step 4: peek, isEmpty, size — the free ones

The rest are one-liners, and each is O(1) because they only read top. peek is pop without the removal — it’s how you look at the next plate without taking it.

public E peek() {
    if (top == 0) {
        throw new NoSuchElementException("peek at an empty stack");
    }
    return data[top - 1];   // the top element, left in place
}
 
public boolean isEmpty() { return top == 0; }
public int size()        { return top; }

Array or linked? The two ways to build one

An array isn’t the only backing. The other classic is a linked stack: each element is its own little node holding a value and a pointer to the one below it, and top is just a reference to the head. Push makes a new node pointing at the old top; pop follows the head’s pointer one step down.

Both are genuine stacks, and here’s the thing that surprises people: on the operations that matter, they’re identical. The trade-off is about memory, not speed.

So which do you reach for? The array-backed one wins almost always — it’s compact, cache-friendly (neighbours sit next to each other in memory), and its only weakness is that one occasional copy. Reach for the linked version when a single slow push is genuinely unacceptable (hard real-time systems) or when you truly can’t guess a starting size.

The complete implementation

Everything above, assembled into one class you can drop into a project or reproduce on a whiteboard:

package dev.fiveyear.stack;
 
import java.util.NoSuchElementException;
 
public final class ArrayStack<E> {
 
    private E[] data;
    private int top;   // count of elements; also the next free index
 
    @SuppressWarnings("unchecked")
    public ArrayStack() {
        data = (E[]) new Object[8];
        top = 0;
    }
 
    /** Add a value on top. O(1) amortized. */
    public void push(E value) {
        if (top == data.length) {
            grow();
        }
        data[top++] = value;
    }
 
    /** Remove and return the top value. O(1). Throws if empty. */
    public E pop() {
        if (top == 0) {
            throw new NoSuchElementException("pop from an empty stack");
        }
        E value = data[--top];
        data[top] = null;   // let the garbage collector reclaim it
        return value;
    }
 
    /** Look at the top value without removing it. O(1). Throws if empty. */
    public E peek() {
        if (top == 0) {
            throw new NoSuchElementException("peek at an empty stack");
        }
        return data[top - 1];
    }
 
    public boolean isEmpty() { return top == 0; }
    public int size()        { return top; }
 
    @SuppressWarnings("unchecked")
    private void grow() {
        E[] bigger = (E[]) new Object[data.length * 2];
        System.arraycopy(data, 0, bigger, 0, data.length);
        data = bigger;
    }
}

And here it is behaving like the browser back button — the last tab in is the first one out:

ArrayStack<String> tabs = new ArrayStack<>();
tabs.push("home");
tabs.push("docs");
tabs.push("api");
 
tabs.peek();   // "api"  — look, don't remove
tabs.pop();    // "api"  — last in, first out
tabs.pop();    // "docs"
tabs.size();   // 1      — only "home" is left

Recursion is a stack you never declared

Here’s the payoff for building all that intuition. Look at plain recursion — say, factorial:

static long factorial(int n) {
    if (n == 0) return 1;              // the base case — the way out
    return n * factorial(n - 1);       // a call that must finish first
}

There’s no stack anywhere in that code. And yet a stack is absolutely running. Every time a function calls another, the machine pushes a stack frame — a little record holding that call’s arguments, local variables, and the line to return to. The called function runs, and when it returns, its frame is popped and control snaps back to exactly where it left off.

Watch factorial(3). It can’t finish until factorial(2) finishes, which can’t finish until factorial(1), which waits on factorial(0). Frames pile up — deeper, deeper — until factorial(0) hits the base case and returns 1 without recursing. Now the pile unwinds: each frame pops, multiplies, and hands its result down to the one below, folding 1 → 1 → 2 → 6 back out.

This is why the base case isn’t optional decoration — it’s the only thing that stops the pushing. Forget it, and frames pile up forever until the machine’s call stack runs out of room and throws that infamous StackOverflowError. The pile has a ceiling, and infinite recursion hits it.

Matching brackets, the classic

Time for the interview warm-up that shows up everywhere: given a string of brackets, is it balanced? {[()]} is fine; ([)] is not, because the brackets cross.

Your first instinct might be to just count — add one for an opener, subtract for a closer, check you end at zero:

static boolean looksBalanced(String s) {
    int balance = 0;
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') balance++;
        else if (c == ')' || c == ']' || c == '}') {
            balance--;
            if (balance < 0) return false;
        }
    }
    return balance == 0;
}

That handles ((())) perfectly. But feed it ([)] and it happily returns true — the count hits zero, so it looks balanced. The problem is that counting throws away which bracket is open. A ) has to close a (, not whatever happens to be open.

That "close the most recent opener, and it must be the matching type" is a stack in disguise. As you scan, push the closer you’re expecting; when you hit a real closer, it must equal the top of the stack.

static boolean isBalanced(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        switch (c) {
            case '(' -> stack.push(')');
            case '[' -> stack.push(']');
            case '{' -> stack.push('}');
            case ')', ']', '}' -> {
                if (stack.isEmpty() || stack.pop() != c) {
                    return false;   // nothing open, or the wrong type
                }
            }
            default -> { }          // ignore everything else
        }
    }
    return stack.isEmpty();         // leftover openers → unbalanced
}

Pushing the expected closer (instead of the opener) is a small, sweet trick: it turns the match check into a plain equality. isBalanced("([)]") now correctly returns false, because when the ) arrives the top of the stack is the ] we were waiting on. Two failure modes get caught: a closer with nothing open (stack.isEmpty()), and a leftover opener at the end (the final stack.isEmpty() check).

The clever one: the monotonic stack

Now the move that separates "I know what a stack is" from "I know what a stack is for." It’s the trick that makes strong interviewers nod, and it’s the stack equivalent of a magic show.

The problem: for each number in an array, find the next greater element — the first value to its right that’s bigger. For [2, 1, 2, 4, 3] the answer is [4, 2, 4, -1, -1] (a -1 means "nothing bigger ever comes").

The obvious solution is two loops: for each element, scan everything to its right. That’s O(n²). On a million-element array, a trillion comparisons. We can do it in a single pass, O(n), and the whole magic is one stack.

Here’s the intuition, and it’s beautifully human. Picture the numbers as people of different heights standing in a line, each craning to spot the first taller person to their right. A short person might have to wait a long time. So keep a stack of everyone still waiting — and here’s the key — because a taller person would already have blocked the view of a shorter one behind them, the people left waiting always stand in decreasing height, top to bottom. That’s the "monotonic" in monotonic stack: the stack stays sorted, for free, as a side effect.

Now walk the line left to right. When a new person arrives, they are the answer for everyone currently waiting who is shorter than them. So pop each shorter waiter off, record this newcomer as their answer, and stop at the first person taller (who keeps waiting). Then the newcomer joins the wait.

Watch the 4 arrive in the diagram. Two 2s were waiting — and the 4 is taller than both, so it clears them both in one avalanche of pops, becoming the answer for each. Then 3 arrives, isn’t taller than the 4 still waiting, so it just gets in line. When the sweep ends, whoever’s still on the stack (4 and 3) never found anyone taller — their answer is -1.

static int[] nextGreater(int[] nums) {
    int[] answer = new int[nums.length];
    Arrays.fill(answer, -1);                     // default: nothing bigger
    Deque<Integer> stack = new ArrayDeque<>();   // indices, values decreasing
    for (int i = 0; i < nums.length; i++) {
        while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
            answer[stack.pop()] = nums[i];       // i is the first taller one
        }
        stack.push(i);                           // now i waits its turn
    }
    return answer;
}

Now for the part that feels like cheating. That while loop inside the for loop looks like O(n²) — a nested loop is the universal signature of quadratic. So why is it O(n)?

Because each index is pushed exactly once, and popped at most once. A single while can pop many elements — the 4 cleared two at once — but across the entire run, the total number of pops can never exceed the total number of pushes, which is n. The inner loop borrows against a budget the outer loop already paid. Add the n pushes and at most n pops: 2n operations, which is O(n). That’s the whole illusion — the nested loop isn’t nested work, it’s the same n elements each getting handled twice.

The interview corner

Stacks show up in interviews both as a topic and as a hidden tool inside other problems. Here’s how to handle both.

Before you touch the keyboard, ask:

• What should popping or peeking an empty stack do — throw, or return a sentinel? This single question shows you think about edge cases before writing them.
• Is there a maximum size, or should it grow unbounded? A fixed cap changes push (reject vs. grow) and matters for memory-bound systems.
• Do you need anything beyond LIFO — like the minimum so far, in O(1)? That’s a real variant (below), and asking surfaces it early.

The follow-up ladder — where a good interviewer takes you next:

1. "Implement it with a linked list instead of an array." — Each node points to the one below; top is the head. Push and pop become head insert/remove, both O(1), no resizing — at the cost of a pointer per element.
2. "Add getMin() that returns the smallest element in O(1)." — Keep a second stack that only ever holds the running minimum; push to it when the new value is ≤ its top, pop it in lockstep. Every operation stays O(1).
3. "Build a queue using only stacks." — Use two: push onto an inbox stack; when you dequeue, if the outbox is empty, pour the inbox into it (reversing the order), then pop. Amortized O(1) per operation — the same doubling-style accounting.
4. "Evaluate 3 + 4 * 2 - 1." — Two stacks (values and operators), or convert to postfix first; pop and apply when a lower-or-equal-precedence operator arrives. This is the shunting-yard algorithm, and it’s stacks all the way down.
5. "Find the next greater element, in one pass." — The monotonic stack above. If you can explain why it’s O(n) despite the nested loop, you’ve cleared the bar most candidates trip on.

Three mistakes that fail the round:

• Popping without checking empty. An unguarded pop on an empty stack is the single most common crash. State your empty-policy out loud, then enforce it.
• Calling the nested loop O(n²). In the monotonic-stack answer, if you can’t defend the linear bound with the "pushed once, popped once" argument, the interviewer assumes you memorised the code without understanding it.
• Reaching for a stack when order doesn’t reverse. A stack is for LIFO. If the problem wants oldest-first (a print queue, a scheduler, level-order traversal), you want a queue — using a stack there quietly reverses your output.

Where to go from here

You now own the core: two moves at the top, everything O(1), and a hidden stack running under every function call. Three natural next stops:

• The queue and the deque — the FIFO cousin, and the double-ended structure (ArrayDeque) that plays both stack and queue. Pair this article with them and you’ve got the two workhorses of half of all algorithm problems.
• Depth-first search — the graph traversal that is a stack, whether you write it with recursion (the call stack) or an explicit one. It’s the engine behind the trie’s autocomplete walk and countless backtracking problems.
• Largest rectangle in a histogram — the monotonic stack’s boss level. Same "pop the shorter ones" idea, applied to bar heights, and a genuinely satisfying O(n) when you get it.

Next time you hit Ctrl+Z, picture that spring-loaded tube of plates popping the last one off — and know that the recursion running your undo, the parser reading your code, and the call stack you’re standing inside are all the very same machine.