Stacks and queues

Choose by which entry must come back next; then make taking it move nothing.

Before you read: predict

ExamHall's essay editor keeps a candidate's autosaves while the connection is down, in a queue built from two arrays used as stacks, and sends them one at a time once it is back:

What is moves at the end?

const inbox = [];const outbox = [];let moves = 0;function enqueue(draft) {  inbox.push(draft);}function dequeue() {  if (outbox.length === 0) {    while (inbox.length > 0) {      outbox.push(inbox.pop());      moves++;    }  }  return outbox.pop();}for (let n = 1; n <= 5; n++) enqueue('draft ' + n);dequeue();dequeue();for (let n = 6; n <= 8; n++) enqueue('draft ' + n);for (let k = 0; k < 4; k++) dequeue();enqueue('draft 9');export { moves };

The 30-second version

A stack hands back the newest entry, so it fits nesting and undo. A queue hands back the oldest, so it fits order. In JavaScript, push and pop make a stack. For a queue, don't shift() a long array: read from a head index, go round a ring, or pour one stack into another.

Choose by which entry must come back next; then make taking it move nothing.

How it works

Step 1 of 13

A stack returns the newest entry; a queue returns the oldest. push and pop at an array's end make a stack.

In the kitchen

the logs stacked last on the pile are the first you lift off → a stack (step 1)
the drying rack takes logs in at one end and gives them out at the other, oldest first → a queue (step 1)

Analogy: A cabin's woodshed through a long winter (home heating)

In the woodshed	In the code
the logs stacked last on the pile are the first you lift off	a stack (step 1)
the drying rack takes logs in at one end and gives them out at the other, oldest first	a queue (step 1)
at the rack you take the log at a marker and move the marker one log along; no log slides	a head index (step 6)
new logs go on pile A; once pile B is used up, you restack all of A onto B, and the oldest lands on top	two stacks make a queue (step 11)

In real terms: a structure is a rule for which entry comes out next; a fast queue changes a number instead of moving entries.

Breaks down when: a log can be pulled from the middle of a pile, while a stack shows only its top; and logs dry while they wait, while queued entries never change.

Contrasting case: one armful brought in each evening and burnt the same night. Nothing waits, so the order never matters.

Examples, run for real

4.1 ExamHall EXH-4910: an autosave buffer flushed newest first

ExamHall's essay editor kept a candidate's autosaves in a buffer while she was offline and sent them on reconnect. The server keeps the last draft it receives. The flush was while (buffer.length) send(buffer.pop()) (EXH-4910):

4.1 EXH-4910 three offline saves flushed with pop(): sent draft 3, draft 2, draft 1 · the server keeps draft 1
4.1 MR !5210 the same saves read from a head index: sent draft 1, draft 2, draft 3 · the server keeps draft 3 · 0 elements moved

pop() takes the newest entry first (step 1), so the oldest draft arrived last and won. MR !5210 reads the buffer from a head index instead (step 6): oldest first, and the newest draft kept.

4.2 Chat: a message's brackets

Before sending a code snippet, a chat composer checks its brackets with a stack (step 3):

4.2 f(a[i]) · stack after each bracket: ( · ([ · ( · empty · balanced
4.2 f(a[i] · stack after each bracket: ( · ([ · ( · not balanced: ( still open at the end

Each opener goes on the stack and each closer takes the top off. In the second message the ( is never closed, so the stack is not empty at the end.

Try it

Answer first, then check. Nothing is saved.

Question 1 of 8

A video player keeps the newest downloaded segments in a ring that never grows. The ring is an object with three fields, slots, head and size. When the ring is full, push writes the new segment over the oldest and returns the one it dropped; otherwise it returns undefined. push is complete apart from four lines:

In what order do the four lines run, top first?

export function push(q, segment) {  /* the four lines, in order */}

Your order

1empty
2empty
3empty
4empty

Tap the lines in the order you expect.

Question 2 of 8

A ledger checks that each fee formula's brackets are balanced before saving it, such as max(fee[0], (amount * rate)). The check is complete apart from one line:

The team's list has 8 tests: an empty text, pairs side by side and nested, crossing pairs, a closer of the wrong kind, a closer with nothing open, an opener left open, and 200 random strings.

Which check passes all 8?

export function isBalanced(text) {  const opens = { ')': '(', ']': '[', '}': '{' };  const stack = [];  for (const ch of text) {    if (ch === '(' || ch === '[' || ch === '{') stack.push(ch);    else if (ch in opens) {      /* the check */    }  }  return stack.length === 0;}

Question 3 of 8

A box office's waiting list uses a head index and compacts the array once more than half of it has been served:

What is copied at the end?

let line = [];let head = 0;let copied = 0;function join(fan) {  line.push(fan);}function serve() {  const fan = line[head];  head++;  if (head * 2 > line.length) {    const rest = [];    for (let i = head; i < line.length; i++) {      rest.push(line[i]);      copied++;    }    line = rest;    head = 0;  }  return fan;}for (let n = 0; n < 12; n++) join('fan ' + n);for (let round = 0; round < 3; round++) {  for (let k = 0; k < 4; k++) serve();  join('late ' + round + 'a');  join('late ' + round + 'b');}export { copied };

Question 4 of 8

A chat composer keeps its edits for undo in a ring that overwrites its oldest edit when full:

What does the fourth undo() return?

const CAP = 5;const ring = new Array(CAP);let start = 0;let count = 0;function record(edit) {  if (count === CAP) {    ring[start] = edit;    start = (start + 1) % CAP;  } else {    ring[(start + count) % CAP] = edit;    count++;  }}function undo() {  if (count === 0) return null;  count--;  const i = (start + count) % CAP;  const edit = ring[i];  ring[i] = undefined;  return edit;}for (let n = 1; n <= 8; n++) record('edit ' + n);undo();undo();undo();export const fourth = undo();

Question 5 of 8

the interviewer says: "ExamHall's editor must hold any number of autosaves while offline and send them oldest first. Write class DraftQueue with enqueue(item), dequeue() and peek() (both return undefined when empty) and a size property, where new DraftQueue(capacity) starts with room for capacity entries and grows when it must. Dequeue must not slow down as the queue gets longer. Keep the state in ordinary fields, not #private ones." You have 15 minutes and a plain editor.

Before you type: say your test list out loud.

Name at least six tests, each with its input and what it expects.

Your answer (optional, stays on this page)

Question 6 of 8

Now write it, in 15 minutes, from a blank file that exports DraftQueue.

Your answer (optional, stays on this page)

Question 7 of 8

A subtitle editor flags the first tag error in a caption:

What is flagged?

export function firstError(text) {  const open = [];  for (const tag of text.matchAll(/<(\/?)(\w+)>/g)) {    if (tag[1] === '') open.push(tag[2]);    else if (open.pop() !== tag[2]) return tag[0];  }  return open.length > 0 ? '<' + open[open.length - 1] + '>' : null;}export const flagged = firstError('<i>He <b>said <i>no</i> twice</b>, <u>so <b>stop</b> now');

Question 8 of 8

A payments service queues each payer's failed payment for retry, with a head index:

What is retries[0] at the end?

const retries = [];let head = 0;function add(payer) {  retries.push(payer);}function take() {  const payer = retries[head];  head++;  if (head === retries.length) {    retries.length = 0;    head = 0;  }  return payer;}add('amy'); add('ben'); add('cal');take(); take();add('dee'); add('eve');take(); take(); take();add('fay'); add('gus'); add('hal');take();export { retries };

Go deeper

Pro tips

For a queue in JavaScript, keep a head index instead of shift(). When: a queue can grow past a few hundred entries, as in a breadth-first search (step 5). shift() moves every remaining element on each call. Verify (RAN, tips.mjs): (The curriculum row's tip, [SELF].)
```
tip 1 a breadth-first walk over a hub and 2,000 accounts: queue drained with shift() 2,003,001 element writes · with a head index 2,000
```
Say the corner cases out loud: an empty queue, one entry, two entries. When: before running your queue in an interview. Verify (RAN, tips.mjs):
```
tip 2 DraftQueue dequeued until empty and once more: empty: undefined · one entry: a, undefined · two entries: a, b, undefined
```

Source

Vendor pages change, so their claims are labelled as of 2026-10-17; every count this lesson grades is executed on Node 24. The curriculum row's first source, Cormen et al., is a book and keys nothing.

MDN, Array.prototype.shift() (the curriculum row's second source), https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/shift (mdn-array-shift.txt). As of 2026-10-17.
- "The shift() method shifts all values to the left by 1 and decrements the length by 1, resulting in the first element being removed." (step 5, cited from the prerequisite's lane)
MDN, Array.prototype.pop(), https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/pop (mdn-array-pop.txt). As of 2026-10-17.
- "The pop() method removes the last element from an array and returns that value to the caller. If you call pop() on an empty array, it returns undefined." (steps 1, 4)
Tech Interview Handbook, Stack cheatsheet, https://www.techinterviewhandbook.org/algorithms/stack/ (tih-stack.txt). As of 2026-10-17.
- "This behavior is commonly called LIFO (last in, first out)." (step 1)
- "Stacks are an important way of supporting nested or recursive function calls and is used to implement depth-first search." (step 2)
- Its essential questions: "Valid Parentheses" (steps 3–4), "Implement Queue using Stacks" (steps 11–12).
Tech Interview Handbook, Queue cheatsheet, https://www.techinterviewhandbook.org/algorithms/queue/ (tih-queue.txt). As of 2026-10-17.
- "This behavior is commonly called FIFO (first in, first out)." (step 1)
- "However, note that the dequeue operation (assuming the front of the queue is on the left) in such a scenario will be O(n) because it requires shifting of all other elements left by one." (step 5)
- Its recommended practice question "Design Circular Queue" (steps 9–10) and its corner cases (tip 2): "Empty queue", "Queue with one item", "Queue with two items".

Checked against the tools and docs as of 2026-10-17.

Predict first