Cross-Structure Simulation

Description

Sometimes only one kind of structure is available - a message queue, a pair of stacks, a functional list - and you need the other kind. Simulating a stack with queues or a queue with stacks is also the clearest example of where to pay for reordering: on every write, or lazily on reads.

This skill builds both, and uses them to teach amortized analysis: counting the cost of a whole sequence of operations instead of the worst single call, and knowing when that average is good enough.

We'll go from simple to more technical:

1. The pattern: a queue from two stacks (refill only when empty) and a stack from one queue (rotate on push).
2. A second flavor: amortized cost - why each element's moves are paid for once.
3. Where the "when to pay" choice shows up (functional queues, caches, batching, GC).
4. What breaks it: early refills, pouring back, forgetting peek, amortized versus worst case.

The approach

// Queue from two stacks: pay lazily
Deque<Integer> in = new ArrayDeque<>(), out = new ArrayDeque<>();
void enqueue(int x) { in.push(x); }                          // always O(1)
int dequeue() {
    if (out.isEmpty()) {                                     // refill ONLY when out is empty
        while (!in.isEmpty()) out.push(in.pop());            // reversing restores FIFO order
    }
    return out.isEmpty() ? -1 : out.pop();
}

// Stack from one queue: pay on every push
Queue<Integer> q = new LinkedList<>();
void push(int x) {
    q.offer(x);
    for (int i = 0; i < q.size() - 1; i++) q.offer(q.poll());   // rotate x to the front
}
int pop() { return q.isEmpty() ? -1 : q.poll(); }

from collections import deque

# Queue from two stacks: pay lazily
inbox, outbox = [], []


def enqueue(x: int) -> None:
    inbox.append(x)                                           # always O(1)


def dequeue() -> int:
    if not outbox:                                            # refill ONLY when outbox is empty
        while inbox:
            outbox.append(inbox.pop())                        # reversing restores FIFO order
    return outbox.pop() if outbox else -1


# Stack from one queue: pay on every push
q = deque()                                                   # used only as a queue: append / popleft


def push(x: int) -> None:
    q.append(x)
    for _ in range(len(q) - 1):
        q.append(q.popleft())                                 # rotate x to the front


def pop() -> int:
    return q.popleft() if q else -1

Moving everything from in to out reverses it, so the oldest element ends up on top of out. The refill must wait until out is empty: refilling early puts newer elements on top of older ones. Enqueue 1 and 2, dequeue (1), enqueue 3, and a refill now would put 3 above 2 - the next dequeue would return 3 instead of 2.

A second flavor: amortized cost

A single dequeue can move n elements - O(n). But each element is pushed to in once, moved to out once and popped once, so m operations cost O(m) in total: amortized O(1) per operation. One way to see it: charge each enqueue 3 units instead of 1 and save the extra 2 on the element; when it's later moved and popped, it pays with its savings. The stack-from-queue design makes the opposite choice - O(n) on every push, never a spike on pop - which is worse overall but has no surprises.

Where you'll see it

Functional languages build immutable queues from two lists exactly this way (the "batched queue" in Okasaki's Purely Functional Data Structures), since lists are cheap stacks. The "where to pay" choice shows up across systems: write-through versus write-back caches, batching writes into periodic flushes, and garbage collectors that trade frequent small pauses for rare large ones.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. Why must the queue move elements from in to out only when out is empty?

2. What does "amortized O(1)" mean for the two-stack queue?

3. Why is the stack-from-queue's push O(n)?

Key takeaways

• Queue from two stacks: push to in, pop from out, refill out only when empty.
• Each element moves once: amortized O(1) per operation, O(n) worst case for one call.
• Stack from a queue: rotate on push - O(n) push, O(1) pop.
• Decide where to pay: every write, or lazily on reads.