Stack (LIFO) Complete Guide

Data Structure • easy

Stack is LIFO (last-in, first-out). The newest item is always removed first.

It maps naturally to nested structure handling: expressions, undo history, recursion simulation, and syntax validation.

When a problem needs 'most recent unresolved item', stack is usually the right fit.

Typical Complexity Baseline

Metric	Value
Push/pop/top	`O(1)`

See It

Concept Diagram

A small animated SVG that illustrates the core idea the moving parts you need to keep in your head when you read the rest of the guide.

Stack LIFO push and pop

Both ends touch the top. Watch a value push on, sit briefly, then pop off.

Step 1/13Validate '({[]})' push every open, pop on close, check match.

Speed

Watch First

Video Explainer

A quick visual walkthrough before the detailed sections pick the format that helps you learn fastest.

Learn Stack data structures in 10 minutes

Channel: Bro Code

Watch on YouTube →

Mechanics

Core Concepts

The building blocks and terminology you need before everything else clicks. Skim or deep-read.

Top

What it is Current most recent element.

Why it matters Top is a required building block for understanding how Stack (LIFO) stays correct and performant on large inputs.

Push

What it is Insert new item on top.

Why it matters Push is a required building block for understanding how Stack (LIFO) stays correct and performant on large inputs.

Pop

What it is Remove and return top item.

Why it matters Pop is a required building block for understanding how Stack (LIFO) stays correct and performant on large inputs.

Peek

What it is Read top item without removal.

Why it matters Peek is a required building block for understanding how Stack (LIFO) stays correct and performant on large inputs.

Monotonic invariant

What it is Optional ordering rule used in many optimization problems.

Why it matters Monotonic invariant is a required building block for understanding how Stack (LIFO) stays correct and performant on large inputs.

LIFO

What it is Last item added is first item removed.

Why it matters Last item added is first item removed. In Stack (LIFO), this definition helps you reason about correctness and complexity when inputs scale.

Monotonic Stack

What it is Stack that stays increasing/decreasing to optimize comparisons.

Why it matters Stack that stays increasing/decreasing to optimize comparisons. In Stack (LIFO), this definition helps you reason about correctness and complexity when inputs scale.

Sentinel

What it is Dummy value to simplify boundary handling.

Why it matters Dummy value to simplify boundary handling. In Stack (LIFO), this definition helps you reason about correctness and complexity when inputs scale.

Underflow

What it is Pop/peek attempted on empty stack.

Why it matters Pop/peek attempted on empty stack. In Stack (LIFO), this definition helps you reason about correctness and complexity when inputs scale.

Call stack

What it is Runtime-managed stack of active function frames.

Why it matters Runtime-managed stack of active function frames. In Stack (LIFO), this definition helps you reason about correctness and complexity when inputs scale.

Walkthrough

Putting It All Together

Every frame of the concept diagram, laid out top-to-bottom so you can scroll through the algorithm at your own pace.

Step 1/13

Validate '({[]})' push every open, pop on close, check match.

Step 2/13

Read '('. push.

Step 3/13

Read '{'. push.

Step 4/13

Read '['. push. Top = '['.

Step 5/13

Read ']'. pop returns '[' matches → ok.

Step 6/13

Read '}'. pop returns '{' matches → ok.

Step 7/13

Read ')'. pop returns '(' matches → ok.

Step 8/13

Input consumed and stack empty → balanced. Now a different example: undo history.

Step 9/13

User types A → push action onto undo stack.

Step 10/13

User types B → push.

Step 11/13

User types C → push.

Step 12/13

User hits Cmd-Z → pop returns the most recent action ('typed-C') to undo.

Step 13/13

Cmd-Z again → pop 'typed-B'. LIFO is exactly what undo needs.

Tradeoffs

How It Compares

When this technique wins, when it loses, and what to reach for instead.

vs. Queue

Choose this when Choose stack when most-recent-first semantics are required.

Tradeoff Queue is better for first-in-first-out processing.

vs. Recursion

Choose this when Choose explicit stack when recursion depth may exceed safe limits.

Tradeoff Recursion can be cleaner for tree-like code.

vs. Array scan

Choose this when Choose stack when unresolved prior states must be revisited.

Tradeoff Simple scan is better when no backtracking state is needed.

In Production

Real-World Stories

Where this shows up at real companies and what the on-call engineer learned the hard way.

Google

Compiler and parser stacks track nested syntax while converting source code into internal representations.

Takeaway Nested language constructs map directly to stack operations.

Figma

Undo/redo stacks maintain operation history for interactive editing sessions.

Takeaway LIFO behavior provides intuitive user-facing history controls.

Browsers

JavaScript engines and layout systems track nested execution and traversal states with stack structures.

Takeaway Stacks are foundational for runtime correctness.

Code

Implementation

A clean reference implementation in TypeScript, Python, and Go. Switch languages with the toggle.

Push open brackets, pop on close bracket, and ensure expected pair type.

Complexity: Time O(n), Space O(n)

Valid parentheses with stack

Language

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
}

Watch Out

Common Problems and Failure Modes

The bugs and edge cases that bite engineers most often. Skim before you ship.

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.

Pro Tips

Tips and Tricks

Small habits that pay off every time you reach for this pattern.

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.

Pattern Recognition

When to Use

Concrete signals that tell you this is the right pattern both at work and on LeetCode.

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 (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.

Practice

LeetCode Progression

A curated easy-to-hard problem ladder. Each one reinforces a specific aspect of the pattern.

#	Problem	Difficulty	Typical Complexity
1	Valid Parentheses	Easy	`O(n)`
2	Implement Stack using Queues	Easy	`O(n)` worst push
3	Min Stack	Medium	`O(1)` ops
4	Evaluate Reverse Polish Notation	Medium	`O(n)`
5	Daily Temperatures	Medium	`O(n)`
6	Car Fleet	Medium	`O(n log n)`
7	Largest Rectangle in Histogram	Hard	`O(n)`
8	Trapping Rain Water	Hard	`O(n)`
9	Basic Calculator	Hard	`O(n)`
10	Remove K Digits	Hard	`O(n)`