Stacks & Queues

Stacks and queues are linear-access control structures.

• Stack -> LIFO (last-in first-out)
• Queue -> FIFO (first-in first-out)

Most problems here are about choosing the right “who gets processed next” policy.

Stack Fundamentals (LIFO)

Use stack when most recent item should be handled first.

const stack: number[] = []
stack.push(10)
stack.push(20)
stack.push(30)

const top = stack[stack.length - 1] // 30
const popped = stack.pop() // 30

Core ops:

• push O(1)
• pop O(1)
• peek O(1)

Typical use cases:

• DFS / backtracking simulation
• bracket matching
• expression parsing/evaluation
• monotonic stack patterns

Queue Fundamentals (FIFO)

Use queue when oldest waiting item should be processed first.

const queue: number[] = []
queue.push(10) // enqueue
queue.push(20)
const front = queue[0]

JavaScript caveat

shift() is O(n), because all remaining elements are reindexed.

For interview code this is often accepted; for production or large inputs, use a queue with head pointer or deque.

O(1) Queue in JS (Head Pointer Pattern)

class FastQueue<T> {
  private data: T[] = []
  private head = 0

  enqueue(x: T): void {
    this.data.push(x)
  }

  dequeue(): T | undefined {
    if (this.head === this.data.length) return undefined
    const value = this.data[this.head]
    this.head++

    // occasional compaction
    if (this.head > 1024 && this.head * 2 > this.data.length) {
      this.data = this.data.slice(this.head)
      this.head = 0
    }
    return value
  }

  peek(): T | undefined {
    return this.head < this.data.length ? this.data[this.head] : undefined
  }

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

This avoids repeated O(n) shifts.

Classic Stack Problem: Valid Parentheses

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

  for (const ch of s) {
    if (open.has(ch)) stack.push(ch)
    else {
      if (stack.pop() !== match[ch]) return false
    }
  }
  return stack.length === 0
}

Invariant:

• stack contains unmatched opening brackets in order

Queue Core Use: BFS

Queue controls level-by-level expansion.

type Node = { val: number; left: Node | null; right: Node | null }

function levelOrder(root: Node | null): number[][] {
  if (root === null) return []

  const q = new FastQueue<Node>()
  q.enqueue(root)
  const ans: number[][] = []

  while (q.size() > 0) {
    const levelSize = q.size()
    const level: number[] = []

    for (let i = 0; i < levelSize; i++) {
      const node = q.dequeue()!
      level.push(node.val)
      if (node.left) q.enqueue(node.left)
      if (node.right) q.enqueue(node.right)
    }
    ans.push(level)
  }
  return ans
}

The queue boundary (levelSize) gives clean level separation.

Monotonic Stack (High-Value Pattern)

Monotonic stack keeps elements in increasing/decreasing order to answer “next greater/smaller” style queries in O(n).

Next Greater Element

function nextGreaterElement(nums: number[]): number[] {
  const ans = new Array(nums.length).fill(-1)
  const st: number[] = [] // indices, values decreasing

  for (let i = 0; i < nums.length; i++) {
    while (st.length > 0 && nums[st[st.length - 1]] < nums[i]) {
      const idx = st.pop()!
      ans[idx] = nums[i]
    }
    st.push(i)
  }

  return ans
}

Why O(n):

• each index pushed once, popped once

Monotonic Stack Template

const st: number[] = [] // typically store indices

for (let i = 0; i < arr.length; i++) {
  while (st.length > 0 && violatesMonotonic(arr[st[st.length - 1]], arr[i])) {
    const idx = st.pop()!
    // resolve answer for idx using i
  }
  st.push(i)
}

Use cases:

• next greater/smaller
• stock span
• largest rectangle in histogram
• sum of subarray minimums

Monotonic Deque (Queue + Order Constraint)

For sliding-window max/min, plain queue is insufficient because you need quick max and expiry handling.

function maxSlidingWindow(nums: number[], k: number): number[] {
  const ans: number[] = []
  const dq: number[] = [] // indices; values decreasing
  let head = 0

  for (let i = 0; i < nums.length; i++) {
    // remove out-of-window indices
    if (head < dq.length && dq[head] <= i - k) head++

    // maintain decreasing order
    while (head < dq.length && nums[dq[dq.length - 1]] <= nums[i]) dq.pop()

    dq.push(i)
    if (i >= k - 1) ans.push(nums[dq[head]])

    if (head > 1024 && head * 2 > dq.length) {
      dq.splice(0, head)
      head = 0
    }
  }
  return ans
}

This is a true O(n) JavaScript-friendly monotonic deque pattern (no shift() in hot path).

Expression Evaluation (Stack of Values)

Evaluate Reverse Polish Notation

function evalRPN(tokens: string[]): number {
  const st: number[] = []

  for (const t of tokens) {
    if (t === "+" || t === "-" || t === "*" || t === "/") {
      const b = st.pop()!
      const a = st.pop()!

      if (t === "+") st.push(a + b)
      else if (t === "-") st.push(a - b)
      else if (t === "*") st.push(a * b)
      else st.push(Math.trunc(a / b))
    } else {
      st.push(Number(t))
    }
  }
  return st[0]
}

Pattern:

• operators consume recent operands (LIFO)

Min Stack Design

Support getMin() in O(1).

class MinStack {
  private st: number[] = []
  private mins: number[] = []

  push(x: number): void {
    this.st.push(x)
    const m = this.mins.length === 0 ? x : Math.min(x, this.mins[this.mins.length - 1])
    this.mins.push(m)
  }

  pop(): void {
    this.st.pop()
    this.mins.pop()
  }

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

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

Parallel-stack technique generalizes to other aggregates.

Queue via Two Stacks

Classic interview design question.

Idea:

• inStack for enqueue
• outStack for dequeue
• when outStack empty, move all items from inStack to outStack once

class MyQueue {
  private inSt: number[] = []
  private outSt: number[] = []

  push(x: number): void {
    this.inSt.push(x)
  }

  private shiftStacks(): void {
    if (this.outSt.length === 0) {
      while (this.inSt.length > 0) this.outSt.push(this.inSt.pop()!)
    }
  }

  pop(): number {
    this.shiftStacks()
    return this.outSt.pop()!
  }

  peek(): number {
    this.shiftStacks()
    return this.outSt[this.outSt.length - 1]
  }

  empty(): boolean {
    return this.inSt.length === 0 && this.outSt.length === 0
  }
}

Amortized O(1) per op.

Recognizing Stack/Queue Problems Quickly

Stack signals

• “nearest previous/next greater/smaller”
• “balanced symbols”
• “undo” / “backtrack”
• “evaluate expression”

Queue signals

• “minimum number of steps/levels”
• “process in arrival order”
• “multi-source shortest expansion” (BFS)

Deque signals

• sliding window extrema
• 0-1 BFS
• monotonic queue constraints

Common Bugs Checklist

1. Using shift() in tight loops and timing out
2. Pushing values instead of indices in monotonic problems (loses positional logic)
3. Wrong pop condition (< vs <=) causing duplicate handling bugs
4. Forgetting empty checks before pop/peek
5. In RPN/evaluation, wrong operand order for subtraction/division
6. In BFS, mixing level boundaries and dynamic queue length incorrectly

Interview Communication Script

Say:

1. “I need most recent unresolved state -> stack.”
2. “Each element is pushed and popped at most once -> amortized O(n).”
3. “For queue-heavy traversal I use BFS level order with O(V+E).”

Choosing the right data structure quickly is often more important than code detail.

Problem Ladder

Easy

• Valid Parentheses
• Implement Stack using Queues
• Implement Queue using Stacks

Medium

• Daily Temperatures
• Evaluate Reverse Polish Notation
• Binary Tree Level Order Traversal
• Decode String

Hard / high-signal

• Largest Rectangle in Histogram
• Sliding Window Maximum
• Trapping Rain Water
• Sum of Subarray Minimums

Complexity Summary

Final Takeaway

Stacks and queues are control-flow tools:

• stack -> resolve newest pending constraints first
• queue -> process oldest frontier first
• monotonic variants -> maintain order constraints for linear-time query resolution

Mastering these abstractions gives you fast, elegant solutions to many “hard-looking” interview problems.