cf.completefrontend
STACKS & QUEUES · CORE

Queue from two stacks

Build a first-in-first-out queue from two last-in-first-out stacks by pouring one into the other only when needed.

Time O(1) amortized per operationSpace O(n)3 practice problemsStep-through picture

The idea

A stack gives back the newest item, and a queue gives back the oldest. If you pour a stack into a second stack, one item at a time, the order flips: the oldest item ends up on top. Two stacks can therefore act as a queue.

New items always go onto the inbox stack. Items are always taken from the outbox stack. Only when the outbox is empty do you pour everything from inbox into it, which puts the oldest item on top.

A single pour can move many items, but each item is poured at most once in its life. Spread over all operations, each one costs O(1) on average. This kind of "on average over many operations" cost is called amortized cost.

An everyday example

Two trays of cookies

A baker puts each finished cookie on top of a tray. A server can only take cookies from the top of a serving tray. When the serving tray is empty, the baker flips the whole baking tray's pile onto it one cookie at a time, so the cookie baked first is now on top. Customers always get the oldest cookie first.

How the example maps to the code
In the exampleIn the code
The baking traythis.inbox
The serving traythis.outbox
Putting a new cookie on the baking traythis.inbox.push(value)
Flipping the pile when the serving tray is emptythis.outbox.push(this.inbox.pop())
Serving the top cookiethis.outbox.pop()

From the slow way to queue from two stacks

  1. Suppose you may only use stacks, and you need a queue. The obvious way: keep everything in one stack. To dequeue, pour every item into a second stack, which flips the order and puts the oldest item on top, pop it, then pour everything back. Each dequeue moves every item twice, so it costs O(n).
  2. Look at the pour back. After the first pour, the second stack already holds the items in exactly the order they must leave: oldest on top, then the next oldest. Pouring them back only to pour them again on the next dequeue is wasted work. Leave them where they are, and call that stack outbox.
  3. New items still need a place, and they are newer than everything in outbox. So they go onto a separate stack, inbox. As long as outbox has items, its top is the oldest item in the whole queue. Only when outbox is empty do you pour inbox into it, which again puts the oldest waiting item on top.
  4. Each item is pushed onto inbox once, poured once, and popped from outbox once: three moves in its whole life, however the calls are mixed. That pair of stacks is a queue from two stacks.

How it works

  1. Keep two arrays used as stacks: inbox and outbox.
  2. enqueue(value) pushes onto inbox.
  3. dequeue() first checks whether outbox is empty.
  4. If it is, pop every item from inbox and push it onto outbox. The oldest item ends on top.
  5. Pop and return the top of outbox.
  6. The size is the two lengths added together.

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. class TwoStackQueue {
  2. constructor() {
  3. this.inbox = [];
  4. this.outbox = [];
  5. }
  7. enqueue(value) {
  8. this.inbox.push(value);
  9. }
  11. dequeue() {
  12. if (this.outbox.length === 0) {
  13. while (this.inbox.length > 0) {
  14. this.outbox.push(this.inbox.pop());
  15. }
  16. }
  17. return this.outbox.pop();
  18. }
  20. get size() {
  21. return this.inbox.length + this.outbox.length;
  22. }
  23. }

How fast it is

TimeO(1) amortized per operation
Extra memoryO(n)

Each item is pushed, poured, and popped once, so n operations take O(n) work in total. A single dequeue may pour many items at once.

  • Best caseO(1)

    Any enqueue, and any dequeue while outbox still has items, like the second and third dequeues in the trace.

  • Average caseO(1)

    Any long sequence of calls: each item is moved at most three times, so the cost per call is constant when spread over the sequence (amortized).

  • Worst caseO(n)

    A single dequeue right after n enqueues, with outbox empty. It pours all n items before popping one.

Common mistakes

  • Pouring on every dequeue, back and forth, which makes each operation O(n).
  • Pouring while outbox still has items, which mixes new items on top of older ones.
  • Forgetting inbox when computing the size or checking whether the queue is empty.

When to use it

Look for these clues in a problem:

  • The task asks you to build a queue using only stack operations.
  • Items arrive at one end and leave at the other, and you want cheap operations on average.
  • You work with immutable lists, where only the front is cheap to add to and remove from.
  • A queue must also report a running max or min: two min-stacks give a queue with a min.

Check yourself

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

Why must you never pour while outbox still has items?

The poured items are newer than everything in outbox, but they would land on top of it. The next dequeue would return a newer item before an older one.

How many times is each item moved over its whole life?

At most three: pushed onto inbox, poured onto outbox, and popped from outbox. That bound is why the average cost is O(1).

After enqueue(1), enqueue(2), dequeue(), enqueue(3), what do the two stacks hold?

inbox holds [3] and outbox holds [2]. The dequeue poured 1 and 2, so outbox became [2, 1], and popping returned 1.

What is the slowest single dequeue, and when does it happen?

O(n), when outbox is empty and inbox holds n items, all of which are poured before the pop.

Practice problems

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

Not started

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

Start practicing

easy

medium

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 class keeps one rule: reading outbox from top to bottom and then inbox from bottom to top gives every waiting item, oldest first. At the start both are empty, so the rule holds.

enqueue pushes onto the top of inbox, which is the end of that reading order, the place for the newest item. A dequeue with items in outbox pops its top, the first item in the reading order, which is the oldest. A dequeue with an empty outbox pours inbox item by item. Pouring flips the order, so the bottom of inbox, the oldest item, ends on top of outbox, and the reading order is unchanged.

The cost works out because no item ever goes back. Each item makes at most three moves: one push onto inbox, one pour, and one pop from outbox. So any sequence of m calls does at most about 3m pushes and pops in total, which is O(1) per call on average, even though one call may pour many items. This kind of averaging over a sequence of calls is called amortized cost.

Going deeper

3 more ideas

Why the order comes out right

inbox has the newest item on top. Pouring it reverses the order, so outbox has the oldest item on top, followed by the next oldest. New items that arrive meanwhile go to inbox and are all newer than everything in outbox. So as long as outbox isn't empty, its top is the oldest item in the whole queue. We only pour again when outbox runs out.

Why it is O(1) on average

One dequeue can pour n items, which is O(n). But each item is pushed onto inbox once, poured once, and popped from outbox once: three moves in its whole life. So n operations cost O(n) in total, O(1) each on average. Only the occasional pour is slow.

Peeking

To peek without removing, do the same pour check and return this.outbox[this.outbox.length - 1] instead of popping. Never pour while outbox still has items: the new items would land on top of older ones and break the order.

Work it by hand

Every step in a table, with why

Enqueue three letters, take one out, add another, then empty the queue and try one more dequeue.

enqueue("p"), enqueue("q"), enqueue("r"), dequeue(), enqueue("s"), dequeue(), dequeue(), dequeue(), dequeue()

StepCallPouredReturnsinbox (bottom to top)outbox (bottom to top)Why
1enqueue("p")--pemptyNew items always go onto inbox.
2enqueue("q")--p, qemptyq sits on top of p, so inbox alone would give the newest item first.
3enqueue("r")--p, q, remptyThree items wait, all in inbox.
4dequeue()3 items"p"emptyr, qoutbox is empty, so all three are poured. The order flips, p lands on top, and the pop returns it.
5enqueue("s")--sr, qs goes to inbox. It must not be poured now, or it would land on top of the older q and r.
6dequeue()0"q"sroutbox still has items, so no pour: its top, q, is the oldest item.
7dequeue()0"r"semptyAgain straight from outbox.
8dequeue()1 item"s"emptyemptyoutbox is empty, so s is poured over and popped.
9dequeue()0undefinedemptyemptyBoth stacks are empty. The pour loop doesn't run and [].pop() returns undefined.

The items left in the order p, q, r, s, the order they arrived. Only 2 of the 5 dequeues poured anything, and the 4 items were poured 4 times in total, once each.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Queue from two stacksO(1)O(n)Only stack operations are available, or you work with immutable lists. Constant time on average, with occasional slow pours.
Array with shiftO(n)O(n)Tiny queues only. Every dequeue moves all the remaining items.
Array with a head indexO(1)O(n)Plain JavaScript where you need steady O(1) every call, not just on average.
Ring bufferO(1)O(capacity)You know the most items that can wait at once and want memory that never grows.

Extra memory: O(n): every waiting item is in exactly one of the two arrays.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Queue from two stacks and the other approaches, on a scale where each line up is 10 times more steps.
  • Queue from two stacks, Array with a head index, Ring buffer O(1)
  • Array with shift O(n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Queue from two stacks111
Array with shift101,0001 million
Array with a head index111
Ring buffer111

Inputs that need care

5 tricky inputs
dequeue() on an empty queue
The pour loop doesn't run and outbox.pop() returns undefined. Throw or return null if callers need a clear signal.
Enqueue and dequeue taking turns
Each dequeue finds outbox empty and pours exactly one item. Every call is O(1), just with an extra move.
n enqueues followed by n dequeues
The first dequeue pours all n items, and the other n - 1 pop straight from outbox. The total is still about 3n moves.
Peeking at the front
Do the same pour-if-empty check, then read outbox[outbox.length - 1] without popping.
Checking size or emptiness
Add both lengths: inbox.length + outbox.length. Looking at only outbox reports an empty queue while items wait in inbox.

Variations and follow-ups

Twists interviewers add

Queue with a maximum or minimum

Make both stacks min stacks (or max stacks). The queue's minimum is the smaller of the two stacks' minimums, so all operations stay O(1) amortized. This gives a sliding-window minimum without a deque.

Immutable queue

Functional languages build queues from two immutable lists: a front list to read from and a back list, kept in reverse, to add to. When the front list is empty, the back list is reversed into it. It is the same pour-when-empty idea.

Stack from two queues

The reverse problem is less friendly. To pop the newest item, move all but one item from one queue to the other, so either push or pop costs O(n) every time. There is no amortized trick, because moving items between queues doesn't flip their order.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "implement a queue using stacks" or "using only push and pop". It also hides in "a queue that supports getMin", which is two min stacks.
  • Explain the one rule that makes it fast: "only pour when outbox is empty". Then explain why pouring early would break the order: newer items would land on top of older ones.
  • Give the amortized argument in one sentence: "each item is pushed, poured, and popped once, so m calls cost O(m) in total". Interviewers almost always ask why it isn't O(n) per call.
  • Test by hand: enqueue, dequeue, enqueue, then dequeue twice. This catches pouring while outbox still has items.
  • Expect the follow-up "is the worst case still O(1)?". No: one dequeue can pour n items. If every call must be fast, as in an animation frame, use a head-index array or a ring buffer instead.

Where frontend code uses it

The same idea in real UI code
  • Functional and immutable data libraries build queues from two immutable lists, a front list and a reversed back list, using the same pour-when-empty idea, because adding to the front of an immutable list is cheap.
  • It is a classic way to explain amortized cost, which also explains why array.push is O(1) on average even though the array sometimes has to grow and copy.
  • A queue that must report its maximum, such as the slowest request in the current batch, can be built from two max-stacks this way.

Related algorithms