Unit 3: Stacks, Queues & Recursion

Industry Hook — The Real-World Problem First

Concept Explanation — Theory, Earned

2.1 Stacks — Last In, First Out (LIFO)

Layer 1 — Intuition

A stack is a pile of plates in a hostel mess. You can only add a plate on top (push) and remove the plate on top (pop). You can't pull a plate from the middle without toppling the pile. The last plate placed is the first one taken — LIFO.

Layer 2 — Visual: Array vs Linked List Representation

Array-based Stack
          top = 3
           ↓
┌─────┬─────┬─────┬─────┬─────┬─────┐
│  5  │ 12  │  8  │  3  │     │     │  capacity = 6
└─────┴─────┴─────┴─────┴─────┴─────┘
  [0]   [1]   [2]   [3]   [4]   [5]

push(7):  arr[4] = 7, top = 4     → O(1)
pop():    return arr[3] = 3, top = 2  → O(1)

Linked-List-based Stack
  top
   ↓
┌─────┐   ┌─────┐   ┌─────┐   ┌─────┐
│  3  │──▶│  8  │──▶│ 12  │──▶│  5  │──▶ NULL
└─────┘   └─────┘   └─────┘   └─────┘

push(7):  Create node [7], [7].next = top, top = [7]  → O(1)
pop():    return top.data, top = top.next               → O(1)
(Push/pop always at the HEAD — that's why it's O(1))

Layer 3 — Complexity Table

2.2 Arithmetic Expressions & Polish Notation

Why does this matter?

When you type 3 + 5 * 2 in a calculator, how does it know to multiply first? Humans use parentheses and BODMAS rules, but computers need a stack-based algorithm to parse and evaluate expressions. This is how every compiler, interpreter, and calculator app works.

Three Expression Formats

Infix → Postfix Conversion (Shunting-Yard Algorithm)

Token   Action                           Stack        Output
─────   ──────                           ─────        ──────
A       Operand → output                 (empty)      A
+       Push (stack empty)               +            A
B       Operand → output                 +            A B
*       * > + precedence → push          + *          A B
C       Operand → output                 + *          A B C
-       - ≤ * → pop * to output          +            A B C *
        - ≤ + → pop + to output          (empty)      A B C * +
        push -                           -            A B C * +
D       Operand → output                 -            A B C * + D
END     Pop remaining                    (empty)      A B C * + D -

Result: A B C * + D -   ✓

Postfix Evaluation using Stack

Token   Action              Stack
─────   ──────              ─────
3       Push                [3]
5       Push                [3, 5]
2       Push                [3, 5, 2]
*       Pop 2,5 → 5*2=10   [3, 10]
+       Pop 10,3 → 3+10=13 [13]

Result: 13  ✓

2.3 Queues — First In, First Out (FIFO)

Layer 1 — Intuition

A queue is the line at a Swiggy delivery counter. The first order placed is the first one prepared and delivered. New orders join at the rear; completed orders leave from the front. No cutting in line!

Layer 2 — Visual

Array-based Queue (Circular)
  front=1          rear=4
     ↓                ↓
┌─────┬─────┬─────┬─────┬─────┬─────┐
│     │ 20  │ 30  │ 40  │ 50  │     │
└─────┴─────┴─────┴─────┴─────┴─────┘
  [0]   [1]   [2]   [3]   [4]   [5]

Enqueue(60): rear = (4+1) % 6 = 5, arr[5] = 60
Dequeue():   return arr[1]=20, front = (1+1) % 6 = 2

Circular trick: rear = (rear + 1) % capacity
This reuses space when front advances, avoiding the "false full" problem.

Priority Queue & Deque

2.4 Recursion: Divide, Conquer, Combine

Layer 1 — Intuition

Recursion is like Russian nesting dolls (Matryoshka). Open the big doll — inside is a smaller doll. Open that — even smaller. Keep opening until you find the tiny solid doll (base case). Then you "close" them back up in reverse order (returning from recursive calls). Each doll is the same shape, just smaller — that's the recursive structure.

The Three Laws of Recursion

1. Base Case: A condition where the function stops calling itself (the tiny doll)
2. Recursive Case: The function calls itself with a SMALLER problem
3. Progress: Each call must move TOWARD the base case

Merge Sort — O(n log n) guaranteed

Visual
          [38, 27, 43, 3, 9, 82, 10]
                    /          \
        [38, 27, 43, 3]    [9, 82, 10]        ← DIVIDE
          /        \         /       \
     [38, 27]  [43, 3]   [9, 82]   [10]       ← DIVIDE
      /   \     /   \     /   \      |
    [38] [27] [43]  [3] [9] [82]   [10]       ← BASE CASE (size 1)
      \   /     \   /     \   /      |
     [27, 38]  [3, 43]   [9, 82]   [10]       ← MERGE
          \      /           \      /
       [3, 27, 38, 43]    [9, 10, 82]         ← MERGE
                \            /
         [3, 9, 10, 27, 38, 43, 82]            ← MERGE (final)

Quick Sort — average O(n log n), worst O(n²)

Visual
Pivot = last element. Partition: elements ≤ pivot go left, > pivot go right.

     [10, 80, 30, 90, 40, 50, 70]     pivot = 70
      ↓   ↓   ↓   ↓   ↓   ↓   ↓
     [10, 30, 40, 50] [70] [80, 90]   ← After partition

Then recursively sort left [10,30,40,50] and right [80,90].