Chapter 7 — Stack & Queue

Two structures. Both are sequences. What differs is the rule for which element you can touch next.

Part 1: The Core Idea — Access Rules

Every data structure is defined by what operations it supports and what they cost. Arrays give you random access — reach any element in O(1). But sometimes random access is the wrong tool. Sometimes what you need is constrained access: you can only interact with one specific element, and only in a specific order.

Stack: You can only touch the element you added most recently. Last In, First Out. (LIFO)

Queue: You can only touch the element you added least recently. First In, First Out. (FIFO)

These constraints aren't limitations — they're the feature. Many real problems have natural LIFO or FIFO structure, and the constraint ensures you handle them in the right order.

Part 2: The Stack — Physical Reality

A stack is conceptually simple: a pile where you only interact with the top.

Operations:

• push(x) — add x to the top. O(1).
• pop() — remove and return the top element. O(1).
• peek() — return the top element without removing. O(1).
• isEmpty() — check if stack is empty. O(1).

In JavaScript, an array already gives you a stack via push and pop:

const stack = [];
stack.push(1);   // [1]
stack.push(2);   // [1, 2]
stack.push(3);   // [1, 2, 3]
stack.pop();     // returns 3, stack = [1, 2]
stack.pop();     // returns 2, stack = [1]

The rightmost end of the array is the "top" of the stack. push appends (O(1) amortized), pop removes from the end (O(1)). This is efficient because no shifting occurs.

Class implementation (for clarity):

class Stack {
  constructor() {
    this.data = [];
  }

  push(x) {
    this.data.push(x);
  }

  pop() {
    if (this.isEmpty()) throw new Error("Stack underflow");
    return this.data.pop();
  }

  peek() {
    if (this.isEmpty()) throw new Error("Stack is empty");
    return this.data[this.data.length - 1];
  }

  isEmpty() {
    return this.data.length === 0;
  }

  size() {
    return this.data.length;
  }
}

The physical metaphor: A stack of plates. You can only add or remove from the top. To get to a plate at the bottom, you must first remove all plates above it. This is why undo history, browser back button, and the call stack (Chapter 4) are stacks — the most recent action is always the first to be reversed.

Part 3: The Queue — Physical Reality

A queue is a line. First person in, first person served.

Operations:

• enqueue(x) — add x to the back. O(1).
• dequeue() — remove and return the front element. O(1).
• front() — return the front element without removing. O(1).
• isEmpty() — check if queue is empty. O(1).

The problem with naive array queues:

const queue = [];
queue.push(1);    // enqueue: O(1)
queue.push(2);
queue.shift();    // dequeue: O(n) — shifts every element left!

Array.prototype.shift() is O(n) because it moves every remaining element one position left in memory. For a queue processing 1 million items, this is catastrophic.

Why it's O(n): Arrays are contiguous in memory. When you remove the first element, the remaining n-1 elements must physically shift to fill the gap (or the base pointer advances, but V8 doesn't always do this optimization for small arrays). This is the same shifting cost we saw in Chapter 2 for insert/delete at the front.

Proper queue implementation — two-pointer (no shifting):

class Queue {
  constructor() {
    this.data = [];
    this.head = 0;  // index of front element
  }

  enqueue(x) {
    this.data.push(x);   // O(1) amortized
  }

  dequeue() {
    if (this.isEmpty()) throw new Error("Queue underflow");
    const val = this.data[this.head];
    this.head++;
    // Optional: compact when head advances far (to avoid memory leak)
    if (this.head > this.data.length / 2) {
      this.data = this.data.slice(this.head);
      this.head = 0;
    }
    return val;
  }

  front() {
    return this.data[this.head];
  }

  isEmpty() {
    return this.head >= this.data.length;
  }

  size() {
    return this.data.length - this.head;
  }
}

Now dequeue is O(1) — just advance head. The downside: the array grows and never shrinks (until compaction). For interview code, shift() is often acceptable with a note about its O(n) cost.

Circular buffer (production queue): Use a fixed-size array with head and tail indices that wrap around using modulo arithmetic. dequeue advances head % capacity. enqueue advances tail % capacity. O(1) for both, O(1) space overhead. Used in ring buffers in operating systems, network drivers.

Part 4: The Deque — Both Ends

A deque (double-ended queue, pronounced "deck") supports O(1) push and pop from both ends.

Operations: pushFront, pushBack, popFront, popBack, peekFront, peekBack.

We saw this in Chapter 6 (Sliding Window Maximum). JavaScript has no built-in deque, so we simulate it with an array and track indices — or use a doubly linked list for true O(1) both ends.

For most interview problems, array-as-deque with unshift/push/shift/pop is fine. But note:

• push / pop (back): O(1).
• unshift / shift (front): O(n) in arrays.

For LeetCode, this is usually accepted. For production, use a doubly linked list.

Part 5: Stack — What Problems It Solves

The stack's LIFO property solves problems where the most recent thing is the most relevant thing.

Pattern 1: Matching/Balancing

When you encounter an opening bracket (, push it. When you encounter a closing bracket ), the most recent unmatched opening bracket should match it — pop and check. If they don't match, invalid. If stack is empty when you see ), invalid.

This works because brackets nest: the innermost pair closes first (LIFO order).

Pattern 2: "Previous / Next Greater / Smaller Element"

For each element, find the nearest element (to the left or right) that is greater or smaller. Brute force: two loops, O(n²). With a stack (monotonic stack): O(n).

Pattern 3: Expression Evaluation

Evaluate 3 + 4 * 2. Two stacks: one for values, one for operators. Push values; when you see an operator, check precedence against the top of the operator stack. This is how compilers evaluate expressions.

Pattern 4: Undo / History

Every undo action: pop the last action from the stack and reverse it. Text editors, Photoshop, browser back button — all stacks.

Pattern 5: DFS Simulation

Depth-first search of a graph naturally uses a stack — either the call stack (recursive DFS) or an explicit stack (iterative DFS). Push unvisited neighbors, pop to visit next. Chapter 12 covers this.

Part 6: The Monotonic Stack

The monotonic stack is the most important advanced stack technique. It answers the question: "For each element, what is the nearest element to its left (or right) that is greater (or smaller)?" in O(n) total.

The Problem

Next Greater Element: For each element in the array, find the next element to the right that is greater. If none exists, return -1.

nextGreater([2, 1, 2, 4, 3]) → [4, 2, 4, -1, -1]

Brute force: for each element, scan right until you find something larger. O(n²).

The Stack Insight

Process elements left to right. Maintain a stack of elements waiting to find their next greater element.

When you process a new element curr:

• While the stack is not empty AND curr > stack.top: the top element has found its next greater — it's curr. Pop it, record the answer.
• Push curr onto the stack (it hasn't found its next greater yet).

Elements on the stack are decreasing (each element is smaller than the one below it). This is a monotonic decreasing stack — it maintains a decreasing invariant from bottom to top.

function nextGreaterElement(nums) {
  const result = new Array(nums.length).fill(-1);
  const stack = [];  // stores indices of elements waiting for next greater

  for (let i = 0; i < nums.length; i++) {
    // Pop all elements smaller than nums[i] — nums[i] is their next greater
    while (stack.length > 0 && nums[stack[stack.length - 1]] < nums[i]) {
      const idx = stack.pop();
      result[idx] = nums[i];
    }
    stack.push(i);
  }
  // Elements remaining in stack have no next greater → result stays -1
  return result;
}

Full Dry Run: nextGreaterElement([2, 1, 2, 4, 3])

result = [-1,-1,-1,-1,-1]. stack=[].

i=0, nums[0]=2:
  stack empty. Push 0. stack=[0]. "index 0 (val=2) waiting."

i=1, nums[1]=1:
  nums[stack.top]=nums[0]=2. 1 < 2. Don't pop.
  Push 1. stack=[0,1]. "index 1 (val=1) waiting."

i=2, nums[2]=2:
  nums[stack.top]=nums[1]=1. 2 > 1. Pop! result[1]=2.  ← index 1's next greater is 2 ✓
  stack=[0]. nums[stack.top]=nums[0]=2. 2 = 2. Not strictly greater. Don't pop.
  Push 2. stack=[0,2].

i=3, nums[3]=4:
  nums[stack.top]=nums[2]=2. 4 > 2. Pop! result[2]=4.  ← index 2's next greater is 4 ✓
  stack=[0]. nums[stack.top]=nums[0]=2. 4 > 2. Pop! result[0]=4.  ← index 0's next greater is 4 ✓
  stack=[]. Push 3. stack=[3].

i=4, nums[4]=3:
  nums[stack.top]=nums[3]=4. 3 < 4. Don't pop.
  Push 4. stack=[3,4].

End of array. stack=[3,4] remain → result[3]=-1, result[4]=-1. (No next greater found.)

result=[4,2,4,-1,-1] ✓

Why O(n)?

Each element is pushed once and popped at most once. Total stack operations ≤ 2n. Each operation is O(1). Total: O(n).

The brute force did O(n) work per element (scan right). The monotonic stack defers the "has anyone found their next greater?" check — when a large element arrives, it solves the puzzle for all smaller elements stacked up before it in one sweep.

Part 7: Monotonic Stack Variants

The pattern adapts to four variants:

General rule: Stack order = opposite of the relation you're looking for.

• Looking for next greater: stack is decreasing (we pop when we find something greater than top).
• Looking for next smaller: stack is increasing (we pop when we find something smaller than top).

Right-to-left processing finds "previous" answers:

function previousSmaller(nums) {
  const result = new Array(nums.length).fill(-1);
  const stack = [];

  for (let i = nums.length - 1; i >= 0; i--) {
    while (stack.length > 0 && nums[stack[stack.length-1]] >= nums[i]) {
      const idx = stack.pop();
      result[idx] = nums[i];  // nums[i] is the previous smaller for idx
    }
    stack.push(i);
  }
  return result;
}

Part 8: Queue — What Problems It Solves

Pattern 1: BFS (Breadth-First Search)

Process all nodes at distance 1, then distance 2, then distance 3... The queue ensures FIFO order — you process nodes in the order you discovered them, guaranteeing level-by-level traversal. Chapter 12 covers this deeply.

Pattern 2: Sliding Window Maximum

The monotonic deque from Chapter 6 is a queue variant — elements are added to the back and removed from the front (FIFO on natural order), with additional back-removal for the monotonic invariant.

Pattern 3: Task Scheduling

OS task scheduler: processes wait in a ready queue. CPU fetches the next process, runs it for a time slice, re-enqueues if not done. FIFO ensures fairness.

Pattern 4: Level-order tree traversal

Process all nodes at level 0 (root), then level 1, then level 2... Queue ensures you process each level completely before moving to the next. Chapter 10 (Trees).

Part 9: Stack With Extra Power — Min Stack

Problem: Design a stack that supports push, pop, and getMin() — all in O(1).

Naively: to find the minimum, scan the entire stack → O(n). The trick: maintain a parallel min-stack that tracks the minimum at each level.

When you push a value, also push min(value, currentMin) onto the min-stack. When you pop, also pop the min-stack. getMin() just peeks the top of the min-stack.

class MinStack {
  constructor() {
    this.stack = [];
    this.minStack = [];  // minStack[i] = minimum of stack[0..i]
  }

  push(val) {
    this.stack.push(val);
    const currentMin = this.minStack.length > 0
      ? Math.min(val, this.minStack[this.minStack.length - 1])
      : val;
    this.minStack.push(currentMin);
  }

  pop() {
    this.stack.pop();
    this.minStack.pop();
  }

  top() {
    return this.stack[this.stack.length - 1];
  }

  getMin() {
    return this.minStack[this.minStack.length - 1];
  }
}

Dry run:

push(-2): stack=[-2], minStack=[-2].
push(0):  stack=[-2,0], minStack=[-2,-2].  (min(0,-2)=-2)
push(-3): stack=[-2,0,-3], minStack=[-2,-2,-3]. (min(-3,-2)=-3)
getMin(): return minStack.top() = -3. ✓
pop():    stack=[-2,0], minStack=[-2,-2].
getMin(): return -2. ✓
top():    return 0. ✓

Why it works: The min-stack records "what was the minimum when this element was on top?" When we pop the current element, the minimum reverts to what it was before — exactly what the min-stack remembers.

Space cost: O(n) extra space (the min-stack). Can be optimized to O(1) extra space by only pushing to min-stack when the new value is ≤ current min, but the pop logic becomes more complex. For interviews, the simple version suffices.

Part 10: Implementing One With The Other

Classic interview: implement a Queue using two Stacks.

Insight: A stack reverses order. Two reversals restore order. Push all elements onto Stack 1. To dequeue, pour Stack 1 into Stack 2 (reversing order — oldest is now on top). Pop from Stack 2.

class MyQueue {
  constructor() {
    this.inbox = [];   // stack for incoming pushes
    this.outbox = [];  // stack for outgoing pops
  }

  push(x) {
    this.inbox.push(x);  // O(1)
  }

  pop() {
    this.transfer();
    return this.outbox.pop();  // O(1) amortized
  }

  peek() {
    this.transfer();
    return this.outbox[this.outbox.length - 1];
  }

  empty() {
    return this.inbox.length === 0 && this.outbox.length === 0;
  }

  transfer() {
    // Only transfer when outbox is empty
    if (this.outbox.length === 0) {
      while (this.inbox.length > 0) {
        this.outbox.push(this.inbox.pop());
      }
    }
  }
}

Why O(1) amortized for pop: Each element is transferred from inbox to outbox exactly once. Total transfers across all operations = n. Per-operation amortized cost = O(1).

Dry run:

push(1): inbox=[1], outbox=[].
push(2): inbox=[1,2], outbox=[].
push(3): inbox=[1,2,3], outbox=[].
pop():
  outbox empty → transfer: outbox=[3,2,1]→pop from inbox=[]. outbox=[1,2,3]... 

Wait, let me re-trace:
  inbox=[1,2,3]. Transfer: pop 3 from inbox → push 3 to outbox. outbox=[3].
                           pop 2 → outbox=[3,2].
                           pop 1 → outbox=[3,2,1].
                           inbox=[].
  outbox.pop() = 1. ✓ (FIFO: 1 was pushed first)
pop(): outbox=[3,2]. pop() = 2. ✓
push(4): inbox=[4]. outbox=[3].
pop(): outbox not empty. outbox.pop()=3. ✓
pop(): outbox=[]. Transfer: inbox=[4]→outbox=[4]. outbox.pop()=4. ✓

Part 11: Mental Model

Reach for a Stack when:

1. You need the most recent unprocessed item. "What did I do last?" → pop.
2. Matching pairs: opening/closing brackets, HTML tags, function calls.
3. Undo semantics: each action is pushed, each undo pops.
4. "For each element, what is the nearest previous/next element satisfying X?" → Monotonic stack.
5. DFS — either recursive (uses call stack) or iterative (explicit stack).
6. You need to reverse a sequence (push all, pop all).

Reach for a Queue when:

1. You need to process in the order things arrived. Fairness, FIFO.
2. BFS — process level by level.
3. Task scheduling — fair resource allocation.
4. Buffering between a producer and consumer — smooth out rate differences.

The key difference in feeling:
Stack feels like "depth" — going deeper into something, then coming back. Recursion, nested structures, undo.
Queue feels like "breadth" — spreading out evenly, processing everything at each level before going deeper. BFS, scheduling, streaming.

Part 12: Real Systems

Browser History (Stack):
"Back" button is a stack pop. Every navigation pushes the current URL. "Back" pops and navigates to the previous URL. "Forward" is a second stack (forward history) — navigating back pushes current URL onto forward stack; navigating forward pops from it. When you navigate to a new URL from a backed-up position, the forward stack is cleared (you've branched off).

V8 Call Stack (Stack):
Already covered in Chapter 4. Every function call pushes a frame onto V8's call stack. Return pops it. RangeError: Maximum call stack size exceeded is the OS-level stack limit being hit.

Node.js Event Loop (Queue):
Node's event loop is built around queues. Incoming I/O callbacks go into the I/O callback queue. Timers (setTimeout, setInterval) go into the timer queue. Microtasks (Promises, queueMicrotask) go into the microtask queue. The event loop pops from these queues in a defined priority order. This is FIFO processing — earliest-added callback runs first. Understanding Node's queue structure explains why Promise.then runs before setTimeout(fn, 0).

Redis LPUSH / RPUSH (Queue/Deque):
Redis lists are doubly-linked lists acting as deques. RPUSH key val appends to the right. LPOP key removes from the left. This gives a FIFO queue. BRPOP / BLPOP are blocking versions — the client waits until an item is available. Many task queue systems (Sidekiq, Celery, Bull) use Redis lists this way: workers do BRPOP, producers do RPUSH.

Undo in VS Code (Stack):
Every keystroke or edit command is pushed onto VS Code's undo stack. Ctrl+Z pops the last action and reverses it. The redo stack catches what's undone. When you type something new after undoing, the redo stack is cleared — same browser forward-history behavior.

OS Process Scheduler (Queue):
The Linux CFS (Completely Fair Scheduler) maintains a red-black tree (sorted by "virtual runtime") acting as a priority queue. Each process gets a time slice; when the slice expires, the process is re-inserted at its new virtual runtime position. Processes waiting for I/O go into wait queues (FIFO) until their event arrives, then re-enter the scheduler.

TCP Send Buffer (Queue):
When your Node.js server writes data to a socket faster than the network can send it, the data goes into the TCP send buffer — a queue in the kernel. The TCP stack dequeues data as acknowledgments arrive from the receiver. If the buffer fills up, socket.write() returns false and you need to wait for the drain event — this is backpressure, built on queue semantics.

Part 13: Vocabulary Map

Part 14: 5 Practice Problems

1. Trace and Predict

function f(s) {
  const stack = [];
  for (const c of s) {
    if (stack.length > 0 && stack[stack.length - 1] === c) {
      stack.pop();
    } else {
      stack.push(c);
    }
  }
  return stack.join('');
}

Trace f("abbaca"). What does this function do? What is the time and space complexity? What does it return if the input is already in the "reduced" state?

2. Find the Waste

To find the previous smaller element for every position in [3,1,2,4]:

Brute force: for each i, scan left until you find something smaller. O(n²).

Describe how a monotonic stack would solve this in O(n). What order of traversal? What invariant does the stack maintain? What is the stack state after processing each element?

3. Failure Analysis

class MinStack {
  constructor() { this.stack = []; this.min = Infinity; }
  push(val) {
    this.stack.push(val);
    this.min = Math.min(this.min, val);
  }
  pop() {
    this.stack.pop();
    // Bug is here: how do we update this.min?
    this.min = Math.min(...this.stack);  // attempt
  }
  getMin() { return this.min; }
}

The pop logic is wrong in two ways. Identify both bugs. (Hint: what happens on pop when this.stack is empty? What is the time complexity of Math.min(...this.stack), and why does it defeat the purpose?)

4. Design Under Constraints

Design a stack that also supports getMax() in O(1), with O(n) space. Then: design a stack that supports getMin() AND getMax() both in O(1). How many extra stacks do you need?

Then: can you implement it with only O(1) extra space (not O(n))? (Hint: store encoded differences instead of values. This is a classic space-optimization trick — try to derive it.)

5. Reach Beyond

largestRectangleInHistogram([2,1,5,6,2,3]) → 10.

For each bar, the largest rectangle using that bar as the shortest bar extends left and right until it hits a bar shorter than itself. What stack technique finds "nearest shorter bar to the left" and "nearest shorter bar to the right" for every bar in O(n)? (Two monotonic stack passes — or one pass storing indices.) This is LeetCode 84 (Hard) and is the foundation of the "Maximal Rectangle" (LeetCode 85).

Connect Forward

Chapter 8 — Linked Lists introduces the doubly-linked list: the data structure that implements a deque with true O(1) front and back operations (no array shifting). The linked list's head and tail pointers map directly to queue's front and back.

Chapter 10 (Trees) uses both: stack for iterative DFS (preorder/inorder/postorder without recursion) and queue for BFS (level-order traversal). Once you know stacks and queues cold, you'll find tree traversal problems much easier.

Chapter 12 (Graphs) builds BFS entirely on queue. When you see "shortest path" or "minimum steps," the queue is the tool.

Connect Backward

The monotonic deque from Chapter 6 (Sliding Window Maximum) was a monotonic stack applied to a queue. Now you understand both components. The deque maintained a decreasing invariant (monotonic) using pushBack and popBack (stack-like) while also using popFront (queue-like) to remove expired window elements. Two data structures, one algorithm.

The call stack from Chapter 4 is a stack. Recursion = stack. Every recursive algorithm can be converted to an iterative one using an explicit stack — you're just making the call stack's work visible.