Queue Using Two Stacks

Implement FIFO with two LIFO stacks by pouring when the output side is empty—classic amortized interview pattern.

Try this in Python

class QueueTwoStacks:
    def __init__(self) -> None:
        self.a: list[int] = []
        self.b: list[int] = []

    def enqueue(self, x: int) -> None:
        self.a.append(x)

    def dequeue(self) -> int:
        if not self.b:
            while self.a:
                self.b.append(self.a.pop())
        return self.b.pop()


q = QueueTwoStacks()
q.enqueue(1)
q.enqueue(2)
print(q.dequeue(), q.dequeue())

Key takeaways

• Each element moves at most twice between stacks overall.
• Keeps enqueue and dequeue amortized O(1).
• Understand why occasional slow dequeue is OK.