Stacks

Last in, first out

A stack restricts you deliberately. You may only add to the top and remove from the top. The most recently added item is the first one you get back.

The usual picture is a stack of plates: you put a plate on top, and you take one off the top. Reaching the bottom plate means removing everything above it.

Three operations define it:

The restriction is the point. Because there are only three things you can do, code using a stack is easy to reason about.

Which class to use

Java has a Stack class, but the recommended choice is ArrayDeque.

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

Deque<String> history = new ArrayDeque<>();

history.push("moveArm");
history.push("closeClaw");
history.push("liftArm");

System.out.println(history.peek());   // liftArm
System.out.println(history.pop());    // liftArm
System.out.println(history.pop());    // closeClaw
System.out.println(history.size());   // 1

Checking for empty

pop and peek on an empty ArrayDeque throw NoSuchElementException. Always check first.

while (!history.isEmpty()) {
    System.out.println(history.pop());
}

If you would rather get null than an exception, use the polling forms:

String top = history.poll();     // null when empty, instead of throwing
String look = history.peekFirst();

Where stacks show up

Undo history. Each action gets pushed. Undo pops the most recent one — exactly the behaviour you want.

Matching brackets. Push each opening bracket; on a closing bracket, pop and check it matches.

static boolean isBalanced(String s) {
    Deque<Character> stack = new ArrayDeque<>();

    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (stack.isEmpty()) return false;      // closing with nothing open
            char open = stack.pop();
            if ((c == ')' && open != '(') ||
                (c == ']' && open != '[') ||
                (c == '}' && open != '{')) {
                return false;                        // mismatched pair
            }
        }
    }
    return stack.isEmpty();                          // anything left unclosed?
}

Two checks are easy to forget: popping from an empty stack means a closing bracket appeared with nothing open, and a non-empty stack at the end means something was never closed. Both are failures.

Reversing. Push everything, then pop everything.

Deque<Integer> stack = new ArrayDeque<>();
for (int v : values) stack.push(v);
while (!stack.isEmpty()) System.out.print(stack.pop() + " ");

Method calls. Java itself uses a stack. Each method call pushes a frame holding its local variables; returning pops it. This is why infinite recursion throws StackOverflowError — the call stack has a size limit.

That connection is worth holding onto: a recursive method and an explicit stack can express the same thing. Deep recursion that overflows can often be rewritten as a loop with a Deque.

Building one yourself

Worth doing once, to see there is nothing mysterious inside.

class IntStack {
    private int[] data = new int[16];
    private int size = 0;

    void push(int value) {
        if (size == data.length) {
            data = java.util.Arrays.copyOf(data, size * 2);   // grow
        }
        data[size++] = value;
    }

    int pop() {
        if (size == 0) throw new IllegalStateException("stack is empty");
        return data[--size];
    }

    int peek() {
        if (size == 0) throw new IllegalStateException("stack is empty");
        return data[size - 1];
    }

    boolean isEmpty() { return size == 0; }
}

All three operations touch only the last slot, so all three are instant. Growing happens rarely, exactly as in ArrayLists.

Next