232. Implement Queue using Stacks

Problem¶

Implement MyQueue with two stacks, supporting FIFO push, pop, peek, and empty. Use only stack operations; pop and peek are called only when nonempty. Aim for amortized \(O(1)\) per operation.

Operation    Return    Queue (front → back)
MyQueue()    None      []
push(1)      None      [1]
push(2)      None      [1, 2]
peek()       1         [1, 2]
pop()        1         [2]
empty()      False     [2]

class MyQueue:
    def __init__(self):
        pass

    def push(self, x: int) -> None:
        pass

    def pop(self) -> int:
        pass

    def peek(self) -> int:
        pass

    def empty(self) -> bool:
        pass

Key trick¶

Push onto an input stack; transfer everything to an output stack only when the output stack is empty, reversing the order so the oldest element is on top.

Trap¶

Transferring while the output stack still contains elements breaks FIFO order; using pop(0) violates the stack-only restriction.

Why is it interesting?¶

An occasional expensive reversal still gives amortized \(O(1)\) operations because each element transfers between stacks at most once.

Python solution¶

class MyQueue:
    def __init__(self):
        self.stack_push = []
        self.stack_pop = []

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

    def _transfer(self) -> None:
        # Existing output elements must stay ahead of newer input elements.
        if not self.stack_pop:
            while self.stack_push:
                self.stack_pop.append(self.stack_push.pop())

    def pop(self) -> int:
        self._transfer()
        return self.stack_pop.pop()

    def peek(self) -> int:
        self._transfer()
        return self.stack_pop[-1]

    def empty(self) -> bool:
        return not (self.stack_push or self.stack_pop)

Time: Amortized \(O(1)\) per operation; pop and peek can take \(O(n)\) for a transfer. A sequence of \(k\) operations takes \(O(k)\) overall.

Space: \(O(n)\) for \(n\) queued elements.

Comment on my solution¶

Your solution is correct and already achieves optimal amortized time. Moving the empty-output check into the transfer helper removes duplication and makes the FIFO invariant harder to violate.

# WORKS
class MyQueue:
    def __init__(self):
        self.stack_push = []
        self.stack_pop = []

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

    def _reverse_stack(self):
        while self.stack_push:
            self.stack_pop.append(self.stack_push.pop())

    def pop(self) -> int:
        if self.stack_pop:
            return self.stack_pop.pop()
        self._reverse_stack()
        return self.stack_pop.pop()

    def peek(self) -> int:
        if self.stack_pop:
            return self.stack_pop[-1]
        self._reverse_stack()
        return self.stack_pop[-1]

    def empty(self) -> bool:
        return not (self.stack_pop or self.stack_push)