1. The "Implicit" Stack: Recursion & Backtracking

Used in: Trees, Graphs (DFS), Dynamic Programming (Top-Down)

Every time you write a recursive function, the computer uses a System Stack (Call Stack) in the background. It pauses the current function, saves its variables (state), and pushes a new "frame" on top.

How it works:

1. Push: When you call recursive(n-1), the current state n is paused and pushed onto the stack.
2. Base Case: The condition where you stop pushing (e.g., n == 0).
3. Pop: Once the base case returns, the stack pops the top frame, resuming the previous function exactly where it left off.

Example: Factorial(3)

• fact(3) calls fact(2) $\rightarrow$ PUSH
• fact(2) calls fact(1) $\rightarrow$ PUSH
• fact(1) returns 1 $\rightarrow$ POP (returns to fact(2))
• fact(2) computes $2 \times 1$ $\rightarrow$ POP (returns to fact(3))

Relevance to Interviews:

• DFS: Uses this exact mechanism to traverse deep into a graph/tree and backtrack when it hits a dead end.
• Backtracking: You rely on the stack to "undo" choices automatically when a function returns (e.g., N-Queens, Sudoku).

---

2. The "Explicit" Stack: Iterative DFS

Used in: Graphs, Trees

Sometimes you want to avoid recursion (to avoid Stack Overflow errors) or you need more control. You can manually create a Stack data structure to mimic the recursion above.

The DFS Pattern (Iterative):

1. Push the starting node.
2. While stack is not empty:
   • Pop the top node (current).
   • Process it (e.g., print it).
   • Push all unvisited neighbors.

Why this matters:

• This is the standard pattern for Graph Traversal.
• In a Grid (Maze) problem, the stack holds the path you have taken so far. If you hit a wall, you pop (backtrack) to the previous cell.

---

3. The "Monotonic" Stack: Array Optimization

Used in: Array Problems (Next Greater Element, Histogram)

This is a specific pattern where you keep elements in the stack sorted (either increasing or decreasing).

The Logic:

• You want to find the "Next Greater Element" for every number in an array.
• Iterate through the array.
• While the current number is greater than the number at the top of the stack:
  • Pop the stack. The current number is the "Next Greater" for the popped element.
• Push the current number.

Visualizing it: Imagine a line of people. You want to see who is taller than you to your right. If a short person stands in front of a tall person, the short person is "invisible" to anyone looking from the left. The stack removes these "invisible" (useless) elements.

Key Problems:

• Daily Temperatures (LeetCode 739)
• Largest Rectangle in Histogram (LeetCode 84)

---

4. Stacks in Dynamic Programming (DP)

Used in: Understanding Top-Down vs. Bottom-Up

• Top-Down DP (Memoization): This is literally just Recursion + a Cache. It uses the Call Stack (see #1). You dive deep into the subproblems using the stack until you hit the base case, then bubble up the answers.
• Bottom-Up DP (Tabulation): This technique removes the stack entirely. Instead of using stack memory to hold the state, you use an Array or Matrix (dp[]). You fill the table iteratively (0 to N).

Insight:

Often, converting a recursive solution to an iterative DP solution is just asking: "How can I fill a table so I don't need this expensive stack memory?"

Summary Checklist