cf.completefrontend
STACKS & QUEUES · FOUNDATION

Queue

A list where items join at the back and leave from the front, so the first item in is the first one out.

Time O(total turns)Space O(total turns)8 practice problemsStep-through picture

The idea

A queue is a line. New items join at the back (enqueue) and items are served from the front (dequeue). Nobody cuts in, so items leave in the same order they arrived: first in, first out.

Queues appear whenever work must be handled fairly in arrival order: jobs waiting for a worker, messages waiting to be sent, or places to visit in breadth-first search, where everything one step away is handled before anything two steps away.

In JavaScript, array.shift() removes the front item but moves every other item down by one, which is slow for big queues. A simple fix is to keep a head index of the front item and move it forward instead of shifting.

An everyday example

A line at a coffee shop

Customers join the end of the line and the barista serves whoever is at the front. If a big order needs more time, a fair shop serves part of it and asks the customer to rejoin the back of the line, so one big order can't block everyone.

How the example maps to the code
In the exampleIn the code
The linequeue
A customer joins the endqueue.push(job)
Serving the front customerconst job = queue[head]; head++
Rejoining the back with the rest of the orderqueue.push({ id, time: job.time - slice })
Nobody left in linehead === queue.length

From the slow way to queue

  1. Start with the obvious queue in JavaScript: an array where push adds to the back and shift takes from the front. It reads well, but shift moves every remaining item one slot to the left. Each dequeue costs O(n), so serving n items costs O(n^2). On 100,000 items that is billions of moves.
  2. The moves are wasted. Once an item is served, nothing ever looks at its slot again, so there is no reason to close the gap. Instead of moving the items toward the front, move the front toward the items: keep a number head, the index of the item that is first in line.
  3. Now dequeue is queue[head] followed by head++, and enqueue is still push. The queue is empty when head has caught up with queue.length. Items keep their arrival order because they only ever join at the back and leave at the front.
  4. Round-robin scheduling shows why the order matters. A job that needs more time than one slice runs for one slice and then joins the back again, behind every job already waiting. So every job gets a turn before any job gets a second one. That loop is a queue with a head index.

How it works

  1. Put the starting items in an array queue in arrival order, and set head = 0, the index of the front item.
  2. While head < queue.length, the queue isn't empty.
  3. Take the front item, job = queue[head], and move head forward by one.
  4. Handle it. Here, if job.time fits in one slice, the job finishes and its id goes into finished.
  5. Otherwise run it for one slice and push what is left of it onto the back of the queue.
  6. When the queue is empty, finished holds the jobs in the order they completed.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function roundRobin(jobs, slice) {
  2. const queue = jobs.map((time, id) => ({ id, time }));
  3. let head = 0;
  4. const finished = [];
  5. while (head < queue.length) {
  6. const job = queue[head];
  7. head++;
  8. if (job.time <= slice) {
  9. finished.push(job.id);
  10. } else {
  11. queue.push({ id: job.id, time: job.time - slice });
  12. }
  13. }
  14. return finished;
  15. }

How fast it is

TimeO(total turns)
Extra memoryO(total turns)

Each turn is one O(1) dequeue and at most one O(1) enqueue. A job needing t units takes about t / slice turns, and every turn leaves one entry in the array.

  • Best caseO(n)

    Every job fits in one slice, like jobs = [1, 2, 3] with slice = 3. There are exactly n turns and nothing rejoins.

  • Average caseO(total turns)

    Mixed job sizes. A job of size t takes ceil(t / slice) turns, and each turn is one O(1) dequeue plus at most one O(1) enqueue.

  • Worst caseO(T)

    slice = 1, so every unit of work is its own turn and the number of turns equals T, the sum of all job times.

Common mistakes

  • Using shift() in a loop over a big queue, which turns an O(n) loop into O(n^2). Keep a head index or use a ring buffer.
  • Using pop() by habit. That takes from the back and turns the queue into a stack.
  • Checking queue.length === 0 to see if the queue is empty while using a head index. With a head index, the queue is empty when head === queue.length.
  • Changing the queue while looping over it with for...of and expecting the loop to see only the original items.

When to use it

Look for these clues in a problem:

  • Items must be handled in the order they arrived.
  • The task simulates a line, a buffer, or turns that rotate (round robin).
  • You explore something level by level, nearest first: breadth-first search.
  • Work arrives over time and only the recent items matter, such as "requests in the last 3 seconds".

Check yourself

Answer each one in your head first, then open it.

Why is queue.length === 0 the wrong empty test here?

Served items stay in the array, so queue.length never shrinks. The queue is empty when head === queue.length.

How many turns do jobs of [5, 2, 7, 3] take with slice = 3?

7: ceil(5 / 3) = 2, ceil(2 / 3) = 1, ceil(7 / 3) = 3, and ceil(3 / 3) = 1.

What changes if you replace queue[head]; head++ with queue.pop()?

pop takes the newest item, so the structure becomes a stack. A job that rejoins would run again at once instead of waiting for the others.

Why does a short job finish before a long job that arrived earlier?

The long job uses one slice and goes to the back, so the short job reaches the front and finishes in its first turn. In the trace, J1 finished before J0.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 8 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The loop keeps one rule: queue[head] to queue[queue.length - 1] are the waiting jobs in the order they will be served, and everything before head has been served. At the start, every job is waiting in arrival order and head is 0, so the rule holds.

Each turn keeps the rule. Taking queue[head] and moving head forward removes the front job. A job that needs more time is pushed onto the back, after every job already waiting, which is exactly where first in, first out says a newcomer goes. Between two turns of the same job, every other waiting job gets exactly one turn.

The loop ends because every turn lowers some job's remaining time by slice, or finishes it. A job that needs t units takes ceil(t / slice) turns, here 2, 1, 3, and 1, so the total number of entries is finite: 7. When head reaches the last entry, every job has finished.

Going deeper

3 more ideas

Why first in, first out is fair

A job that rejoins the queue goes behind every job that was already waiting. So every waiting job gets a turn before any job gets a second turn. No job waits forever, and short jobs finish early instead of waiting behind long ones.

Why a head index instead of shift

queue.shift() removes the first item and moves every other item down one place, which costs O(n). Doing that for every item makes the whole loop O(n^2). Reading queue[head] and doing head++ costs O(1). The trade-off is that served items stay in the array; for long-running queues, a ring buffer or a linked list reuses that memory.

Cost

Each enqueue and dequeue is O(1). In the round-robin example, a job with time t is dequeued about t / slice times, so the total work is the sum of those turns. The queue holds at most one entry per waiting job plus the served ones before head.

Work it by hand

Every step in a table, with why

Run four jobs with a slice of 3 time units. Two jobs need more than one turn, so they rejoin the back of the line.

jobs = [5, 2, 7, 3], slice = 3

Stephead afterjobResultWaiting, front to backfinishedWhy
11J0 needs 5rejoins as J0 needs 2J1:2, J2:7, J3:3, J0:2[]5 > 3, so J0 runs for one slice and its remaining 2 units go to the back of the queue.
22J1 needs 2finishesJ2:7, J3:3, J0:2[1]2 <= 3, so J1 finishes in its first turn, before the longer J0.
33J2 needs 7rejoins as J2 needs 4J3:3, J0:2, J2:4[1]J2 runs one slice and joins the back behind J0's second turn.
44J3 needs 3finishesJ0:2, J2:4[1, 3]3 <= 3: a job that needs exactly one slice finishes, because the check is <=.
55J0 needs 2finishesJ2:4[1, 3, 0]J0 gets its second turn only after every other job had its first.
66J2 needs 4rejoins as J2 needs 1J2:1[1, 3, 0]J2 is the only job left, so it rejoins a queue where it is the only entry.
77J2 needs 1finishesempty[1, 3, 0, 2]head is 7 and queue.length is 7, so the queue is empty and the loop stops.

It returns [1, 3, 0, 2] after 7 turns. The array ends with 7 entries, one per turn: 4 starting jobs plus 3 rejoined ones, all before head.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
QueueO(1)O(n)Items must leave in arrival order and each enqueue and dequeue should be constant time. Here n counts every item ever pushed, since served ones stay before head.
Array with shiftO(n)O(n)Only for tiny queues. Every dequeue moves all the remaining items.
Ring bufferO(1)O(capacity)You know the most items that can wait at once and want memory that never grows.
Linked-list queueO(1)O(n)The size has no known limit and served items should be freed right away.

Extra memory: O(total turns): served entries stay in the array before head. A ring buffer or a linked-list queue would keep only the waiting jobs, O(n).

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Queue and the other approaches, on a scale where each line up is 10 times more steps.
  • Queue, Ring buffer, Linked-list queue O(1)
  • Array with shift O(n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Queue111
Array with shift101,0001 million
Ring buffer111
Linked-list queue111

Inputs that need care

5 tricky inputs
No jobs: jobs = []
head < queue.length is 0 < 0, which is false, so the loop never runs and the function returns [].
A job that needs exactly one slice
job.time <= slice is true, so it finishes in its first turn. Using < instead would send it round once more with 0 time left.
A job with time = 0
It finishes on its first turn, since 0 <= slice. It still waits behind the jobs in front of it.
slice = 0 or a negative slice
A job's time never gets smaller, so it rejoins forever and the loop never ends. Check that slice is positive before starting.
One huge job, jobs = [1000000], with slice = 1
The loop runs 1,000,000 turns and the array grows to 1,000,000 entries. If memory matters, drop the served part now and then, or use a ring buffer.

Variations and follow-ups

Twists interviewers add

Compact the served part

When head passes half the array's length, replace the array with queue.slice(head) and set head = 0. Each item is copied at most a few times over its life, so operations stay O(1) on average and memory stays close to the waiting count.

Ring buffer

With a known upper limit on waiting items, store them in a fixed array and wrap head and the back index round with % capacity. Nothing moves and no memory grows.

Breadth-first search

Put the start in the queue, then repeatedly take the front item and add its unvisited neighbors to the back. Because items leave in arrival order, everything one step away is handled before anything two steps away.

Priority queue

If jobs must be served by urgency instead of arrival, a heap replaces the queue. Each operation then costs O(log n) instead of O(1).

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "in the order they arrive", "first come, first served", "round robin", "level by level", or "nearest first". The last two mean breadth-first search, which runs on a queue.
  • When you write a queue in JavaScript, say why you avoid shift: "it moves every item, so I keep a head index instead". Interviewers often ask about it.
  • Test by hand on an empty input, a job that needs exactly slice, and a job that needs several turns. Check that the empty test is head === queue.length, not queue.length === 0.
  • Expect the follow-up "what about memory, if the queue runs for days?". Answer with compaction or a ring buffer, both of which free the served slots.

Where frontend code uses it

The same idea in real UI code
  • The browser's event loop takes tasks from a task queue in order, and promise callbacks wait in a separate microtask queue that is emptied after each task.
  • Breadth-first walks of the DOM or of a component tree, for example to find the nearest focusable element, use a queue.
  • Upload managers and request schedulers keep a queue of pending requests and start the next one when a slot frees up.

Related algorithms