Chapter 09 — Stacks

Chapter 09 — Stacks

Hey everyone! Welcome back to Namaste DSA!

A stack is the simplest structure with a big personality: Last In, First Out (LIFO). Think of a pile of plates — you add to the top and take from the top. This one rule powers undo buttons, the browser back button, expression evaluation, and the call stack itself.

What we will cover:

• LIFO and the core operations
• Implementing a stack (JS array)
• Valid parentheses
• Monotonic stack — next greater element
• Where stacks show up in real life
• Interview Questions

---

1. LIFO — Last In, First Out

┌─────────────────────────────────────────────────────────────┐
│            STACK (pile of plates)                           │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│   push(C) →   ┌───┐  ← top (pop takes this first)           │
│               │ C │                                         │
│               ├───┤                                         │
│               │ B │                                         │
│               ├───┤                                         │
│               │ A │  ← bottom (first one in)                │
│               └───┘                                         │
│                                                             │
│   push → add to top      pop → remove from top              │
│   peek → look at top     all O(1)                           │
└─────────────────────────────────────────────────────────────┘

---

2. Implementing a Stack

In JavaScript an array IS a stack — push and pop already work on the end (both O(1)).

const stack = [];
stack.push(10);     // [10]
stack.push(20);     // [10, 20]
stack.peek = () => stack[stack.length - 1];  // 20
stack.pop();        // returns 20 → [10]
stack.length === 0  // isEmpty check

---

3. Valid Parentheses

Classic problem: is "({[]})" balanced? Push opening brackets; when you hit a closing bracket, the top of the stack must be its match.

function isValid(s) {
    const stack = [];
    const pairs = { ")": "(", "]": "[", "}": "{" };
    for (const c of s) {
        if (c === "(" || c === "[" || c === "{") {
            stack.push(c);                 // opening → push
        } else {
            if (stack.pop() !== pairs[c]) return false;  // mismatch
        }
    }
    return stack.length === 0;             // nothing left over
}

HAND TRACE: "({[]})"
  '(' push → [ ( ]
  '{' push → [ (, { ]
  '[' push → [ (, {, [ ]
  ']' pop → '[' matches ✔ → [ (, { ]
  '}' pop → '{' matches ✔ → [ ( ]
  ')' pop → '(' matches ✔ → [ ]
  stack empty → true ✔

---

4. Monotonic Stack — Next Greater Element

A monotonic stack keeps its elements in sorted order (increasing or decreasing). It answers "what's the next bigger element to the right?" for every item in O(n).

function nextGreater(arr) {
    const result = new Array(arr.length).fill(-1);
    const stack = [];                  // stores INDICES
    for (let i = 0; i < arr.length; i++) {
        // while current is bigger than the top's value, it's their answer
        while (stack.length && arr[i] > arr[stack[stack.length - 1]]) {
            const idx = stack.pop();
            result[idx] = arr[i];
        }
        stack.push(i);
    }
    return result;
}

HAND TRACE: nextGreater([2, 1, 3])

  i=0 (2): stack empty → push 0        stack=[0]
  i=1 (1): 1 > 2? no → push 1          stack=[0,1]
  i=2 (3): 3 > arr[1]=1? yes → result[1]=3, pop
           3 > arr[0]=2? yes → result[0]=3, pop
           push 2                       stack=[2]
  result = [3, 3, -1] ✔

Each index is pushed and popped at most once → O(n), even with the inner while loop.

---

5. Where Stacks Show Up

✔ Undo / Redo           — push each action, pop to undo
✔ Browser back button   — pages stack up
✔ Function call stack   — every function call pushes a frame
✔ Expression evaluation — converting/evaluating math
✔ DFS (Chapter 18)      — iterative DFS uses a stack
✔ Balanced brackets     — compilers check your code this way

---

Interview Questions — Quick Fire!

Q: What is a stack and what does LIFO mean?

"A stack is a linear structure where you add and remove from the same end, the top. LIFO means Last In, First Out — the most recently added item is the first one removed, like a pile of plates. Push, pop, and peek are all O(1)."

Q: How do you check for balanced parentheses?

"Scan the string; push every opening bracket. On a closing bracket, pop the stack and confirm it's the matching opener — if not, it's invalid. At the end the stack must be empty. It's O(n) time and O(n) space."

Q: What is a monotonic stack?

"A stack whose elements are kept in increasing or decreasing order by popping violators before pushing. It solves 'next greater/smaller element' type problems in O(n), because each element is pushed and popped at most once."

Q: How is the call stack related to a stack data structure?

"It literally is one. Each function call pushes a frame holding its local variables and return address; when the function returns, its frame is popped. That LIFO behaviour is why recursion unwinds in reverse order."

---

Quick Recap

Concept	Key Takeaway
LIFO	Last in, first out — add/remove at top.
Operations	push, pop, peek — all O(1).
JS array	push/pop already give you a stack.
Valid parens	Push openers, match on close.
Monotonic stack	Next greater/smaller in O(n).

What's Next?

Chapter 10: Queues & Deques — the FIFO cousin of the stack, and the engine that powers BFS (Breadth-First Search) in Chapter 18.

Keep coding, keep grinding! See you in the next one!