Queue From Two Stacks

The Idea

Keep an inbox stack for arrivals and an outbox stack for departures. When the outbox runs dry, pour the whole inbox into it — the order flips, so the oldest item now sits on top. Every item moves at most twice, which makes dequeue O(1) amortized.

Real-World Example

Deal a face-down deck card by card into a fresh pile and it comes out reversed: the bottom card ends up on top. Deal that pile once more and the deck is back exactly as it started. Two flips cancel out.

The Code

class Queue:
    def __init__(self):
        self.inbox, self.outbox = [], []
    def enqueue(self, x):
        self.inbox.append(x)              # always cheap
    def dequeue(self):
        if not self.outbox:               # refill only when empty
            while self.inbox:             # pour: the order flips
                self.outbox.append(self.inbox.pop())
        return self.outbox.pop()          # oldest sits on top

q = Queue()
for x in [1, 2, 3]:
    q.enqueue(x)
print(q.dequeue(), q.dequeue())           # 1 2

inbox = [1, 2, 3]
outbox = []
while inbox:
  outbox.append(inbox.pop())
print(outbox)