Applications of Stack

A stack applies here whenever a process must suspend an unfinished unit of work, go deeper into a new one, and later resume exactly where it left off — the LIFO discipline guarantees the most recently suspended context is always the first one restored, which is precisely the order needed for nested/recursive structure (function calls, nested brackets, DFS branches, undo history).

Recognize the pattern

• The problem has nesting or reversal: brackets, tags, recursive calls, undo history, browser back button.
• You need to match the most recent unresolved item first (innermost bracket closes first, last action undone first).
• A traversal must fully exhaust one branch before trying a sibling (DFS) — as opposed to level-by-level (BFS, which needs a queue instead).
• You are converting a human-ordered (infix) sequence into a machine-ordered one by deferring operators until their operands are ready.

Brute force vs optimal

Take balanced-bracket validation as the running contrast. Brute force: repeatedly scan the string, find any adjacent matching pair like (), [], {}, delete it, and rescan from the start until no pair remains or the string is stuck. Each deletion costs an O(n) scan, and up to n/2 deletions happen, so this is O(n²) time, O(n) space for the mutable copy. Optimal (stack): scan once left to right; push every opener; on a closer, pop and check it matches. One pass, O(1) work per character → O(n) time, O(n) space worst case (all openers, e.g. (((().

Complexity, derived

Each of the n characters triggers exactly one stack operation (a push or a pop), and push/pop on an array-backed stack are O(1) amortized (occasional resize doubles capacity, amortizing to O(1) per op). Total operations = n ⇒ time O(n). Space is bounded by how many openers can be simultaneously unmatched — worst case every character is an opener, so the stack holds up to n entries ⇒ space O(n). The same accounting applies to DFS-with-explicit-stack (each vertex pushed once, popped once ⇒ O(V+E) time, O(V) space for stack + visited set) and to the call stack during recursion (space O(depth), not O(n), because siblings don't coexist).

Worked example: evaluating postfix 3 4 2 * 1 5 - / +

This is the postfix form of 3 + (4*2)/(1-5), produced by exactly the deferred-operator idea above. Scan left to right; numbers push, operators pop two operands, compute, push the result.

Final pop gives 1, matching 3 + (4*2)/(1-5) = 3 + 8/(-4) = 3 - 2 = 1. 9 tokens → 9 O(1) operations → O(n) time confirmed.

Reference implementation (bracket matching)

boolean isBalanced(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
    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;
        }
    }
    return stack.isEmpty();
}

Pitfalls

• Forgetting the final emptiness check — "(()" never fails a pop, but the stack isn't empty at the end; skipping that check wrongly reports balanced.
• Counting instead of stacking — per-type counters pass "([)]" (every count balances) even though the nesting order is wrong; only a stack enforces that the most recent opener matches the current closer.
• Popping an empty stack — an unmatched closer like ")(" must be checked with isEmpty() before popping, or it throws / silently underflows.
• Using recursion for arbitrarily deep nesting (e.g. DFS on a 100,000-node linear chain) — the call stack has a fixed OS-level size and overflows; an explicit heap-allocated stack does not.
• Confusing LIFO with priority — a stack always returns the most *recent* item, not the most important one; that needs a heap/priority queue instead.

When to use / when not — vs. Queue (BFS)

Use a stack when correctness depends on most-recent-first resolution: nested syntax, undo/redo, backtracking, DFS, call-frame management. Don't use a stack when you need shortest-path / level-order guarantees — a queue (FIFO) is the named alternative there, e.g. BFS finds the shortest unweighted path because it explores all distance-k nodes before any distance-(k+1) node, which a stack cannot guarantee (DFS may find *a* path but not the shortest one). Trade-off: DFS uses O(depth) space and is simple to implement recursively; BFS uses O(width) space, which can be far larger on wide shallow graphs, but is required whenever "first found = shortest" matters.

Takeaways

• Stacks solve problems whose structure is nested or reversible — the operator/bracket/call that opened last must close first.
• Converting an O(n²) rescan-and-delete approach into a single O(n) pass is the recurring stack win: one push/pop per element, no re-scanning.
• Recursion *is* an implicit stack; reach for an explicit one when recursion depth is unbounded or you need to inspect/modify the pending frames.
• Pick stack vs. queue by what "first" needs to mean: most recent (stack) or earliest discovered (queue).

Recall: Why does DFS with an explicit stack use O(depth) space in the best case but can use O(V) space in the worst case?

Synthesized from stack/DFS complexity analysis and postfix-evaluation mechanics; verify against your course's specific graph-representation assumptions (adjacency list vs matrix) when computing DFS space bounds.