Queues

Track front and rear indices. Enqueue at rear, dequeue from front. Use modular arithmetic for circular behavior to avoid wasting space.

class ArrayQueue {
    constructor(capacity) {
        this.items = new Array(capacity);
        this.front = 0;
        this.rear = 0;
        this.size = 0;
        this.capacity = capacity;
    }

    enqueue(val) {
        if (this.size === this.capacity) return false;
        this.items[this.rear] = val;
        this.rear = (this.rear + 1) % this.capacity;
        this.size++;
        return true;
    }

    dequeue() {
        if (this.size === 0) return null;
        const val = this.items[this.front];
        this.front = (this.front + 1) % this.capacity;
        this.size--;
        return val;
    }
}

This gives O(1) enqueue and dequeue without wasting space.

A circular queue wraps the rear index back to the start when it reaches the end of the array, reusing freed spaces from dequeue operations.

class CircularQueue {
    constructor(k) {
        this.queue = new Array(k);
        this.head = -1;
        this.tail = -1;
        this.size = k;
    }

    enqueue(val) {
        if (this.isFull()) return false;
        if (this.isEmpty()) this.head = 0;
        this.tail = (this.tail + 1) % this.size;
        this.queue[this.tail] = val;
        return true;
    }

    dequeue() {
        if (this.isEmpty()) return false;
        if (this.head === this.tail) { this.head = -1; this.tail = -1; }
        else this.head = (this.head + 1) % this.size;
        return true;
    }

    isEmpty() { return this.head === -1; }
    isFull() { return (this.tail + 1) % this.size === this.head; }
}

Used in CPU scheduling, buffer management, and traffic systems.

A priority queue serves elements based on priority rather than insertion order. Higher priority elements are dequeued first.

• Typically implemented with a heap for O(log n) insert and extract.
• Used in Dijkstra's algorithm, task scheduling, and Huffman coding.

// Simple priority queue (not optimal — use a heap for production)
class PriorityQueue {
    constructor() { this.items = []; }

    enqueue(val, priority) {
        this.items.push({ val, priority });
        this.items.sort((a, b) => a.priority - b.priority);
    }

    dequeue() {
        return this.items.shift();
    }
}
// pq.enqueue("low", 3);
// pq.enqueue("high", 1);
// pq.dequeue() => { val: "high", priority: 1 }

The sort-based approach is O(n log n) per enqueue. A proper min-heap achieves O(log n).

BFS explores a graph level by level using a queue. Enqueue the start node, then dequeue and enqueue its unvisited neighbors.

function bfs(graph, start) {
    const visited = new Set([start]);
    const queue = [start];
    const result = [];

    while (queue.length) {
        const node = queue.shift();
        result.push(node);
        for (const neighbor of graph[node]) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
    return result;
}
// graph = { A:['B','C'], B:['D'], C:['E'], D:[], E:[] }
// bfs(graph, 'A') => ['A','B','C','D','E']

Time: O(V + E)  |  Space: O(V)

Use stack1 for enqueue and stack2 for dequeue. When stack2 is empty, transfer all elements from stack1 to stack2 (reversing the order).

class QueueFromStacks {
    constructor() {
        this.stack1 = [];  // for push
        this.stack2 = [];  // for pop
    }

    enqueue(val) {
        this.stack1.push(val);
    }

    dequeue() {
        if (!this.stack2.length) {
            while (this.stack1.length) {
                this.stack2.push(this.stack1.pop());
            }
        }
        return this.stack2.pop();
    }
}
// q.enqueue(1); q.enqueue(2); q.enqueue(3);
// q.dequeue() => 1 (FIFO order)

Amortized O(1) per operation. Each element is moved at most twice.

A deque supports insertion and deletion at both ends in O(1) time.

class Deque {
    constructor() { this.items = []; }

    addFront(val)  { this.items.unshift(val); }
    addRear(val)   { this.items.push(val); }
    removeFront()  { return this.items.shift(); }
    removeRear()   { return this.items.pop(); }
    peekFront()    { return this.items[0]; }
    peekRear()     { return this.items[this.items.length - 1]; }
    isEmpty()      { return this.items.length === 0; }
}

• Use cases: Sliding window maximum, palindrome checking, work-stealing algorithms.
• Note: JavaScript's unshift/shift are O(n). For true O(1), use a doubly linked list.

Use a deque that stores indices. Keep elements in decreasing order; the front always has the max for the current window.

function maxSlidingWindow(nums, k) {
    const deque = [];
    const result = [];
    for (let i = 0; i < nums.length; i++) {
        // Remove indices outside the window
        if (deque.length && deque[0] < i - k + 1) deque.shift();
        // Remove smaller elements from back
        while (deque.length && nums[deque[deque.length - 1]] < nums[i]) {
            deque.pop();
        }
        deque.push(i);
        if (i >= k - 1) result.push(nums[deque[0]]);
    }
    return result;
}
// maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3)
// => [3,3,5,5,6,7]

Time: O(n)  |  Space: O(k)

Use a queue and a frequency map. Enqueue each character; dequeue from front while it has count > 1.

function firstNonRepeatingStream(stream) {
    const freq = {};
    const queue = [];
    const results = [];

    for (const ch of stream) {
        freq[ch] = (freq[ch] || 0) + 1;
        queue.push(ch);

        while (queue.length && freq[queue[0]] > 1) {
            queue.shift();
        }
        results.push(queue.length ? queue[0] : null);
    }
    return results;
}
// firstNonRepeatingStream("aabcbc")
// => ['a', null, 'b', 'b', 'c', null]

Time: O(n) amortized  |  Space: O(n)

Start with "1" in the queue. For each number, dequeue it, then enqueue it + "0" and it + "1".

function generateBinary(n) {
    const result = [];
    const queue = ["1"];
    for (let i = 0; i < n; i++) {
        const front = queue.shift();
        result.push(front);
        queue.push(front + "0");
        queue.push(front + "1");
    }
    return result;
}
// generateBinary(5) => ["1","10","11","100","101"]
// generateBinary(8) => ["1","10","11","100","101","110","111","1000"]

Time: O(n)  |  Space: O(n). This elegantly uses the queue's FIFO property to generate numbers in order.

Use an input stack and an output stack. Enqueue goes to input; dequeue lazily moves all elements from input to output, reversing order (FIFO).

class MyQueue {
    constructor() { this.inbox = []; this.outbox = []; }
    push(x) { this.inbox.push(x); }
    pop() {
        this._refill();
        return this.outbox.pop();
    }
    peek() {
        this._refill();
        return this.outbox[this.outbox.length - 1];
    }
    empty() { return !this.inbox.length && !this.outbox.length; }
    _refill() {
        if (!this.outbox.length)
            while (this.inbox.length) this.outbox.push(this.inbox.pop());
    }
}
// push(1), push(2), peek() => 1, pop() => 1, empty() => false

Amortized Time: O(1) per operation  |  Space: O(n)

Use a fixed-size array with head, tail, and count variables. Wrap indices with modulus.

class CircularQueue {
    constructor(k) { this.q = new Array(k); this.k = k; this.head = 0; this.tail = 0; this.count = 0; }
    enQueue(val) {
        if (this.isFull()) return false;
        this.q[this.tail] = val;
        this.tail = (this.tail + 1) % this.k;
        this.count++;
        return true;
    }
    deQueue() {
        if (this.isEmpty()) return false;
        this.head = (this.head + 1) % this.k;
        this.count--;
        return true;
    }
    Front() { return this.isEmpty() ? -1 : this.q[this.head]; }
    Rear()  { return this.isEmpty() ? -1 : this.q[(this.tail - 1 + this.k) % this.k]; }
    isEmpty() { return this.count === 0; }
    isFull()  { return this.count === this.k; }
}
// new CircularQueue(3): enQueue(1)=T, enQueue(2)=T, enQueue(3)=T
// enQueue(4)=false (full), Rear()=3, deQueue()=T, enQueue(4)=T

Time: O(1) for all ops  |  Space: O(k)

Use a queue (FIFO). Start with root, process nodes level by level: dequeue, visit, enqueue children.

function levelOrder(root) {
    if (!root) return [];
    const result = [], queue = [root];
    while (queue.length) {
        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:   3
//        / //       9  20
//          / //         15   7
// Output: [[3],[9,20],[15,7]]

Time: O(n)  |  Space: O(w) where w is max width

BFS guarantees the shortest path in unweighted graphs. Enqueue (row, col, steps), mark cells visited immediately upon enqueueing to avoid revisiting.

function shortestPath(grid, start, end) {
    const rows = grid.length, cols = grid[0].length;
    const visited = Array.from({length: rows}, () => new Array(cols).fill(false));
    const queue = [[...start, 0]]; // [row, col, steps]
    visited[start[0]][start[1]] = true;
    const dirs = [[0,1],[0,-1],[1,0],[-1,0]];
    while (queue.length) {
        const [r, c, steps] = queue.shift();
        if (r === end[0] && c === end[1]) return steps;
        for (const [dr, dc] of dirs) {
            const nr = r + dr, nc = c + dc;
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                && !visited[nr][nc] && grid[nr][nc] !== 1) {
                visited[nr][nc] = true;
                queue.push([nr, nc, steps + 1]);
            }
        }
    }
    return -1; // no path
}
// Grid 0=open 1=wall: [[0,0,0],[1,1,0],[0,0,0]]
// start=[0,0], end=[2,2]  => Output: 4

Time: O(rows × cols)  |  Space: O(rows × cols)

Use a monotonic decreasing deque of indices. Remove indices that fall outside the window (from front), and remove smaller elements (from back). Front always holds the max.

function maxSlidingWindow(nums, k) {
    const deque = [], result = [];
    for (let i = 0; i < nums.length; i++) {
        // Remove out-of-window indices
        while (deque.length && deque[0] < i - k + 1) deque.shift();
        // Remove smaller elements
        while (deque.length && nums[deque[deque.length-1]] < nums[i]) deque.pop();
        deque.push(i);
        if (i >= k - 1) result.push(nums[deque[0]]);
    }
    return result;
}
// Input: nums=[1,3,-1,-3,5,3,6,7], k=3   => Output: [3,3,5,5,6,7]
// Input: nums=[1], k=1                    => Output: [1]

Time: O(n) — each element pushed/popped at most once  |  Space: O(k)

Use a queue and a frequency map. Queue holds candidates in order. On each query, pop from the front while the front character has frequency > 1.

function firstNonRepeating(stream) {
    const freq = {}, order = [];
    const result = [];
    for (const ch of stream) {
        freq[ch] = (freq[ch] || 0) + 1;
        order.push(ch);
        while (order.length && freq[order[0]] > 1) order.shift();
        result.push(order.length ? order[0] : '#');
    }
    return result;
}
// Input: "aabc"  => Output: ["a","#","b","b"]
// Input: "aababc" => Output: ["a","#","b","b","b","c"]

Time: O(n)  |  Space: O(n)

Use a max-heap (priority queue) for frequencies and a cooldown queue. At each time unit, use the most frequent available task.

function leastInterval(tasks, n) {
    const freq = {};
    for (const t of tasks) freq[t] = (freq[t] || 0) + 1;
    // MaxHeap simulation using sorted array (simplified)
    let heap = Object.values(freq).sort((a, b) => b - a);
    let time = 0;
    const cooldown = []; // [freq, availableAt]
    while (heap.length || cooldown.length) {
        time++;
        if (heap.length) {
            const top = heap.shift() - 1;
            if (top > 0) cooldown.push([top, time + n]);
        }
        // Re-add tasks that have cooled down
        if (cooldown.length && cooldown[0][1] === time) {
            heap.push(cooldown.shift()[0]);
            heap.sort((a, b) => b - a);
        }
    }
    return time;
}
// Input: tasks=["A","A","A","B","B","B"], n=2  => Output: 8
// Input: tasks=["A","A","A","B","B","B"], n=0  => Output: 6

Time: Approximately O(n log k)  |  Space: O(k) where k is unique tasks

Process each node: if it has a left child, connect left.next = right. If it has a next sibling, connect right.next = next.left. Traverse level by level.

function connect(root) {
    if (!root) return null;
    const queue = [root];
    while (queue.length) {
        const size = queue.length;
        for (let i = 0; i < size; i++) {
            const node = queue.shift();
            if (i < size - 1) node.next = queue[0]; // link within level
            if (node.left)  queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
    }
    return root;
}
// Perfect tree:   1
//               /   //              2     3
//             /    / //            4  5  6   7
// After connect: 1->null, 2->3->null, 4->5->6->7->null

Time: O(n)  |  Space: O(w) max queue width

Convert the tree to an undirected graph (track parents), then do a BFS from the target node to distance K.

function distanceK(root, target, k) {
    const graph = new Map();
    // Build adjacency list including parent edges
    function buildGraph(node, parent) {
        if (!node) return;
        if (!graph.has(node.val)) graph.set(node.val, []);
        if (parent) {
            graph.get(node.val).push(parent.val);
            graph.get(parent.val).push(node.val);
        }
        buildGraph(node.left, node);
        buildGraph(node.right, node);
    }
    // Add all nodes to graph first
    function init(node) {
        if (!node) return;
        graph.set(node.val, []);
        init(node.left); init(node.right);
    }
    init(root); buildGraph(root, null);
    // BFS from target
    const visited = new Set([target.val]);
    let queue = [target.val];
    for (let dist = 0; dist < k; dist++) {
        const next = [];
        for (const n of queue)
            for (const nb of (graph.get(n) || []))
                if (!visited.has(nb)) { visited.add(nb); next.push(nb); }
        queue = next;
    }
    return queue;
}
// Target node=5, k=2 => nodes at distance 2 from 5 = [7, 4, 1]

Time: O(n)  |  Space: O(n)

Use BFS with node indices. Assign each node an index (left child = 2i, right child = 2i+1). Width at each level = last_index - first_index + 1.

function widthOfBinaryTree(root) {
    if (!root) return 0;
    let maxWidth = 0;
    let queue = [[root, 0n]]; // [node, index] using BigInt for large trees
    while (queue.length) {
        const size = queue.length;
        const firstIdx = queue[0][1];
        const next = [];
        for (let i = 0; i < size; i++) {
            const [node, idx] = queue[i];
            const relIdx = idx - firstIdx; // normalize to avoid overflow
            if (node.left)  next.push([node.left,  relIdx * 2n]);
            if (node.right) next.push([node.right, relIdx * 2n + 1n]);
        }
        maxWidth = Math.max(maxWidth, Number(queue[size-1][1] - queue[0][1]) + 1);
        queue = next;
    }
    return maxWidth;
}
// Balanced tree depth 3  => Output: 4 (bottom level)

Time: O(n)  |  Space: O(w) max level width

Use a queue storing timestamps. On each hit, add timestamp. On getHits, remove timestamps older than 5 minutes ago, then return queue size.

class HitCounter {
    constructor() { this.hits = []; }
    hit(timestamp) {
        this.hits.push(timestamp);
    }
    getHits(timestamp) {
        // Remove hits older than 300 seconds
        while (this.hits.length && this.hits[0] <= timestamp - 300) {
            this.hits.shift();
        }
        return this.hits.length;
    }
}
// hit(1),hit(2),hit(3),getHits(4)=3
// hit(300),getHits(300)=4
// getHits(301)=3  (hit at t=1 expired)

Time: O(1) amortized for hit, O(n) worst case for getHits  |  Space: O(n)

Use BFS level by level. Alternate reversing the level array using a boolean flag (left-to-right vs right-to-left).

function zigzagLevelOrder(root) {
    if (!root) return [];
    const result = [];
    let queue = [root], leftToRight = true;
    while (queue.length) {
        const size = queue.length;
        const level = [];
        const next = [];
        for (let i = 0; i < size; i++) {
            const node = queue[i];
            level.push(node.val);
            if (node.left)  next.push(node.left);
            if (node.right) next.push(node.right);
        }
        result.push(leftToRight ? level : [...level].reverse());
        leftToRight = !leftToRight;
        queue = next;
    }
    return result;
}
// Tree:   3
//        / //       9  20
//          / //         15   7
// Output: [[3],[20,9],[15,7]]

Time: O(n)  |  Space: O(w) max level width

Iterate the grid. When a '1' is found, trigger a BFS to mark all connected land cells as visited. Count how many times BFS is triggered.

function numIslands(grid) {
    let count = 0;
    const rows = grid.length, cols = grid[0].length;
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (grid[r][c] === '1') {
                count++;
                const queue = [[r, c]];
                grid[r][c] = '0'; // mark visited
                while (queue.length) {
                    const [row, col] = queue.shift();
                    for (const [dr, dc] of [[0,1],[0,-1],[1,0],[-1,0]]) {
                        const nr = row+dr, nc = col+dc;
                        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === '1') {
                            grid[nr][nc] = '0';
                            queue.push([nr, nc]);
                        }
                    }
                }
            }
        }
    }
    return count;
}
// Input: [["1","1","0"],["1","0","0"],["0","0","1"]]  => Output: 2
// Input: [["1","1","1"],["0","1","0"],["1","1","1"]]  => Output: 1

Time: O(rows × cols)  |  Space: O(min(rows, cols))

Use BFS with all 8 possible knight moves. BFS guarantees minimum steps since all moves have equal cost.

function minKnightMoves(x, y) {
    // Work in positive quadrant due to symmetry
    x = Math.abs(x); y = Math.abs(y);
    const moves = [[1,2],[2,1],[2,-1],[1,-2],[-1,-2],[-2,-1],[-2,1],[-1,2]];
    const visited = new Set(['0,0']);
    let queue = [[0, 0, 0]]; // [row, col, steps]
    while (queue.length) {
        const [r, c, steps] = queue.shift();
        if (r === x && c === y) return steps;
        for (const [dr, dc] of moves) {
            const nr = r + dr, nc = c + dc;
            // Prune: stay within reasonable bounds
            if (nr >= -2 && nc >= -2 && !visited.has(nr + ',' + nc)) {
                visited.add(nr + ',' + nc);
                queue.push([nr, nc, steps + 1]);
            }
        }
    }
}
// Input: x=2, y=1   => Output: 1  (one knight move)
// Input: x=5, y=5   => Output: 4

Time: O(max(x,y)²)  |  Space: O(max(x,y)²)