Stack algorithms with ArrayDeque

For this lesson, we'll focus on the stack patterns you should recognize in interviews and write cleanly in Java 21: balanced brackets, undo-redo, monotonic stacks, Reverse Polish Notation, min-stack, iterative DFS and the histogram rectangle stretch. We will use ArrayDeque as the stack, but we will not repeat its circular-array internals here; those live in Queue, Deque and ArrayDeque.

01Picture it first: unfinished work on top

A stack is a pile of unfinished promises. When you see {[()]}, every opener waits until its matching closer arrives. The innermost opener, (, is on top, so it must be resolved before [ and {.

That is the mental model: last opened, first resolved.

Fig. 1

Balanced bracket scanning pushes opening brackets and pops the most recent matching opener when a closer arrives

Interviewers love this pattern because it is small enough to code quickly and subtle enough to test whether you understand the invariant. The invariant is not "I have seen some brackets". It is sharper: the stack contains unmatched opening brackets, top first, in the only order they can still be closed.

02Balanced brackets under the hood

Here is how I'd write the core bracket checker. This version ignores non-bracket characters, which is a choice you should state if the prompt includes arbitrary text.

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

final class BalancedBracketsDemo {
    static boolean isValidBrackets(String input) {
        Deque<Character> stack = new ArrayDeque<>();
        Map<Character, Character> openingForClosing = Map.of(
                ')', '(',
                ']', '[',
                '}', '{'
        );

        for (char ch : input.toCharArray()) {
            if (ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);
            } else if (openingForClosing.containsKey(ch)) {
                if (stack.isEmpty() || stack.pop() != openingForClosing.get(ch)) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        System.out.println(isValidBrackets("{[()]}")); // true
    }
}

Notice three things:

• We check isEmpty() before pop() because empty pop() throws NoSuchElementException.
• We compare the closing bracket to the most recent unmatched opener, not to any opener seen earlier.
• We return stack.isEmpty() at the end because leftover openers mean the input ended too early.

For {[()]}, the walkthrough is short enough to narrate while coding:

If the input is ([)], the ) sees [ on top. That is the bug the stack catches: the right bracket exists, but the nesting order is wrong.