Queues

Interactive Visualization

Time Complexity

Key Points

• FIFO: First In, First Out
• enqueue: add to back, dequeue: remove from front
• JS arrays can work as queues but shift() is O(n)
• For performance, use a proper Queue class or linked list
• BFS (Breadth-First Search) uses a queue
• Used for: level-order traversal, scheduling, buffering

Code Examples

// Using array as queue (simple but not optimal)
const queue = []

// Enqueue - add to back - O(1)
queue.push(1)  // [1]
queue.push(2)  // [1, 2]
queue.push(3)  // [1, 2, 3]

// Dequeue - remove from front - O(n)!
queue.shift()  // Returns 1, queue is [2, 3]
queue.shift()  // Returns 2, queue is [3]

// Peek front
queue[0]  // 3

// ⚠️ shift() is O(n) - not ideal for large queues

class Queue {
  constructor() {
    this.items = {}
    this.head = 0
    this.tail = 0
  }

  enqueue(item) {
    this.items[this.tail] = item
    this.tail++
  }

  dequeue() {
    if (this.isEmpty()) return undefined
    const item = this.items[this.head]
    delete this.items[this.head]
    this.head++
    return item
  }

  peek() {
    return this.items[this.head]
  }

  isEmpty() {
    return this.tail === this.head
  }

  size() {
    return this.tail - this.head
  }
}

// All operations O(1)!

function levelOrder(root) {
  if (!root) return []

  const result = []
  const queue = [root]

  while (queue.length > 0) {
    const levelSize = queue.length
    const level = []

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()
      level.push(node.val)

      if (node.left) queue.push(node.left)
      if (node.right) queue.push(node.right)
    }

    result.push(level)
  }

  return result
}

// Tree:     1
//          / \
//         2   3
// Output: [[1], [2, 3]]

function shortestPath(graph, start, end) {
  const queue = [[start, 0]]  // [node, distance]
  const visited = new Set([start])

  while (queue.length > 0) {
    const [node, dist] = queue.shift()

    if (node === end) return dist

    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor)
        queue.push([neighbor, dist + 1])
      }
    }
  }

  return -1  // No path found
}

// BFS finds shortest path in unweighted graphs
// because it explores level by level

function numIslands(grid) {
  let count = 0

  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[0].length; j++) {
      if (grid[i][j] === '1') {
        count++
        bfs(grid, i, j)  // Mark entire island
      }
    }
  }

  return count
}

function bfs(grid, r, c) {
  const queue = [[r, c]]
  grid[r][c] = '0'  // Mark visited

  while (queue.length > 0) {
    const [row, col] = queue.shift()
    const dirs = [[1,0], [-1,0], [0,1], [0,-1]]

    for (const [dr, dc] of dirs) {
      const nr = row + dr, nc = col + dc
      if (nr >= 0 && nr < grid.length &&
          nc >= 0 && nc < grid[0].length &&
          grid[nr][nc] === '1') {
        grid[nr][nc] = '0'
        queue.push([nr, nc])
      }
    }
  }
}

// STACK (LIFO) - Last In, First Out
// Like a stack of plates
const stack = []
stack.push(1)  // [1]
stack.push(2)  // [1, 2]
stack.pop()    // 2 (last added)

// Use for: DFS, recursion, undo, matching

// QUEUE (FIFO) - First In, First Out
// Like a line at a store
const queue = []
queue.push(1)  // [1]
queue.push(2)  // [1, 2]
queue.shift()  // 1 (first added)

// Use for: BFS, scheduling, buffering

// Easy to remember:
// Stack = DFS = go DEEP first
// Queue = BFS = go WIDE first

Common Mistakes

• Using array.shift() in hot path (O(n) each call)
• Confusing BFS (queue) with DFS (stack)
• Not tracking visited nodes in graph BFS (infinite loop)
• Forgetting queue for shortest path problems

Interview Tips

• BFS = Queue, DFS = Stack (or recursion)
• BFS finds shortest path in UNWEIGHTED graphs
• Level-order tree traversal = BFS with a queue
• For large queues, implement O(1) dequeue

Practice Problems

Related Concepts