Stack (LIFO)

O(n)

Push each item as you see it; when something needs to match its most recent unmatched partner, pop and compare. The last thing pushed is always the first thing checked (last in, first out).

Signals

valid parentheses / balanced bracketsmatch the most recent open with the next closeundo, backtrack to the last state, nested structureevaluate an expression with nested operatorsprocess in reverse order of arrival

Template

function isValid(s) {
    const stack = [];
    const pairs = { ')': '(', ']': '[', '}': '{' };
    for (const ch of s) {
        if (ch in pairs) {
            if (stack.pop() !== pairs[ch]) return false;
        } else {
            stack.push(ch);
        }
    }
    return stack.length === 0;
}

Looks similar, isn't

Monotonic stack: A plain stack only needs to match open/close pairs in the order they came in, popping on a direct match. A monotonic stack is a different job: it keeps its elements sorted while popping to find each element's next-greater or next-smaller neighbour.

n up to 1e5 characters/tokens -> O(n): each item is pushed once and popped at most once.

Learn this pattern