A stack follows LIFO — Last In, First Out.

Think Stack when you see:

• Next / previous relationships
• Nested structures
• Undo / history
• Min / max tracking
• Depth-first traversal

Quick Recognition Cheat Sheet

If you see…	Think…	Main Idea
Next/previous greater/smaller	Monotonic Stack	Keep increasing/decreasing order
Parentheses, expressions, undo	Stack Simulation	Push state, pop when completed/undone
getMin() / getMax() in O(1)	Min/Max Stack	Track running min/max
Depth-first traversal	DFS Stack	Replace recursion with explicit stack

---

1. Monotonic Stack

When to use

• Arrays
• Next/previous greater or smaller
• Nearest larger/smaller element

Why it works

Maintain the stack in increasing or decreasing order.

Pop elements when they no longer satisfy the required order.

This often reduces:

O(n²) → O(n)

Typical Questions

• Next Greater Element
• Next Smaller Element
• Stock Span
• Daily Temperatures
• Largest Rectangle in Histogram

Mental Trigger

Next/Previous + Greater/Smaller → Monotonic Stack

---

2. Stack Simulation

When to use

• Strings
• Parentheses/brackets
• Expressions
• Undo/history
• Nested structures

Why it works

A stack naturally handles nested dependencies and previous state.

Typical Questions

• Valid Parentheses
• Postfix/Prefix Expression
• Simplify Path
• Undo/Redo
• Browser History Simulation

Mental Trigger

Nested + Undo/History → Stack Simulation

---

3. Min/Max Stack

When to use

The problem asks for:

• getMin() in O(1)
• getMax() in O(1)
• Min/max after push/pop

Why it works

Track the current min/max using:

• An auxiliary stack, or
• A value + min/max pair

Typical Questions

• Design Min Stack
• Design Max Stack

Mental Trigger

Min/Max + O(1) → Track State in Stack

---

4. DFS Using Stack

When to use

• Trees
• Graphs
• Depth-first traversal
• Avoiding recursion

Why it works

An explicit stack mimics the recursive call stack.

Typical Questions

• Graph DFS
• Iterative Tree Traversal
• Path Existence
• Connected Components

Mental Trigger

Depth-First → Stack

---

Quick Decision Guide

Next / Previous + Greater / Smaller
        ↓
   Monotonic Stack

Parentheses / Expression / Undo / Nested
        ↓
   Stack Simulation

getMin() / getMax() in O(1)
        ↓
    Min/Max Stack

Depth-First / Replace Recursion
        ↓
      DFS Stack