Stacks & Queues

Stack — LIFO

Last In, First Out. Think: a stack of plates. The last plate added is the first one taken off.

JavaScript arrays make a perfectly good stack:

const stack: number[] = []
stack.push(10)      // add to top
stack.push(20)
stack.push(30)
const top = stack[stack.length - 1]  // peek: 30
const val = stack.pop()              // remove top: 30

All stack operations — push, pop, peek — are O(1).

Use stacks for:

• DFS traversal (iterative alternative to recursion)
• Undo/redo operations
• Matching/balancing problems (parentheses, brackets)
• Expression evaluation
• Monotonic stack problems (next greater/smaller element)

Queue — FIFO

First In, First Out. Think: a line at a coffee shop. First person in line gets served first.

const queue: number[] = []
queue.push(10)      // enqueue
queue.push(20)
const front = queue[0]   // peek front
const val   = queue.shift()  // dequeue: 10 — O(n) in JS!

Warning: Array.shift() is O(n) because it shifts all elements left. For interviews this is fine. For production code with high throughput, use a proper deque (linked list or circular buffer).

Use queues for:

• BFS traversal
• Level-order tree processing
• Task scheduling, event processing
• Sliding window maximum (monotonic deque variant)

Classic: valid parentheses

Push opening brackets onto the stack. When you see a closing bracket, check if the top of the stack matches.

function isValid(s: string): boolean {
  const stack: string[] = []
  const match: Record<string, string> = { ')': '(', ']': '[', '}': '{' }

  for (const c of s) {
    if ('([{'.includes(c)) {
      stack.push(c)
    } else {
      if (stack.pop() !== match[c]) return false
    }
  }
  return stack.length === 0
}

This pattern — “use a stack to remember what you saw and match it later” — appears in many forms: evaluate expressions, decode strings, find the minimum remove to make valid, etc.

Monotonic stack

This is the pattern that separates people who know stacks from people who really know stacks.

A monotonic stack maintains elements in either increasing or decreasing order. When a new element violates the order, we pop elements from the stack and process them.

Problem: Next Greater Element

For each element, find the next element to the right that is strictly greater. Return -1 if none exists.

function nextGreaterElement(nums: number[]): number[] {
  const result = new Array(nums.length).fill(-1)
  const stack: number[] = []  // stores indices

  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)
  }
  return result  // remaining stack indices have no greater element — stay -1
}

Walk through [2, 1, 3, 4, 1]:

• i=0: push 0. stack=[0]
• i=1: nums[1]=1 < nums[0]=2, just push. stack=[0,1]
• i=2: nums[2]=3 > nums[1]=1 → result[1]=3, pop 1. nums[2]=3 > nums[0]=2 → result[0]=3, pop 0. Push 2. stack=[2]
• i=3: nums[3]=4 > nums[2]=3 → result[2]=4. Push 3. stack=[3]
• i=4: nums[4]=1 < nums[3]=4, push. stack=[3,4]
• Result: [3, 3, 4, -1, -1]

The template:

const stack: number[] = []  // monotonic stack of indices

for (let i = 0; i < arr.length; i++) {
  while (stack.length > 0 && /* condition: arr[stack.top] vs arr[i] */) {
    const idx = stack.pop()!
    // process: arr[idx]'s answer is arr[i] (or idx, i, etc.)
  }
  stack.push(i)
}
// remaining elements in stack have no answer

Use monotonic stack for:

• Next greater / next smaller element
• Largest rectangle in histogram (classic hard problem)
• Trapping rainwater
• Sum of subarray minimums / maximums

The time complexity is O(n) even though there’s a while inside a for — each element is pushed and popped at most once.

Min stack

Design a stack that supports getMin() in O(1) alongside normal stack operations.

class MinStack {
  private stack:    number[] = []
  private minStack: number[] = []  // parallel stack of mins

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

  pop(): void {
    this.stack.pop()
    this.minStack.pop()
  }

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

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

The min stack mirrors the main stack. Each position in minStack stores “what’s the minimum of everything below and including this position”. Popping is free because we pop both stacks together.

Complexity reference