💬 Discord
Sign In
NeetCode #346LC-225EasyStackNC 250
← Back to All Problems

#346 · #225 · Implement Stack using Queues(用队列实现栈)

📌 Problem Statement & Constraints

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

💡 Core Algorithmic Approaches

  1. The trick is to make push rotate the queue so the newest element is always at the front.
  2. Push the new element at the back, then rotate the other size - 1 elements from the front to the back.
  3. After the rotation, pop and top are simply front operations, both O(1).
  4. A single queue suffices -- the second queue is unnecessary for this rotation trick.

💻 Benchmark Python3 Implementation

class MyStack:
    def __init__(self):
        from collections import deque
        self.q = deque()

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

    def pop(self) -> int:
        return self.q.popleft()            # front is the newest

    def top(self) -> int:
        return self.q[0]

    def empty(self) -> bool:
        return not self.q

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n) for push (the rotation) and O(1) for everything else. An alternative makes push O(1) and pop O(n).
💾 Space Complexity
O(n) for the queue.

⚠️ Interview Pitfalls & Follow-ups

  • Rotating len(self.q) times instead of len(self.q) - 1: the newest element would move back to the rear, defeating the purpose.
  • Using two queues: unnecessary; the rotation trick needs only one.
  • Making pop O(n) instead of push: both are valid designs, but be clear about which operation carries the cost.
  • Using q[-1] for top: after the rotation the newest element is at index 0, not -1.