Stack — when you need the most recent unresolved thing

A stack is last-in, first-out: the only item you can reach is the one you added most recently. That's exactly the shape you want whenever the next thing to resolve is always the most recent unresolved one. Matching brackets is the clean example — when you hit a closing bracket, it has to pair with the most recent still-open one, which is sitting right on top. Push openers, pop on a match; if the top doesn't match, the string is invalid.

The vocabulary, defined once

Every word in this lesson points at a precise, simple idea. Pin them down now and the rest reads itself.

• Stack — an ordered collection where insertions and removals happen at one end only, called the top. In most languages it is just a plain dynamic array (Python list, JS array) used through a restricted set of operations; the discipline, not the data type, is what makes it a stack.
• LIFO — "last in, first out": the most recently added item is the first one removed. Contrast with a queue, which is FIFO ("first in, first out", like a line at a checkout).
• Push — add an item onto the top. In Python that is st.append(x); in JS st.push(x). Cost: O(1) amortized.
• Pop — remove and return the top item. Python st.pop(), JS st.pop(). Cost: O(1). Popping an empty stack is an error you must guard against.
• Peek (a.k.a. top) — look at the top item without removing it. Python st[-1], JS st[st.length - 1]. Use it when you need to inspect before deciding whether to pop.
• Top — the position (and the item) at the open end of the stack; "peek" is the act of reading it.
• Matching / balanced parentheses — a string of bracket characters in which every opener (( [ {) has a corresponding closer () ] }) of the same kind, and pairs are properly nested (you never close an outer bracket while an inner one is still open). ([]) is balanced; ([)] is not.
• Expression evaluation — computing the value of something like 3 + 4 * 2 or its parenthesized / postfix forms. Stacks hold pending operands and operators until precedence says it's time to apply them.
• Monotonic stack (previewed below) — a stack you deliberately keep sorted in one direction (always increasing or always decreasing) by popping anything that would break the order before you push. It is the engine behind "next greater element" and similar problems.

The call stack — the stack you already use

You have been relying on a stack since your very first function call. When your program calls a function, the runtime pushes a stack frame onto the call stack — a record holding that call's local variables and the spot to return to when it finishes. Call another function from inside, and a new frame is pushed on top. When a function returns, its frame is popped, and control resumes in the frame now exposed at the top. This is pure LIFO: the most recently entered function is always the next to finish. That is also why deep, unbounded recursion crashes with a "stack overflow" — you pushed more frames than the call stack can hold. Understanding this makes the next idea click: any recursive algorithm can be rewritten with an explicit stack you manage by hand, because all you are doing is reproducing the call stack's LIFO bookkeeping yourself.

def is_valid(s):
    pair = {')':'(', ']':'[', '}':'{'}
    st = []
    for ch in s:
        if ch in pair:
            if not st or st.pop() != pair[ch]:
                return False
        else:
            st.append(ch)
    return not st

function isValid(s: string): boolean {
  const pair: Record<string,string> = {")":"(", "]":"[", "}":"{"};
  const st: string[] = [];
  for (const ch of s) {
    if (ch in pair) { if (st.pop() !== pair[ch]) return false; }
    else st.push(ch);
  }
  return st.length === 0;
}

Reading the template line by line

The whole solution is nine lines, and each one earns its place. pair is the lookup that turns the question "what opener does this closer need?" into a single O(1) dictionary read — keying on closers means ch in pair doubles as the test "is this character a closer?". st is the stack of openers we have seen but not yet closed. The loop visits each character once. If ch is a closer, we demand two things in one expression: the stack is non-empty (not st guards against a closer with no opener waiting) and the popped top equals the expected opener; failing either returns False. Otherwise ch is an opener, so we push it to wait for its partner. The final not st is the cleanup verdict: True only when nothing is left unmatched. Python's short-circuit or matters here — not st is checked before st.pop(), so we never pop an empty stack.

The canonical stack problem — write it and run it live:

The family of stack problems

Valid Parentheses is one member of a family. The shared DNA: at each step the thing you must act on is the most recent unresolved item, and a stack hands you that item in O(1). Learn to spot which member you are looking at.

• Matching / nesting — balanced brackets, valid HTML/XML tags, removing matched pairs. Push openers, pop on the corresponding closer. Same skeleton as the template above.
• Undo / linear backtracking — a text editor's undo, simplifying a Unix path (cd .. pops the last directory off the stack), processing "..." with backspaces. The most recent action is the first to reverse — LIFO again.
• DFS / iterative tree & graph traversal — replace the recursive call stack with your own. Push the start node; loop while the stack is non-empty: pop a node, process it, push its unvisited neighbors. The explicit stack reproduces recursion's depth-first order without risking a stack-overflow on deep inputs.
• Expression evaluation — evaluate (2 + 3) * 4 or its postfix form 2 3 + 4 *. Keep one stack of operands (and, for infix, one of operators); when precedence or a closing paren says "apply now," pop the operands, apply the operator, push the result back. The shunting-yard algorithm is this idea fully fleshed out.
• Next-greater / next-smaller (monotonic stack) — "for each element, find the next one to its right that is larger." Walk the array keeping a stack of indices whose answers are still pending, in decreasing value order. Each new value pops every smaller value beneath it — that new value is their next-greater answer — then pushes itself. Each element is pushed and popped at most once, so the whole sweep is O(n) even though it feels like a nested search. Stock-span, daily-temperatures, and largest-rectangle-in-histogram all run on this.

Recognition signals & pitfalls

Reach for a stack the moment a problem's phrasing carries one of these tells: "matching" or "nested" pairs; "most recent," "last," or "innermost"; "undo" or "previous unmatched"; "next greater/smaller/warmer/closer" element; or "evaluate an expression." If you find yourself wanting to peek backward at the most recent thing you have not finished with, that is a stack.