Part 10 · Lesson 39 · read
Queues and Deques
First in, first out, and a queue you can use from both ends.
On this page
First in, first out
A queue is like a line at a ticket counter. People join at the back and are served from the front. So whoever arrived first leaves first. This rule is FIFO: first in, first out. In code, a queue is a collection of values where you add at one end (the back) and remove at the other end (the front). It is the opposite of a stack (a stack uses one end only). The operations are:
- enqueue — add to the back.
- dequeue — remove from the front and return it.
- peek — look at the front.
Queues fit anything where the order of arrival matters. Examples are print jobs and messages waiting for a worker (a program that handles them one by one). Later in the course, you will also use a queue for breadth-first search (visiting a tree or graph level by level).
const queue = [];queue.push("a"); // enqueue at the backqueue.push("b");queue.push("c");console.log(queue.shift()); // a dequeue from the frontconsole.log(queue.shift()); // bconsole.log(queue[0]); // c peek the frontconsole.log(queue.length); // 1Why shift() is a trap
Using push with shift works, and it is fine for small data. But shift() removes the first item. By the rules of the language, every other item then has to move one place to the left. That makes each dequeue O(n), so the time grows with the size of the array. (O(n) means the work grows in step with n, the number of items.) Engines such as V8 (the part of Chrome and Node.js that runs JavaScript) have tricks that make shift fast for arrays up to a certain size. But those tricks can change, and they stop helping on large arrays. In an interview, you can say "shift is O(n), so I will track a head index instead". That shows you know how arrays really work.
shift() once per node on a queue of 100,000 items. It can quietly turn an O(n) algorithm into an O(n²) one. If you are not sure, use a head index.A queue with a head index
Do not remove the front item. Leave it in place and move a head index (a number that points to the front item) forward. Dequeue and enqueue are both O(1). The array only grows, so now and then cut off the part you have already used. This clean-up is "amortised" O(1), which means its cost averages out to O(1) per operation.
class Queue { constructor() { this.items = []; this.head = 0; } // head = index of the front item enqueue(x) { this.items.push(x); } dequeue() { if (this.head >= this.items.length) return undefined; const x = this.items[this.head]; this.items[this.head] = undefined; // drop the old value so its memory can be freed this.head++; if (this.head > 1000 && this.head * 2 > this.items.length) { // compact now and then so the array does not grow forever this.items = this.items.slice(this.head); this.head = 0; } return x; } peek() { return this.items[this.head]; } get size() { return this.items.length - this.head; }}const q = new Queue();q.enqueue(1); q.enqueue(2); q.enqueue(3);console.log(q.dequeue()); // 1console.log(q.peek()); // 2console.log(q.size); // 2A queue made of two stacks
This is a classic question: build a queue using only stacks. Keep an in-stack for new items. For pop and peek, use an out-stack. When the out-stack is empty, pour the whole in-stack into it. Pouring reverses the order. So the oldest item ends up on top, and that is exactly the item a queue must return.
class MyQueue { constructor() { this.inStack = []; this.outStack = []; } push(x) { this.inStack.push(x); } // new items always go on the in-stack #moveIfNeeded() { if (this.outStack.length === 0) { while (this.inStack.length) this.outStack.push(this.inStack.pop()); // reversing a stack puts the OLDEST on top } } pop() { this.#moveIfNeeded(); return this.outStack.pop(); } peek() { this.#moveIfNeeded(); return this.outStack[this.outStack.length - 1]; } empty() { return this.inStack.length === 0 && this.outStack.length === 0; }}const q = new MyQueue();q.push(1); q.push(2); q.push(3);console.log(q.pop()); // 1 (moves 1,2,3 across; 1 ends on top)q.push(4);console.log(q.pop()); // 2 (the out-stack still holds 2 and 3, so no refill)console.log(q.pop()); // 3console.log(q.pop()); // 4 (out-stack empty: move 4 across)| Fact | Consequence |
|---|---|
| An item moves from the in-stack to the out-stack at most once | the total moving work is at most the number of pushes |
| Most pops find the out-stack already filled | they cost O(1) |
| One pop may move many items | one single operation can be O(n)... |
| ...but earlier pushes already paid for that work | amortised O(1) per operation |
Amortised means averaged over a whole series of operations. It is not a promise for each single operation.
The circular queue
A queue with a fixed capacity (a fixed maximum size) can reuse the space left behind by removed items. It does this by wrapping around the array, like a clock that goes from 12 back to 1. Keep the index of the front and the count of items. The next free slot is (head + size) % capacity. The modulo (%, the remainder after division) connects the end of the array back to its start. Keeping size as its own number also avoids the common mix-up between "empty" and "full".
class CircularQueue { constructor(k) { this.buf = new Array(k); this.cap = k; this.head = 0; this.size = 0; } enQueue(x) { if (this.size === this.cap) return false; this.buf[(this.head + this.size) % this.cap] = x; // the slot after the last item, wrapping around this.size++; return true; } deQueue() { if (this.size === 0) return false; this.head = (this.head + 1) % this.cap; this.size--; return true; } Front() { return this.size === 0 ? -1 : this.buf[this.head]; } Rear() { return this.size === 0 ? -1 : this.buf[(this.head + this.size - 1) % this.cap]; }}const q = new CircularQueue(3);console.log(q.enQueue(1), q.enQueue(2), q.enQueue(3), q.enQueue(4)); // true true true falseconsole.log(q.Rear()); // 3q.deQueue(); // frees slot 0console.log(q.enQueue(4)); // true (4 is stored in slot 0, wrapping around)console.log(q.Rear()); // 4Deque: both ends
A deque (say "deck"; it means double-ended queue) lets you add and remove at both ends. It can act as a stack, as a queue, or as something in between. JavaScript has no built-in deque. With an array, the back is fast (push, pop) and the front is slow (shift, unshift). In an interview, you can write "deque" and use an array (or a head-index class). Add a note that real code would use a proper deque.
Sliding window maximum
The sliding window maximum problem asks for the biggest value in every window of size k (a window is k values side by side that slides along the array one place at a time). Checking each window again from scratch costs O(n·k). The trick is to keep only the candidates that could still become the biggest value. Keep them in a deque of indices:
- Remove the front if its index is now outside the window.
- Remove from the back every value that is not larger than the new value. It is older and smaller. So it can never beat the new value while the new value is in the window.
- Add the new index at the back. The values in the deque now go down from front to back.
- Once the first window is full, the front of the deque is the biggest value.
function maxSlidingWindow(nums, k) { const dq = []; // indices; their values are in DECREASING order, so dq[0] is the window maximum const out = []; for (let i = 0; i < nums.length; i++) { while (dq.length && dq[0] <= i - k) dq.shift(); // 1. front fell out of the window while (dq.length && nums[dq[dq.length - 1]] <= nums[i]) dq.pop(); // 2. smaller values at the back can never be the maximum again dq.push(i); // 3. add the new index if (i >= k - 1) out.push(nums[dq[0]]); // 4. a full window: the front is its maximum } return out;}console.log(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3)); // [3, 3, 5, 5, 6, 7]console.log(maxSlidingWindow([1], 1)); // [1]Every index enters and leaves the deque at most once, so the total work is O(n). (With a plain array, dq.shift() itself can cost up to O(k). Question 4 shows a version with a head index where every step is truly O(1).)
Traced: window maximum of 1 3 -1 -3 5 3 6 7
The deque (a list you can add to and remove from at both ends) holds positions (indices). Their values go down from front to back. The front is always the biggest value in the current window.
▶const dq = [];2const out = [];3for (let i = 0; i < nums.length; i++) {4 while (dq.length && dq[0] <= i - k) dq.shift();5 while (dq.length && nums[dq[dq.length - 1]] <= nums[i]) dq.pop();6 dq.push(i);7 if (i >= k - 1) out.push(nums[dq[0]]);8}| k | 3 |
| dq | [] |
| out | [] |
Practice questions
First decide which end each operation uses. That tells you whether you need a stack, a queue or a deque.
Build a FIFO queue using only stack operations: push and pop at the end, peek, and size or empty checks.
Hint 1
Hint 2
Show all 2 solutions with explanations
Keep one stack where the front of the queue is on top. To push, empty it into a helper stack, add the new item, and pour everything back.
class SlowQueue { constructor() { this.s = []; } push(x) { const tmp = []; while (this.s.length) tmp.push(this.s.pop()); this.s.push(x); while (tmp.length) this.s.push(tmp.pop()); } pop() { return this.s.pop(); } peek() { return this.s[this.s.length - 1]; } empty() { return this.s.length === 0; }}const q = new SlowQueue();q.push(1); q.push(2);console.log(q.peek()); // 1console.log(q.pop()); // 1console.log(q.empty()); // falseIt gives the right answer, but every push costs O(n).
Push onto the in-stack. For pop and peek, first check the out-stack. If it is empty, pour the in-stack into it.
class MyQueue { constructor() { this.inS = []; this.outS = []; } push(x) { this.inS.push(x); } #fill() { if (!this.outS.length) while (this.inS.length) this.outS.push(this.inS.pop()); } pop() { this.#fill(); return this.outS.pop(); } peek() { this.#fill(); return this.outS[this.outS.length - 1]; } empty() { return !this.inS.length && !this.outS.length; }}const q = new MyQueue();q.push(1); q.push(2);console.log(q.peek()); // 1console.log(q.pop()); // 1console.log(q.empty()); // falseEach item is moved only once. So the average cost is O(1) per operation, even though one single pop may cost O(n).
Use the two-stack version. Say the word "amortised" (averaged over many operations). (LeetCode 232.)
Build a LIFO stack using only queue operations: enqueue at the back, dequeue from the front, peek, size, and empty.
Hint 1
Show all 2 solutions with explanations
Push the new item. Then move the size − 1 older items, one by one, from the front to the back. Now the newest item is at the front.
class MyStack { constructor() { this.q = []; this.head = 0; } get size() { return this.q.length - this.head; } #dequeue() { return this.q[this.head++]; } push(x) { this.q.push(x); for (let i = 0; i < this.size - 1; i++) this.q.push(this.#dequeue()); // rotate the older items behind x } pop() { return this.#dequeue(); } top() { return this.q[this.head]; } empty() { return this.size === 0; }}const s = new MyStack();s.push(1); s.push(2);console.log(s.top()); // 2console.log(s.pop()); // 2console.log(s.empty()); // falsepush is O(n). pop, top and empty are O(1). (The head index avoids shift. In this short example, the used part at the start of the array is never cleaned up.)
Pushing is a plain enqueue. To pop, move all items except the last one from the front to the back. Then dequeue the last one.
class MyStack { constructor() { this.q = []; } push(x) { this.q.push(x); } // O(1) pop() { for (let i = 0; i < this.q.length - 1; i++) this.q.push(this.q.shift()); return this.q.shift(); // the former last item } top() { const x = this.pop(); this.q.push(x); return x; } empty() { return this.q.length === 0; }}const s = new MyStack();s.push(1); s.push(2); s.push(3);console.log(s.pop()); // 3console.log(s.top()); // 2Now pop costs O(n). In both versions, one side (push or pop) has to pay O(n).
The first one keeps top and pop simple. Say that one operation has to be O(n). (LeetCode 225.)
Design a queue with a fixed maximum size that reuses free space. Every operation must be O(1).
Hint 1
Hint 2
% capacity to wrap an index that goes past the end back to 0.Show all 2 solutions with explanations
The slot for a new item is (head + size) % cap. Dequeue moves head forward by one slot and wraps around at the end. The last item (Rear) is at (head + size − 1) % cap.
class CircularQueue { constructor(k) { this.buf = new Array(k); this.cap = k; this.head = 0; this.size = 0; } enQueue(x) { if (this.size === this.cap) return false; this.buf[(this.head + this.size) % this.cap] = x; this.size++; return true; } deQueue() { if (this.size === 0) return false; this.head = (this.head + 1) % this.cap; this.size--; return true; } Front() { return this.size === 0 ? -1 : this.buf[this.head]; } Rear() { return this.size === 0 ? -1 : this.buf[(this.head + this.size - 1) % this.cap]; } isEmpty() { return this.size === 0; } isFull() { return this.size === this.cap; }}const q = new CircularQueue(3);console.log(q.enQueue(1), q.enQueue(2), q.enQueue(3), q.enQueue(4)); // true true true falseconsole.log(q.Rear()); // 3console.log(q.deQueue()); // trueconsole.log(q.enQueue(4)); // trueconsole.log(q.Rear()); // 4All operations are O(1). Storing size removes a problem: "head equals tail" could mean either empty or full.
Make k + 1 slots and keep a head and a tail. Empty means head === tail. Full means (tail + 1) % (k + 1) === head. One slot is left empty on purpose, so you can tell empty and full apart.
class CircularQueue { constructor(k) { this.buf = new Array(k + 1); this.n = k + 1; this.head = 0; this.tail = 0; } isEmpty() { return this.head === this.tail; } isFull() { return (this.tail + 1) % this.n === this.head; } enQueue(x) { if (this.isFull()) return false; this.buf[this.tail] = x; this.tail = (this.tail + 1) % this.n; return true; } deQueue() { if (this.isEmpty()) return false; this.head = (this.head + 1) % this.n; return true; } Front() { return this.isEmpty() ? -1 : this.buf[this.head]; } Rear() { return this.isEmpty() ? -1 : this.buf[(this.tail - 1 + this.n) % this.n]; }}const q = new CircularQueue(2);console.log(q.enQueue(7), q.enQueue(8), q.enQueue(9)); // true true falseconsole.log(q.Rear()); // 8Same speed. Look at (tail − 1 + n) % n. In JavaScript, -1 % n is -1, not a valid index. So you must add n before you take the remainder.
Use the first one. It is easier to understand. (LeetCode 622.)
A window of size k slides from left to right over nums. For every window, report the biggest value.
Hint 1
Hint 2
Show all 2 solutions with explanations
For each window, look at all k values and take the biggest.
function maxSlidingWindow(nums, k) { const out = []; for (let i = 0; i + k <= nums.length; i++) { let best = -Infinity; for (let j = i; j < i + k; j++) best = Math.max(best, nums[j]); out.push(best); } return out;}console.log(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3)); // [3, 3, 5, 5, 6, 7]O(n·k). If n and k are both 10⁵, this is far too slow.
Keep the indices of values that go down in an array used as a deque. Move head forward to remove from the front. Use pop to remove from the back.
function maxSlidingWindow(nums, k) { const dq = []; // indices let head = 0; // dq[head] is the front const out = []; for (let i = 0; i < nums.length; i++) { if (head < dq.length && dq[head] <= i - k) head++; // front left the window while (dq.length > head && nums[dq[dq.length - 1]] <= nums[i]) dq.pop(); // drop smaller from the back dq.push(i); if (i >= k - 1) out.push(nums[dq[head]]); } return out;}console.log(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3)); // [3, 3, 5, 5, 6, 7]console.log(maxSlidingWindow([9, 8, 7], 2)); // [9, 8]console.log(maxSlidingWindow([1], 1)); // [1]O(n) time. Each index is pushed once and removed at most once. You need at most one front removal per step, because the window moves only one place at a time.
Say the brute force way first, then show the deque. (LeetCode 239.)
For each new ping(t), count how many pings happened in the last 3000 milliseconds, including the current one.
Hint 1
Show all 2 solutions with explanations
Enqueue t. Keep removing from the front while the front is older than t − 3000. The size of the queue is the answer.
class RecentCounter { constructor() { this.q = []; this.head = 0; } ping(t) { this.q.push(t); while (this.q[this.head] < t - 3000) this.head++; return this.q.length - this.head; }}const r = new RecentCounter();console.log(r.ping(1)); // 1console.log(r.ping(100)); // 2console.log(r.ping(3001)); // 3console.log(r.ping(3002)); // 3Each timestamp is added once and removed at most once. So the average cost is O(1) per ping.
Keep every timestamp in an array. It is already sorted, because calls arrive in time order. Use binary search to find the first timestamp that is ≥ t − 3000.
class RecentCounter { constructor() { this.times = []; } ping(t) { this.times.push(t); let lo = 0, hi = this.times.length; while (lo < hi) { const mid = (lo + hi) >> 1; if (this.times[mid] < t - 3000) lo = mid + 1; else hi = mid; } return this.times.length - lo; }}const r = new RecentCounter();console.log(r.ping(1)); // 1console.log(r.ping(3001)); // 2console.log(r.ping(3002)); // 2O(log n) per ping, and the memory keeps growing without limit. So the queue is better. We show this one to connect with the binary search lesson.
Use the queue. (LeetCode 933.)
People stand in a line. Each person wants tickets[i] tickets and buys one per second. If they want more, they go to the back of the line. How long until person k has all their tickets?
Hint 1
Show all 2 solutions with explanations
Use a queue of indices. Take the front person. They buy one ticket (1 second). If they still need more, send them to the back. Stop when person k is done.
function timeRequiredToBuy(tickets, k) { const need = [...tickets]; const queue = tickets.map((_, i) => i); let head = 0, time = 0; while (true) { const i = queue[head++]; need[i]--; time++; if (need[i] === 0) { if (i === k) return time; } else queue.push(i); }}console.log(timeRequiredToBuy([2, 3, 2], 2)); // 6console.log(timeRequiredToBuy([5, 1, 1, 1], 0)); // 8O(total tickets) time. This can be large if one person wants many tickets.
Person k buys tickets[k] times. A person before k (or k itself) buys at most tickets[k] tickets. A person after k buys at most tickets[k] − 1 tickets before k finishes.
function timeRequiredToBuy(tickets, k) { let time = 0; for (let i = 0; i < tickets.length; i++) { time += Math.min(tickets[i], i <= k ? tickets[k] : tickets[k] - 1); } return time;}console.log(timeRequiredToBuy([2, 3, 2], 2)); // 6console.log(timeRequiredToBuy([5, 1, 1, 1], 0)); // 8O(n). A good path in an interview is to act it out first and then spot the formula. (LeetCode 2073.)
Start with the simulation. Then show the formula.
Students stand in a queue. Each student prefers sandwich type 0 or 1. A stack of sandwiches (also 0 or 1) is on the table. The front student takes the top sandwich if it matches. If not, the student goes to the back. Return how many students never eat.
Hint 1
Show all 2 solutions with explanations
Keep sending students to the back until the front student matches the top sandwich. If the whole line goes round once with no match, everyone left is stuck.
function countStudents(students, sandwiches) { const queue = [...students]; let top = 0, rotations = 0; while (queue.length && rotations < queue.length) { if (queue[0] === sandwiches[top]) { queue.shift(); top++; rotations = 0; } else { queue.push(queue.shift()); rotations++; } } return queue.length;}console.log(countStudents([1, 1, 0, 0], [0, 1, 0, 1])); // 0console.log(countStudents([1, 1, 1, 0, 0, 1], [1, 0, 0, 0, 1, 1])); // 3The worst case is O(n²) with these array operations.
The order of students does not matter for who can eat. Only the counts matter. Go through the sandwiches. If no student wants the top one, stop. The students left are stuck.
function countStudents(students, sandwiches) { const want = [0, 0]; for (const s of students) want[s]++; for (let i = 0; i < sandwiches.length; i++) { if (want[sandwiches[i]] === 0) return sandwiches.length - i; // nobody left wants this one want[sandwiches[i]]--; } return 0;}console.log(countStudents([1, 1, 0, 0], [0, 1, 0, 1])); // 0console.log(countStudents([1, 1, 1, 0, 0, 1], [1, 0, 0, 0, 1, 1])); // 3O(n) time and O(1) space. This looks like a simulation question, but it becomes simple counting once you ask what really matters. (LeetCode 1700.)
Use counting, after you mention the simulation.
Make it stick
- Explain FIFO. Explain why
Array.shift()is a poor way to dequeue. - Describe how two stacks can make a queue. Explain why each item moves at most once.
- Write the formula for the index of the next free slot in a circular queue. Explain what the modulo does.
- Say the rule that always stays true for the sliding-window deque (an invariant). Name the two kinds of removal.
Revisit schedule: solve two of the questions again tomorrow, again in 3 days, and once more in a week — without looking at the answers. Each time it will feel easier. That is the memory forming.
What's next
Lesson 40 finishes this part with the monotonic stack (a stack whose values always go up or always go down). You will solve: next greater element, daily temperatures, stock span, the largest rectangle in a histogram, and trapping rain water.
Practise on LeetCode
Real interview problems that use exactly what this lesson teaches. Solve them in JavaScript after the practice questions above.
Published by Jainik · Last updated · How these lessons are made
Keep learning
Part of the study guide
Related series