Queue

What is it?

Some problems need to be processed in the exact order they arrived — a printer processing print jobs, customer support tickets, tasks waiting to run. A queue models this directly: items are added at the back and removed from the front, so whatever arrived first leaves first.

This rule is called FIFO — First In, First Out.

Explain like I'm 10

A queue is like a line at a coffee shop. New people join at the back, and the person who's been waiting longest is always served next, from the front.

Examples

Using an array as a queue

const queue = [];

queue.push("first");  // ["first"]
queue.push("second");  // ["first", "second"]

console.log(queue.shift()); // "first" — removes and returns the front item
console.log(queue);         // ["second"]

push adds to the back; shift removes from the front — together they behave like a queue. Note that shift is O(n) on a plain array since every remaining item shifts down.

How it works

A queue exposes two main operations: enqueue (add to the back) and dequeue (remove from the front). Conceptually both should be O(1); in JavaScript, using a plain array's .shift() is actually O(n) because everything has to shift down, so real-world queues are often implemented with a linked list to keep both ends O(1).

enqueue("A")  enqueue("B")  dequeue()
     ↓             ↓            ↓
   [A]           [A,B]      returns "A", leaves [B]

Why does it exist?

Queues naturally model anything processed in arrival order: task scheduling, message processing, handling requests in the order they came in, and breadth-first traversal of trees and graphs.

When to use it

Reach for a queue whenever things must be handled in the exact order they arrived — a task queue, a message queue, print jobs, or breadth-first traversal of a tree or graph.

When not to use it

If the most recent item should be handled first instead of the oldest, you want a stack, not a queue. And for a high-throughput queue in real code, avoid a plain array's .shift() — reach for a linked-list-based queue or a dedicated library instead.

Common mistakes

• Confusing a queue's FIFO order with a stack's LIFO order.

• Using .shift() on a large array in performance-sensitive code without realizing it's O(n), not O(1).

• Forgetting to check whether a queue is empty before dequeuing.

Practice exercises

1. Easy:

   Implement a Queue class with enqueue and dequeue methods.

2. Medium:

   Use a queue to simulate people being served in a waiting line, printing the order they're served in.

3. Hard:

   Use a queue to implement a breadth-first traversal over a simple tree of nested objects.

Interview questions

What does FIFO mean?

First In, First Out — the earliest added item is always the first one removed.

What's a real-world use of a queue in software?

Task/job scheduling, request handling, and breadth-first search over trees and graphs.

Why is `.shift()` on a JavaScript array not ideal for a high-performance queue?

Because it's O(n) — every remaining element has to move down by one index. A linked-list-based queue keeps both ends O(1).

What is a circular buffer (ring buffer), and how does it give a queue O(1) enqueue and dequeue using a fixed-size array?

It reuses a fixed-size array by tracking a head index (where the next dequeue reads from) and a tail index (where the next enqueue writes to), both wrapping back to 0 via modulo once they reach the end of the array. Since neither operation shifts existing elements — they just read/write at the tracked index and advance it — both stay O(1).

In a circular buffer, `head` and `tail` can both equal the same index whether the buffer is empty or completely full — how do implementations tell the two apart?

By keeping a separate count (or size) field alongside head/tail — comparing head/tail alone is ambiguous. Some implementations instead reserve one array slot as always-unused, so 'full' means (tail + 1) % capacity === head, distinct from 'empty' meaning head === tail.

Walk through enqueueing A, B, C and then dequeuing once, on an initially empty circular buffer of capacity 4. Where do `head` and `tail` end up?

Start: head=0, tail=0, count=0. enqueue(A): buffer[0]=A, tail becomes 1, count=1. enqueue(B): buffer[1]=B, tail becomes 2, count=2. enqueue(C): buffer[2]=C, tail becomes 3, count=3. dequeue(): returns buffer[head]=A, head becomes 1, count=2. Final state: head=1, tail=3, count=2, holding B and C.

Why must resizing a full circular buffer copy elements starting from `head`, rather than just copying the raw backing array index-by-index?

The logical order of items wraps around once tail has passed index 0, so raw array order (index 0, 1, 2, ...) no longer matches insertion order — copying it directly would scramble which item is oldest. Copying starting from head and wrapping around exactly count times reproduces the correct logical order in the new, larger array.

What is a deque (double-ended queue), and how does it differ from a plain queue?

A deque supports O(1) insertion and removal at both ends — front and back — rather than only enqueue-at-back and dequeue-at-front. A plain queue can be thought of as a deque restricted to just those two operations.

What is a priority queue, and what does it typically use for insert/extract, along with the complexity of those operations?

A priority queue always returns the highest- (or lowest-) priority item next, regardless of arrival order. It's typically implemented with a binary heap: insert is O(log n), extract-min/max is O(log n), and peeking at the top priority item is O(1).

Why doesn't a plain unsorted list or a sorted array make a good priority queue?

An unsorted list needs an O(n) scan to find the highest-priority item on every extraction. A sorted array keeps extraction O(1) but every insertion costs O(n) to shift elements and keep it sorted. A binary heap instead gives O(log n) for both insert and extract, which balances much better when both operations happen repeatedly.

Building a binary heap from n elements one at a time (n inserts) costs O(n log n) — but there's a way to build one from an existing array in O(n). What is it, and why is it faster?

Bottom-up heapify: starting from the last non-leaf node and working backward to the root, sift each node down into place. Most nodes sit near the bottom of the tree and need very few swaps to settle, and the total work across all nodes — weighted by how many are near the bottom versus the top — sums to O(n), not O(n log n), unlike inserting one at a time into an initially empty heap.

What is a monotonic queue (or deque), and what classic problem does it solve in O(n) instead of O(n·k)?

The sliding window maximum problem. A monotonic deque keeps only indices whose values are in strictly decreasing order from front to back; before pushing a new index, any indices at the back with smaller values are popped off, since they can never be the max again once a larger, later value is in the window. The front always holds the current window's max, and since each index is pushed and popped at most once overall, the whole array is processed in O(n) instead of recomputing each window's max from scratch.

How does breadth-first search (BFS) use a queue, and what happens if you swap in a stack instead?

BFS enqueues a node's newly discovered neighbors and dequeues from the front, so nodes are explored in the order they were discovered — level by level. Swapping in a stack means the most recently discovered node gets explored next instead, which produces depth-first order — a genuinely different traversal, not just a slower BFS.

Why is a queue (not a stack) the structure behind a level-order tree traversal?

Level order requires visiting every node at depth d before any node at depth d+1. A queue's FIFO order guarantees that: nodes are dequeued (and their children enqueued) in the same order they were discovered, so an entire level drains before the next level's nodes — enqueued after them — are ever reached.

What's the amortized time complexity of dequeue in a queue implemented with two stacks (`in` and `out`), and why can a single call still cost O(n)?

Amortized O(1). A dequeue that finds out empty must pop every element off in and push it onto out — an O(n) operation that one time — but each element makes that in-to-out move at most once during its entire lifetime in the queue, so the total cost across n operations is bounded by O(n), spreading to O(1) per operation on average.

Why does a linked-list-based queue need a reference to both the head and the tail node, when a stack built the same way only needs one?

A stack only ever touches one end (the top), so a single pointer suffices. A queue touches both ends — dequeuing from the front, enqueuing at the back — so without a direct tail reference, enqueuing would require walking the entire list from head to find the last node, making it O(n) instead of O(1).

What is a blocking queue, and where does it show up in concurrent programming?

A queue where dequeuing from an empty queue (or enqueuing to a full, bounded one) makes the calling thread wait instead of erroring immediately. It's the backbone of producer-consumer designs — like a thread pool's task queue — letting producers and consumers safely hand off work without busy-polling.

How does a JavaScript runtime's event loop use a queue?

Callbacks scheduled as macrotasks — like setTimeout callbacks or I/O completions — are placed on a task queue and executed one at a time, in the order they were queued (FIFO), interleaved with rendering and other work. It's a direct, real-world use of the queue data structure inside the language runtime itself.

What's the time and space complexity of enqueue/dequeue on a well-implemented queue (linked list or circular buffer), versus using `.shift()` on a plain array?

O(1) time and O(1) extra space per operation for both a linked-list-based queue (with head and tail pointers) and a circular buffer (until it needs to resize). .shift() on a plain array is O(n) time, since every remaining element must move down one index to fill the gap.

Scenario: a task scheduler must process tasks in submission order, and thousands are submitted per second. Why would `array.push()` + `array.shift()` become a bottleneck, and what's the fix?

.shift() is O(n), so draining n tasks costs O(n²) total as the queue empties — at high throughput this quickly dominates. A circular buffer or linked-list-based queue keeps both enqueue and dequeue O(1), so processing n tasks costs O(n) overall instead.

What's a common off-by-one bug when implementing a circular buffer's wraparound?

Forgetting the modulo operator when advancing head/tail — writing tail = tail + 1 instead of tail = (tail + 1) % capacity — which lets the index walk straight past the end of the backing array instead of wrapping back to 0.

What happens if you call dequeue on an empty queue without checking first?

Depending on the implementation, it either throws, returns undefined/null, or — in a hand-rolled circular buffer that tracks raw indices without a count check — reads stale leftover data or corrupts the head/tail bookkeeping. Checking emptiness before dequeuing avoids all of these failure modes.

Compare a circular-buffer-based queue to a linked-list-based queue in terms of memory layout and cache behavior.

A circular buffer stores elements contiguously in one pre-allocated array, so sequential access is cache-friendly, though its capacity is fixed until an explicit O(n) resize. A linked-list-based queue never needs a bulk resize and grows one node at a time, but each node is typically a separate heap allocation, making traversal more likely to cause cache misses, plus a per-node pointer's extra memory cost.

Trace these operations on an initially empty queue: enqueue(1), enqueue(2), dequeue(), enqueue(3), dequeue(), dequeue(). What does each dequeue return, and what's left at the end?

enqueue(1) → [1]. enqueue(2) → [1,2]. dequeue() returns 1, leaving [2]. enqueue(3) → [2,3]. dequeue() returns 2, leaving [3]. dequeue() returns 3, leaving it empty — each dequeue removes from the front, in the same order items were enqueued.

Why would you choose a priority queue over a regular queue for a hospital ER's 'next patient' system?

A regular queue serves strictly in arrival order (FIFO), but an ER needs to serve the most urgent patient next, regardless of arrival time. A priority queue orders by an assigned priority (urgency) instead of arrival time, extracting the highest-priority patient in O(log n) via a heap, each time a slot opens up.

What single difference between a stack and a queue — which end each operation happens at — changes the order items come out in?

A stack adds and removes from the same end (the top): LIFO, most recently added comes out first. A queue adds at one end and removes from the other: FIFO, the oldest comes out first. The exact same sequence of insertions comes back out in opposite orders from the two structures.

What's the amortized time complexity of processing an entire n-element array through a monotonic queue (sliding window maximum), given that a single step can pop several elements at once?

O(n) amortized. A single new element can trigger popping several smaller elements from the back of the deque, but every element is pushed onto the deque exactly once and popped at most once across the whole run — so the total number of push/pop operations over all n steps is bounded by O(n), not O(n) per individual step.

Why is a queue the right structure (not a stack) for a print spooler shared by many users?

Fairness: the first job submitted should be the first one printed, regardless of who submitted it — exactly FIFO. A stack would print the most recently submitted job first, so an early job could be starved indefinitely by a steady stream of newer ones, the opposite of what a shared print queue needs.

What's the difference between a bounded queue and an unbounded queue, and what does 'bounded' change about enqueue?

An unbounded queue can grow to hold as many items as available memory allows. A bounded queue has a fixed maximum capacity, so an enqueue attempt while it's already full must either reject the new item, block until space frees up (as in a blocking queue), or evict something (like the oldest item) — rather than always succeeding immediately.