💬 Discord
Sign In
NeetCode #347LC-232EasyStackNC 250
← Back to All Problems

#347 · #232 · Implement Queue using Stacks(用栈实现队列)

📌 Problem Statement & Constraints

Implement a first-in-first-out queue using only two stacks, supporting push, pop, peek and empty. Constraints: 1 <= x <= 9; at most 100 calls.

💡 Core Algorithmic Approaches

  1. Use an input stack and an output stack. push always goes to the input stack.
  2. When a pop or peek is needed, transfer everything from the input stack to the output stack if the output stack is empty.
  3. The transfer reverses the order, so the oldest element ends up on top of the output stack.
  4. Each element is moved at most twice, giving O(1) amortised cost per operation.

💻 Benchmark Python3 Implementation

class MyQueue:
    def __init__(self):
        self.in_st = []
        self.out_st = []

    def _transfer(self) -> None:
        if not self.out_st:                # only transfer when needed
            while self.in_st:
                self.out_st.append(self.in_st.pop())

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

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

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

    def empty(self) -> bool:
        return not self.in_st and not self.out_st

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(1) amortised per operation: each element is pushed once, transferred once, and popped once.
💾 Space Complexity
O(n) for the two stacks.

⚠️ Interview Pitfalls & Follow-ups

  • Transferring on every operation: the amortised O(1) argument relies on the output stack being non-empty.
  • Checking empty on only one stack: both must be empty.
  • Reversing the transfer direction: elements must move from the input stack to the output stack, which reverses their order so the oldest is on top.
  • Confusing this with the two-queue stack: the two problems use opposite rotation strategies.