Stack (LIFO) Complete Guide

Video Explainer

Prefer video learning? This explainer gives a quick visual walkthrough of the core idea before you dive into the detailed sections below.

Core Concepts

Learn the core building blocks and terminology in one place before comparisons, so the mechanics are clear and duplicates are removed.

How It Compares

Real-World Stories and Company Examples

Valid parentheses with stack

function isValidParentheses(text: string): boolean {
  const stack: string[] = []
  const expectedOpenByClose: Record<string, string> = { ')': '(', ']': '[', '}': '{' }

  for (const char of text) {
    if (char === '(' || char === '[' || char === '{') {
      stack.push(char)
      continue
    }
    const expectedOpen = expectedOpenByClose[char]
    if (!expectedOpen) continue
    if (stack.pop() !== expectedOpen) return false
  }

  return stack.length === 0
}

Common Problems and Failure Modes

• Popping without checking empty state.
• Using stack where queue semantics are needed.
• Missing equal-value handling in monotonic stack logic.
• Confusing character index with character value in parser tasks.
• Recursive solution without depth safeguards.

Tips and Tricks

• Stack is the default choice for 'most recent unresolved item' problems.
• For monotonic stack questions, decide monotonic direction first, then implement push/pop rules.
• Use sentinel values to simplify empty-stack edge conditions.
• If recursion depth might explode, convert recursion to explicit stack iteration.

When to Use

Use these signals to decide if this data structure/algorithm is the right fit before implementation.

Real-system usage signals

• Simple push/pop API with O(1) operations.
• Natural model for nested parentheses and parser state.
• Useful for monotonic patterns and backtracking breadcrumbs.

LeetCode-specific tips (including pattern-identification signals)

• Identification signal: last opened item must close first (parentheses, nested structures, undo/history behavior).
• Identification signal: you need to process nearest previous/next greater-smaller relationships while scanning once.
• If the solution needs push/pop symmetry with strict LIFO order, choose stack before queue or map.
• For Stack (LIFO) questions, start by naming the core invariant before writing code.
• Use the constraint section to set time/space target first, then pick the data structure/algorithm.
• Solve one tiny example by hand and map each transition to your variables before implementing.
• Run adversarial cases: empty input, duplicates, max-size input, and sorted/reverse patterns when relevant.
• During interviews, explain why your approach is the right pattern for this prompt, not just why the code works.