Stacks

A stack is last in, first out. Everything happens at one end, which is why every operation is O(1) and why the implementation is the shortest in this track.

Three operations

There is no "get the third element". A structure that let you do that would not be a stack — the restriction is the abstraction.

Why an array and not a linked list

A stack only ever touches one end, and the end of an array is exactly where appends are cheap. So the array version gets O(1) operations and contiguous memory, with no node allocation per element.

    public void push(E item) {
        if (size == items.length) {
            items = java.util.Arrays.copyOf(items, items.length * 2);
        }
        items[size++] = item;
    }

    @SuppressWarnings("unchecked")
    public E pop() {
        if (size == 0) {
            throw new EmptyStackException();
        }
        E item = (E) items[--size];
        items[size] = null; // let it be collected
        return item;
    }

Same doubling as ArrayList, same amortised O(1), and the same = null on the way out so a popped object is not pinned in memory by a slot nobody can reach.

Balanced brackets

The reason interviewers ask about stacks: it is the smallest problem where a stack is obviously the right answer. Each closing bracket must match the most recently opened one — which is the definition of LIFO.

    public static boolean balanced(String input) {
        ArrayStack<Character> stack = new ArrayStack<>();
        for (char c : input.toCharArray()) {
            switch (c) {
                case '(', '[', '{' -> stack.push(c);
                case ')' -> {
                    if (stack.isEmpty() || stack.pop() != '(') {
                        return false;
                    }
                }
                case ']' -> {
                    if (stack.isEmpty() || stack.pop() != '[') {
                        return false;
                    }
                }
                case '}' -> {
                    if (stack.isEmpty() || stack.pop() != '{') {
                        return false;
                    }
                }
                default -> { }
            }
        }
        // Anything still open is unbalanced - the check people forget.
        return stack.isEmpty();
    }

Two failure modes people miss, and both are asserted:

        Check.isTrue(!balanced("("), "never closed");
        Check.isTrue(!balanced(")("), "closed before opened");
        Check.isTrue(balanced(""), "empty string is balanced");

The stack.isEmpty() at the end catches "(" — the loop finishes happily with something still open. The stack.isEmpty() || guard inside catches ")(" — popping an empty stack. Omit either and the function returns true for input that is plainly wrong.

The call stack is one of these

When a method calls another, a frame holding its parameters, locals and return address is pushed. When it returns, that frame is popped. That is a literal stack, and it explains two things you have already met: why a stack trace reads innermost-first, and why recursion that never reaches its base case gives StackOverflowError — the pushes never stop.

Where else stacks show up

• Undo. The most recent action is the one to reverse.
• Back buttons. Same shape.
• Expression evaluation. Converting infix to postfix, and evaluating it.
• Depth-first search. DFS is BFS with the queue swapped for a stack.
• Backtracking. Every "try, fail, undo, try the next" algorithm.

⚠️ Do not use java.util.Stack

It has been effectively obsolete since Java 1.2, for two independent reasons:

1. It extends Vector, so every method is synchronised whether or not you are sharing it — you pay for locking you did not ask for.
2. Inheriting from Vector means it also inherits get(int), add(int, E) and the rest. So a Stack lets callers reach into the middle, and the restriction that made it a stack is gone.

Deque<String> stack = new ArrayDeque<>();
stack.push("a");
stack.push("b");
stack.pop();     // "b"

ArrayDeque is unsynchronised, backed by a circular array, and does not expose indexed access. Note one detail: ArrayDeque pushes onto the front, so iterating it goes top-to-bottom, whereas Stack — being a Vector — iterates bottom-to-top. Code that relied on the old iteration order will silently reverse.

What to remember

• LIFO, three operations, all O(1).
• Back it with an array; the one end you touch is the cheap end.
• Balanced brackets needs both the empty-pop guard and the final empty check.
• The call stack is a stack, which is what StackOverflowError means.
• Use ArrayDeque, never java.util.Stack.