practice · medium · from Queues

Queue from Two Stacks

time: O(1)
space: O(n)
tags: queues · stacks · design · amortized

in the wild Bridging a LIFO log-buffer to a FIFO consumer, or wrapping a stack-only API to expose queue semantics.

Problem

Implement a FIFO queue using only two LIFO stacks as your internal storage. The queue should support push(x), pop() (remove + return front), and peek() (return front without removing). Operations should be amortized O(1).

Examples

push 1                 →  queue [1]                  peek=1
push 2                 →  queue [1, 2]                peek=1
pop                    →  returns 1, queue [2]        peek=2
push 3                 →  queue [2, 3]                peek=2
pop                    →  returns 2, queue [3]        peek=3

Why this is the canonical "fake FIFO from LIFO" problem

If all you have is push/pop on LIFO stacks, how do you give the front element of an arriving sequence to a consumer? The trick is to maintain two stacks — one for incoming items (inbox), one for outgoing items (outbox):

push(x) → straight onto inbox.
pop / peek → if outbox is empty, drain all of inbox onto outbox (this flips the order: oldest item ends up on top of outbox). Then pop/peek from outbox.

Each item is moved between the two stacks at most twice — once into inbox, once into outbox. So even though a single pop might be O(n) (if a drain happens), it's O(1) amortized over the whole sequence.

This is the same amortization story as array doubling — rare expensive work paid off by many cheap operations.

Hints

Hint 1 — the order-flip insight

If you push a, b, c onto a single stack, popping gives you c, b, a — reverse order. What if you popped them all off and pushed them onto a second stack? Now popping the second stack gives a, b, c — the original order.

Hint 2 — lazy drain

You don't need to drain after every push. Keep pushing onto inbox. Only when a pop / peek is called and outbox is empty do you drain. New pushes accumulate on inbox until the next drain trigger.

Hint 3 — pseudocode

push(x)         → inbox.push(x)
pop / peek      → if outbox empty: while inbox not empty: outbox.push(inbox.pop())
                  return outbox.{pop, peek}()

If the outbox isn't empty when pop is called, the lazy drain hasn't been spent yet — just take from outbox.

Solution

class Queue:
    def __init__(self):
        self.inbox:  list[int] = []
        self.outbox: list[int] = []

    def push(self, x: int) -> None:
        self.inbox.append(x)

    def _drain(self) -> None:
        # Lazy: only move items when outbox is empty.
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())

    def pop(self) -> int:
        self._drain()
        return self.outbox.pop()

    def peek(self) -> int:
        self._drain()
        return self.outbox[-1]

# Tests
q = Queue()
for v in [1, 2]: q.push(v); print(f"push {v} → peek={q.peek()}")
print(f"pop → {q.pop()} (expected 1)")
q.push(3); print(f"push 3 → peek={q.peek()}")
print(f"pop → {q.pop()} (expected 2)")
print(f"pop → {q.pop()} (expected 3)")

class Queue {
  constructor() { this.inbox = []; this.outbox = []; }
  push(x) { this.inbox.push(x); }
  _drain() {
    if (this.outbox.length === 0) {
      while (this.inbox.length) this.outbox.push(this.inbox.pop());
    }
  }
  pop()  { this._drain(); return this.outbox.pop(); }
  peek() { this._drain(); return this.outbox[this.outbox.length - 1]; }
}

const q = new Queue();
for (const v of [1, 2]) { q.push(v); console.log(`push ${v} → peek=${q.peek()}`); }
console.log(`pop → ${q.pop()} (expected 1)`);
q.push(3); console.log(`push 3 → peek=${q.peek()}`);
console.log(`pop → ${q.pop()} (expected 2)`);
console.log(`pop → ${q.pop()} (expected 3)`);

pub struct Queue {
    inbox:  Vec<i32>,
    outbox: Vec<i32>,
}

impl Queue {
    pub fn new() -> Self { Self { inbox: vec![], outbox: vec![] } }

    pub fn push(&mut self, x: i32) { self.inbox.push(x); }

    fn drain(&mut self) {
        // Lazy: only move when outbox is empty.
        if self.outbox.is_empty() {
            while let Some(v) = self.inbox.pop() {
                self.outbox.push(v);
            }
        }
    }

    pub fn pop(&mut self) -> i32 {
        self.drain();
        self.outbox.pop().unwrap()
    }

    pub fn peek(&mut self) -> i32 {
        self.drain();
        *self.outbox.last().unwrap()
    }
}

fn main() {
    let mut q = Queue::new();
    for v in [1, 2] { q.push(v); println!("push {} → peek={}", v, q.peek()); }
    println!("pop → {} (expected 1)", q.pop());
    q.push(3); println!("push 3 → peek={}", q.peek());
    println!("pop → {} (expected 2)", q.pop());
    println!("pop → {} (expected 3)", q.pop());
}

#include <iostream>
#include <stack>

class Queue {
    std::stack<int> inbox_, outbox_;
    void drain() {
        // Lazy: only move when outbox is empty.
        if (outbox_.empty()) {
            while (!inbox_.empty()) { outbox_.push(inbox_.top()); inbox_.pop(); }
        }
    }
public:
    void push(int x) { inbox_.push(x); }
    int  pop()       { drain(); int v = outbox_.top(); outbox_.pop(); return v; }
    int  peek()      { drain(); return outbox_.top(); }
};

int main() {
    Queue q;
    for (int v : {1, 2}) { q.push(v); std::cout << "push " << v << " → peek=" << q.peek() << "\n"; }
    std::cout << "pop → " << q.pop() << " (expected 1)\n";
    q.push(3); std::cout << "push 3 → peek=" << q.peek() << "\n";
    std::cout << "pop → " << q.pop() << " (expected 2)\n";
    std::cout << "pop → " << q.pop() << " (expected 3)\n";
}

#include <stdio.h>

#define CAP 1024
static int  inbox [CAP], outbox[CAP];
static int  in_sp = 0,   out_sp = 0;

static void push(int x) { inbox[in_sp++] = x; }

static void drain(void) {
    // Lazy: only move when outbox is empty.
    if (out_sp == 0) {
        while (in_sp > 0) outbox[out_sp++] = inbox[--in_sp];
    }
}

static int pop_(void)  { drain(); return outbox[--out_sp]; }
static int peek(void)  { drain(); return outbox[out_sp - 1]; }

int main(void) {
    int ops[] = {1, 2};
    for (int i = 0; i < 2; i++) { push(ops[i]); printf("push %d → peek=%d\n", ops[i], peek()); }
    printf("pop → %d (expected 1)\n", pop_());
    push(3); printf("push 3 → peek=%d\n", peek());
    printf("pop → %d (expected 2)\n", pop_());
    printf("pop → %d (expected 3)\n", pop_());
    return 0;
}

idle

The lazy-drain pattern is the win. A naïve implementation that drains on every push gives O(n) push — much worse. The two-stack trick amortizes the cost: each item is moved exactly twice (into inbox, into outbox) across its lifetime, so the per-operation cost averages out to O(1).

Complexity

Time (amortized): O(1) for push, pop, peek. Worst-case one pop can be O(n) (when the drain happens), but it's paid for by O(n) prior O(1) pushes.
Space: O(n) — at most all n items live on one or the other stack.
vs single-stack approach: If you tried to fake a queue with a single stack, every pop would scan-and-rebuild, costing O(n) per call — total O(n²) for n pops.

In the wild

Job-queue-on-top-of-LIFO-storage. Some embedded systems give you only LIFO primitives in firmware; you build a FIFO on top.
Persistent functional queues. Okasaki's classic two-list (cons-list) queue is exactly this — every step builds a new immutable queue. The amortization argument is the same.
Streaming reversal buffers. Push items onto inbox, drain in a batch when downstream is ready. The outbox is essentially a buffered window with FIFO output.

Variations

Stack from two queues. Symmetric: every push rotates the queue so the new element becomes the front. Cleaner code but O(n) push, O(1) pop.
Real-time (not just amortized) queue. Use three stacks — one inbox, one outbox, one "in-flight transfer". Worst-case O(1) per op. Significantly fiddlier.
Persistent queue. Same two-stack idea, but each operation returns a new queue without mutating the old. Used by functional languages (Haskell, Clojure).