Stacks and Queues

Stacks and queues are the first structures where you understand why the order of processing matters as much as the contents being processed. A stack imposes LIFO order; a queue imposes FIFO order. Those two constraints, applied to the right problem, reduce complexity from quadratic to linear. The most underestimated result in this phase is the monotonic stack: a single-pass O(n) technique that eliminates nested loops for a whole class of problems that appear consistently on LeetCode and Codeforces.

---

1. Stack

LIFO — Last In, First Out

The most recently pushed element is the first to be popped. Think of a stack of plates.

Push 1, 2, 3:    │ 3 │  ← top
                 │ 2 │
                 │ 1 │
                 └───┘

Pop:   returns 3 first, then 2, then 1

Array-Backed Implementation

class Stack:
    arr = []      // underlying array
    top = -1      // index of top element

    push(x):      arr[++top] = x      // O(1)
    pop():        return arr[top--]   // O(1)
    peek():       return arr[top]     // O(1)
    isEmpty():    return top == -1    // O(1)

Using a dynamic array: push is O(1) amortized (resizing happens occasionally), pop is O(1).

Use Cases

Function call stack: Your program maintains a call stack. Each function call pushes a frame (local variables, return address). When the function returns, the frame is popped. Recursive algorithms use the call stack implicitly — knowing this means you understand why deep recursion causes stack overflow and why iterative solutions are sometimes necessary.

Expression evaluation: Convert infix to postfix (Shunting Yard algorithm uses a stack). Evaluate postfix expressions with a stack. Classic interview topic.

Backtracking: DFS traversal, maze solving, permutation generation — all push state onto a stack (either explicitly or via recursion) and pop when backtracking.

---

2. Queue

FIFO — First In, First Out

The first element pushed is the first to be removed. Think of a line at a counter.

Circular Buffer Implementation

Why naive array-backed queue wastes space:

Enqueue 1, 2, 3, then Dequeue 1, 2:
[_, _, 3, _, _, _, _, _, _, _]
         ▲                ▲
        front            back

front has moved right; the left portion is empty but can’t be reused. In a naive array queue, front only moves right — you run out of space even if there’s room.

Circular buffer fix: Treat the array as a ring. Use modular arithmetic.

class CircularQueue:
    arr = [None] * capacity
    front = 0
    back = 0
    size = 0

    enqueue(x):
        arr[back] = x
        back = (back + 1) % capacity   // wrap around
        size++

    dequeue():
        val = arr[front]
        front = (front + 1) % capacity
        size--
        return val

    isFull():   return size == capacity
    isEmpty():  return size == 0

All operations O(1). Space is always fully utilized.

In practice: Use a dynamic array-backed deque (Python collections.deque, Java ArrayDeque) which handles resizing. Know the circular buffer for interviews asking “implement a queue.”

Use Cases

BFS (Breadth-First Search): The canonical use. Enqueue the root, process level by level. BFS requires processing nodes in the order they were discovered — that’s FIFO.

Scheduling: OS scheduling queues (ready queue, I/O queue). Rate limiting (token bucket, sliding window rate limiter).

---

3. Deque (Double-Ended Queue)

A deque supports push/pop from both front and back, all O(1).

push_front(x), pop_front(), peek_front()
push_back(x),  pop_back(),  peek_back()

Java: ArrayDeque. Python: collections.deque. C++: std::deque.

Primary use case: The sliding window maximum problem (covered in Section 5). Also used in BFS with priority modifications and palindrome checks.

---

4. Monotonic Stack

This is where the real value is. The monotonic stack is a stack where elements are maintained in sorted order (either increasing or decreasing). It solves “next greater element” and “nearest smaller element” problems in O(n) instead of the brute-force O(n²).

The Canonical Problem: Next Greater Element

Problem: For each element in an array, find the next element to its right that is strictly greater. If none exists, output -1.

arr   = [2, 1, 5, 6, 2, 3]
result= [5, 5, 6,-1, 3,-1]

Brute force — O(n²):

for i in range(n):
    result[i] = -1
    for j in range(i+1, n):
        if arr[j] > arr[i]:
            result[i] = arr[j]
            break

Monotonic stack — O(n):

stack = []     // stores INDICES, not values
result = [-1] * n

for i in range(n):
    // while stack has elements AND current element is greater than stack top
    while stack and arr[i] > arr[stack[-1]]:
        idx = stack.pop()
        result[idx] = arr[i]   // arr[i] is the "next greater" for arr[idx]
    stack.append(i)

// Anything left in stack has no next greater element → result stays -1

Why is this O(n)?

Each element is pushed onto the stack exactly once and popped at most once. Total pushes + pops ≤ 2n operations. The while loop doesn’t make this O(n²) because the total number of pops across the entire outer loop is bounded by the total number of pushes, which is n.

This is the key insight: Amortized analysis. The total work across all iterations of the outer loop is O(n), not O(n) per outer iteration.

Monotonic Stack Invariant

After processing index i, the stack contains indices in the array whose “next greater element” has not yet been found, maintained in decreasing order of value from bottom to top.

Maintain this invariant: before pushing i, pop all indices whose “next greater” is arr[i].

Variants

Variant	Stack order	What you’re finding
Next Greater	Decreasing (bottom→top)	First larger element to the right
Next Smaller	Increasing (bottom→top)	First smaller element to the right
Previous Greater	Decreasing	First larger element to the left (iterate right→left)
Previous Smaller	Increasing	First smaller element to the left

LeetCode problems that use this pattern: #496 Next Greater Element I, #503 Next Greater Element II (circular), #739 Daily Temperatures, #84 Largest Rectangle in Histogram (hard, uses both left and right smaller), #85 Maximal Rectangle.

---

5. Monotonic Queue: Sliding Window Maximum

Problem (LeetCode #239): Given an array and window size k, find the maximum element in each window as it slides across the array.

Brute force: For each of n-k+1 windows, scan k elements: O(nk).

Monotonic deque: O(n).

dq = collections.deque()   // stores INDICES; front = largest element's index
result = []

for i in range(n):
    // Remove elements outside the window
    while dq and dq[0] < i - k + 1:
        dq.popleft()

    // Maintain decreasing order: remove smaller elements from back
    while dq and arr[dq[-1]] < arr[i]:
        dq.pop()

    dq.append(i)

    // Window is valid once we've seen k elements
    if i >= k - 1:
        result.append(arr[dq[0]])   // front of deque is always the max

Invariant: The deque always contains indices of elements that are candidates for being the maximum of a future window — in decreasing order of value from front to back.

When a new element arrives:

1. Evict expired indices from the front (outside the window)

2. Remove from the back any indices whose values are ≤ new element (they can never be the max while the new element is in the window)

3. Append the new index

The front of the deque is always the maximum of the current window.

Why O(n)? Same argument as monotonic stack: each index is appended once and removed once. Total operations ≤ 2n.

---

6. Practice Problems

Easy

1. LeetCode #20 — Valid Parentheses (stack: push open brackets, pop and match on close)

2. LeetCode #232 — Implement Queue using Stacks (two-stack queue trick)

Medium

3. LeetCode #739 — Daily Temperatures (monotonic stack: next greater element variant)

4. LeetCode #150 — Evaluate Reverse Polish Notation (stack-based expression evaluation)

5. LeetCode #155 — Min Stack (design: constant-time getMin — two stacks or store (val, min_so_far) pairs)

Hard

6. LeetCode #84 — Largest Rectangle in Histogram (monotonic stack; requires finding left+right boundaries for each bar)

---

What Most Engineers Get Wrong

Not recognizing the monotonic stack pattern. If you see a problem that asks “for each element, find the nearest element to the left/right that is larger/smaller,” your immediate response should be “monotonic stack, O(n).” Many people write O(n²) nested loops because they don’t have this pattern locked. The tell: any time you have a for i loop and inside it you want to look backward or forward at other elements to find a threshold — that’s a monotonic stack candidate.

Secondary mistake: Using Python’s list as a deque (with .pop(0) for front removal). list.pop(0) is O(n) — it shifts all remaining elements. Use collections.deque for O(1) front operations, always.

---

Return to README.md · Next: 04_hash_tables.md