Queues / Deques

// 1) BFS — shortest path in an unweighted graph
function shortestPath(graph, start, target) {
    const queue = [start];
    const dist  = new Map([[start, 0]]);
    while (queue.length) {
        const u = queue.shift();
        if (u === target) return dist.get(u);
        for (const v of graph.get(u) ?? []) {
            if (!dist.has(v)) {
                dist.set(v, dist.get(u) + 1);
                queue.push(v);
            }
        }
    }
    return -1;
}

// 2) Sliding-window max — deque holding indices in decreasing order
function maxSlidingWindow(nums, k) {
    const out = [], dq = [];   // indices
    for (let i = 0; i < nums.length; i++) {
        while (dq.length && dq[0] <= i - k) dq.shift();
        while (dq.length && nums[dq.at(-1)] <= nums[i]) dq.pop();
        dq.push(i);
        if (i >= k - 1) out.push(nums[dq[0]]);
    }
    return out;
}

// 3) Bounded blocking queue (in JS you fake it with promises)
class Queue {
    #buf = [];
    #waiters = [];
    enqueue(x) {
        const w = this.#waiters.shift();
        if (w) w(x); else this.#buf.push(x);
    }
    dequeue() {
        return new Promise(resolve => {
            const x = this.#buf.shift();
            if (x !== undefined) resolve(x); else this.#waiters.push(resolve);
        });
    }
}

// 4) JS performance — Array.shift is O(n). For long-running queues:
//    use two stacks, or @datastructures-js/queue, or a circular buffer.

// FIFO. For O(1) both ends use a deque (linked list).
// In JS, a simple double-ended deque from arrays is sufficient for small n.
const q = [];
q.push('a');           // enqueue
const x = q.shift();   // dequeue (O(n) — use a proper deque if hot)