parikshan

Stack

The core idea

A stack remembers the most recent unfinished thing. Whenever a problem asks you to match, nest, or "find the next one that ...", the most recent unfinished thing is exactly what you need to know. Stacks are O(1) for push, pop, and peek, and a problem solved by a stack almost always finishes in a single linear pass.

Three sub-patterns:

  1. Matching: open brackets push; close brackets pop and check the match.
  2. Monotonic stack: keep the stack sorted (increasing or decreasing). When a new element breaks the order, pop until it is restored. Powers all "next greater / next smaller" problems.
  3. Expression evaluation: operands push; operators pop two and push the result. The classic abstract machine for postfix expressions.

When to reach for it

Trigger phrases:

  • "nested / matching ..."
  • "next greater element" / "next smaller"
  • "largest rectangle in histogram"
  • "valid parentheses / valid expression"
  • "evaluate / parse"
  • "undo / backtrack one step"

If you find yourself wanting to look "backwards" but only at the most recent unmatched event, a stack is the right data structure.

How to approach

  1. Decide what each entry on the stack represents. Index, value, or pair?
  2. State the invariant: at every step, what is true about the stack?
  3. Walk the input. For each element, first pop while the invariant would be violated, then push.
  4. After the loop, the stack often contains the "unanswered" elements; decide what to do with them.

Real-world applications

  • Compilers and interpreters: every expression you've ever written was parsed with stacks.
  • Function call stack: literal stack inside every program.
  • Undo systems in editors and IDEs.
  • Browser back button (well, a stack until the user diverges, then a tree).
  • HTML / XML validators: bracket matching, in spirit.
  • Pathological-string detectors in security: detecting unbalanced inputs that try to break parsers.

In the AI-integrated workspace

The agent error here is reaching for a stack when a single counter would do, and reaching for a counter when a stack is required. For example, "valid parentheses" with a single bracket type is a counter problem; with three bracket types it is a stack problem. The agent will often write the stack version when a counter would suffice, which wastes memory but is correct; the inverse error (counter where stack is needed) is silently wrong on inputs like "([)]". Read every "balanced" solution and ask: "Does this distinguish bracket types?".

Monotonic-stack code is dense and prone to off-by-one errors. The two things to check in code review: (1) the stack stores indices, not values, when distances matter, and (2) elements left on the stack at the end are handled. Both are common omissions in generated code.

Problems in this cluster

Easy: valid-parentheses, next-greater-element-i, implement-queue-using-stacks. Medium: min-stack, evaluate-reverse-polish-notation, generate-parentheses, daily-temperatures.

Start with valid-parentheses. It is the canonical stack problem and the deep article walks the discovery in full.