Stacks and Queues
Queues in JavaScript
JavaScript has no queue. The obvious implementation with shift() is quadratic, and it is the most common accidental performance bug in this whole subject.
First in, first out
Add at the back, remove from the front. A checkout line. Where a stack reverses order, a queue preserves it - which is why breadth-first search uses one.
The trap
The obvious queue is O(n) per removal
javascript
const queue = []
queue.push(1) // O(1) — fine
queue.push(2)
queue.shift() // O(n) — every remaining element slides forward
console.log(queue) // what is left after the shiftProcessing a million items this way is roughly half a trillion element moves. It will appear to hang.
The fix: never move the data
Keep a pointer to the front instead of removing from it. Removal becomes O(1); the cost is that the array keeps growing until you clean it up.
An O(1) queue
javascript
class Queue {
#items = []
#head = 0
enqueue(value) {
this.#items.push(value)
}
dequeue() {
if (this.#head >= this.#items.length) return undefined
const value = this.#items[this.#head]
// Release the reference so it can be garbage collected.
this.#items[this.#head] = undefined
this.#head++
// Compact once the dead prefix outgrows the live part, so the
// array cannot grow without bound in a long-running queue.
if (this.#head > 32 && this.#head * 2 > this.#items.length) {
this.#items = this.#items.slice(this.#head)
this.#head = 0
}
return value
}
get size() { return this.#items.length - this.#head }
get isEmpty() { return this.size === 0 }
}
const demoQueue = new Queue()
demoQueue.enqueue("a")
demoQueue.enqueue("b")
console.log(demoQueue.dequeue()) // "a"
console.log(demoQueue.size) // 1The compaction step matters in a server process. Without it a queue that runs for hours holds every item it has ever seen.
Where you will actually use it
Breadth-first search on a tree or graph - the single most common use. Level-order traversal is a queue and nothing else:
Level order, using a queue
javascript
function levelOrder(root) {
if (!root) return []
const out = []
const queue = [root]
let head = 0
while (head < queue.length) {
const levelSize = queue.length - head
const level = []
for (let i = 0; i < levelSize; i++) {
const node = queue[head++]
level.push(node.value)
if (node.left) queue.push(node.left)
if (node.right) queue.push(node.right)
}
out.push(level)
}
return out
}
const demoTree = { value: 1, children: [{ value: 2, children: [] }, { value: 3, children: [] }] }
console.log(levelOrder(demoTree)) // [[1], [2, 3]]Note head++ rather than shift(). Same result, and it turns O(n squared) into O(n).
Deques, briefly
A deque allows adding and removing at both ends. It is what a sliding-window-maximum solution needs. In JavaScript you build it the same way - an array with a head pointer, plus pop for the back.
Why shift is the trap
Array.prototype.shift is O(n) because every remaining element moves down one index. Used once, fine. Used as the dequeue in a BFS over 100,000 nodes, it turns a linear algorithm into a quadratic one - and this is the single most common accidental slowdown in graph code.
A queue that stays O(1) per operation
javascript
class Queue {
constructor() {
this.items = []
this.head = 0
}
enqueue(value) {
this.items.push(value)
}
dequeue() {
if (this.head >= this.items.length) return undefined
const value = this.items[this.head]
this.items[this.head] = undefined // release the reference
this.head++
// Compact occasionally so the array cannot grow without bound.
if (this.head > 32 && this.head * 2 >= this.items.length) {
this.items = this.items.slice(this.head)
this.head = 0
}
return value
}
get size() {
return this.items.length - this.head
}
}
const demoQueue = new Queue()
for (const n of [1, 2, 3]) demoQueue.enqueue(n)
console.log(demoQueue.dequeue(), demoQueue.dequeue()) // 1 2
console.log(demoQueue.size) // 1Moving a pointer instead of the data makes dequeue O(1). The occasional compaction keeps memory proportional to the queue's actual contents rather than everything ever enqueued.
In practice
For interview-sized inputs, shift() is usually accepted - but say that you know it is O(n) and that you would use an index for large inputs. That sentence is often the whole point of the question.