Orders, in order
Kitchen orders are served in the order they arrive: first in, first out (FIFO). That's a queue. Using an array with shift() works but is O(n) per dequeue; a queue that remembers where its head is makes both ends O(1).
A fast queue
class Queue {
#items = {};
#head = 0;
#tail = 0;
enqueue(x) { this.#items[this.#tail++] = x; }
dequeue() {
if (this.#head === this.#tail) return undefined;
const x = this.#items[this.#head];
delete this.#items[this.#head++];
return x;
}
peek() { return this.#items[this.#head]; }
get size() { return this.#tail - this.#head; }
}
const kitchen = new Queue();
kitchen.enqueue("momo for table 2");
kitchen.enqueue("thukpa for table 5");
kitchen.enqueue("tea for table 1");
console.log(kitchen.dequeue(), "| waiting:", kitchen.size);
let t = performance.now();
const q = new Queue();
for (let i = 0; i < 50000; i++) q.enqueue(i);
while (q.size) q.dequeue();
console.log("50,000 orders through the queue:", Math.round(performance.now() - t), "ms");A deque (double-ended queue) allows adding and removing at both ends; a ring buffer is a fixed-size queue that wraps around an array.