HardDSAAsked in 20245 min read

Queue via two stacks

Q: Queue via two stacks

**Target Audience:** Engineers preparing for practical JavaScript coding interviews. **Difficulty:** Hard > **How to read this doc:** the two-stack queue was checked against a plain array queue on 2,000 random operation sequences (0 mismatches), and the amortized claim was counted, not asserted: over 200,000 enqueues and dequeues the total number of element moves was exactly 200,000. A practical surprise was measured too: draining an array with `shift()` had a performance cliff on this Node (5.3 ms for 10,000 items, 841 ms for 20,000), while the two-stack queue stayed under 3 ms. ## 1. The problem, restated A stack removes the most recently added item; a queue removes the oldest. Reversing a sequence turns one into the other, and popping items off one stack and pushing them onto another reverses their order. So keep an INBOX stack for new items and an OUTBOX stack for items ready to be dequeued. ## 2. Clarifying questions a strong candidate asks | Question | Why it matters | | :--

2.8k views

133 of 154

The problem

Problem, as an interviewer would state it: "Implement a FIFO queue using only two stacks (LIFO structures). Discuss edge cases, runtime, and alternatives."

Examples:

Code

q.enqueue(1); q.enqueue(2); q.enqueue(3);
q.dequeue(); // 1
q.dequeue(); // 2
q.enqueue(4);
q.dequeue(); // 3

Clarifying questions expected:

Which operations are needed: enqueue, dequeue, peek, size, isEmpty?
What should dequeue and peek return on an empty queue?
What runtime is expected: is amortized O(1) per operation acceptable?

Code / implementation expected: Yes — real, direct proof against a reference queue, a measurement of the amortized cost, and the classic bug.

js-coding
utility
algorithm

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Engineers preparing for practical JavaScript coding interviews. Difficulty: Hard

How to read this doc: the two-stack queue was checked against a plain array queue on 2,000 random operation sequences (0 mismatches), and the amortized claim was counted, not asserted: over 200,000 enqueues and dequeues the total number of element moves was exactly 200,000. A practical surprise was measured too: draining an array with shift() had a performance cliff on this Node (5.3 ms for 10,000 items, 841 ms for 20,000), while the two-stack queue stayed under 3 ms.

1. The problem, restated

A stack removes the most recently added item; a queue removes the oldest. Reversing a sequence turns one into the other, and popping items off one stack and pushing them onto another reverses their order. So keep an INBOX stack for new items and an OUTBOX stack for items ready to b

The solution is hidden so you can try first

5 min read · 9 sections

Run the code

Edit the code and run it here. Each console line with an expected value becomes a test.

JavaScriptReal, direct proof: a two-stack queue matches an array queue on random operations, moves each element at most once, and avoids the shift() slowdown on large queues

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

No comments yet. Share how you would answer it.

Question 133 of 154 in JavaScript coding

Keep your momentum going.

Mark this question solved to track your progress, then take the next one while it is fresh.

All JavaScript coding questions

Up nextHard→

Virtual DOM diff algorithm

Continue