JavaScript stacks and queues
Use an array as a stack, and write a queue that does not shift the whole array on every removal.
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.head++;
return value;
}
get size() {
return this.items.length - this.head;
}
}
const stack = [];
stack.push("a");
stack.push("b");
stack.push("c");
console.log(stack.pop(), stack.pop(), stack.length);
const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
console.log(queue.dequeue(), queue.dequeue(), queue.size);
console.log(queue.dequeue(), queue.dequeue());c b 1 1 2 1 3 undefined
Explanation
A stack is last-in, first-out, and a JavaScript array already supports it: push adds to the end and pop removes from the end, both in O(1). A queue is first-in, first-out. Using push and shift works, but shift removes from the front and may move every remaining element, which is O(n) for a large array.
A better queue keeps a head index. Dequeue reads the element at the head and moves the index forward, in O(1). Occasionally the consumed part at the front can be discarded to free memory. Stacks are used for undo history and depth-first search, and queues for task scheduling and breadth-first search.
Explore the dry run
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.head++; return value; } get size() { return this.items.length - this.head; }} const stack = [];stack.push("a");stack.push("b");stack.push("c");console.log(stack.pop(), stack.pop(), stack.length); const queue = new Queue();queue.enqueue(1);queue.enqueue(2);queue.enqueue(3);console.log(queue.dequeue(), queue.dequeue(), queue.size);console.log(queue.dequeue(), queue.dequeue());Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| After three pushes the stack holds a, b, c with c on top. | — | — | |
| pop returns the most recently added items first: c, then b. | — | c b 1 | |
| Dequeue just moves the head forward instead of shifting the array. | — | c b 1 | |
| The oldest items come out first: 1, then 2. One item remains. | — | c b 1 1 2 1 | |
| The third dequeue returns 3 and the fourth finds the queue empty. | — | c b 1 1 2 1 3 undefined |
Cost and common mistakes
push, pop, enqueue, and dequeue are O(1) (amortized for push).
- The items array in this queue never shrinks. A production queue periodically compacts it or uses a linked list or ring buffer.
- pop and shift return undefined on an empty array, which is also a valid value to store. Check the length when that matters.
- Arrays with push and pop make the best stacks. Do not use shift or unshift in loops over big arrays.
Try it yourself
Which structure would you use for the browser's back button?
Reveal answer and reasoning
A stack: the most recently visited page is the first one you go back to.