Stack and LIFO Thinking

A stack is the data structure for unfinished work where the most recent item must be handled first. That one rule explains function calls, undo stacks, browser back buttons, syntax parsing, expression evaluation, and many interview problems that look unrelated at first.

The LIFO Mental Model

LIFO means last in, first out. Push adds work to the top. Pop removes the most recent work. Peek reads the next item without removing it. The key question is whether the most recent unresolved item is the one you must compare, close, undo, or continue.

Scenario: Editor Undo and Nested UI State

A document editor records user actions: type text, format paragraph, move block, delete image. Undo must reverse the most recent action first. Redo must reapply the most recently undone action first. Two stacks model this cleanly: an undo stack and a redo stack.

Same Pattern in Java, Python, and JavaScript

Balanced bracket validation is the canonical stack example. Every closing bracket must match the latest unmatched opening bracket.

import java.util.*;

class ValidBrackets {
    static boolean isValid(String text) {
        Map<Character, Character> closeToOpen = Map.of(')', '(', ']', '[', '}', '{');
        Deque<Character> stack = new ArrayDeque<>();
        for (char ch : text.toCharArray()) {
            if (ch == '(' || ch == '[' || ch == '{') stack.push(ch);
            else if (closeToOpen.containsKey(ch)) {
                if (stack.isEmpty() || stack.pop() != closeToOpen.get(ch)) return false;
            }
        }
        return stack.isEmpty();
    }
}

Monotonic Stack Preview

A monotonic stack keeps values in increasing or decreasing order while scanning. It is useful when each new item resolves previous unresolved items, such as next greater element, daily temperatures, stock span, and histogram area. The invariant matters more than the syntax.

Interview signalFrequently Asked Interview Questions

These are canonical interview patterns for this topic, phrased as concrete problem statements. They avoid vague theory questions and prepare you for the exact reasoning interviewers expect: invariant, edge cases, complexity, and trade-off.

• Given a string containing brackets, return whether every closer matches the latest unmatched opener.
• Implement a stack that supports push, pop, top, and getMin in O(1).
• For each day, return how many days until a warmer temperature.

Production practiceCompany-Style Practice Examples

These are not claimed as exact company-specific questions. They are the interview patterns repeatedly used by product companies to test whether you can move from brute force to a defensible implementation.

Solved modelInterview Question Solutions

import java.util.*;

class Brackets {
    static boolean valid(String s) {
        Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
        Deque<Character> stack = new ArrayDeque<>();
        for (char ch : s.toCharArray()) {
            if (ch == '(' || ch == '[' || ch == '{') stack.push(ch);
            else if (pairs.containsKey(ch) && (stack.isEmpty() || stack.pop() != pairs.get(ch))) return false;
        }
        return stack.isEmpty();
    }
}

import java.util.*;

class MinStack {
    private final Deque<Integer> values = new ArrayDeque<>();
    private final Deque<Integer> mins = new ArrayDeque<>();
    void push(int value) { values.push(value); if (mins.isEmpty() || value <= mins.peek()) mins.push(value); }
    void pop() { int removed = values.pop(); if (removed == mins.peek()) mins.pop(); }
    int top() { return values.peek(); }
    int getMin() { return mins.peek(); }
}

import java.util.*;

class DailyTemperatures {
    static int[] solve(int[] t) {
        int[] ans = new int[t.length];
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < t.length; i++) {
            while (!stack.isEmpty() && t[i] > t[stack.peek()]) { int prev = stack.pop(); ans[prev] = i - prev; }
            stack.push(i);
        }
        return ans;
    }
}

Solved modelWorked Interview Answer

Validate bracket pairs using the latest unmatched opener. A closing bracket must match the most recent unresolved opening bracket, which is exactly stack behavior.

import java.util.*;

class Brackets {
    static boolean valid(String s) {
        Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
        Deque<Character> stack = new ArrayDeque<>();
        for (char ch : s.toCharArray()) {
            if (ch == '(' || ch == '[' || ch == '{') stack.push(ch);
            else if (pairs.containsKey(ch) && (stack.isEmpty() || stack.pop() != pairs.get(ch))) return false;
        }
        return stack.isEmpty();
    }
}

Hands-on drillTry It Yourself

Failure patternsCommon Mistakes to Avoid

• Using a stack without proving latest-unresolved behavior.
• Forgetting to check empty stack before pop.
• Returning true while unmatched openers remain.
• Using recursion accidentally when explicit stack depth should be controlled.

Execution guardrailQuick-Start Checklist

• Define what each stack item represents.
• Push unresolved work.
• Compare or resolve only against the top.
• Pop exactly when work is completed.
• State time and maximum stack size.

Recall drillKnowledge Check

VocabularyKey Terms

Next practiceFurther Reading

• Practice valid parentheses, min stack, next greater element, and daily temperatures.
• Review browser history and undo stacks as product examples.
• Study monotonic stack patterns before histogram problems.