#225

Easy

auto_awesomeStack-based state management

LeetCode Problem Workspace

Implement Stack using Queues

This problem tests your ability to simulate a LIFO stack using two queues while preserving all standard stack operations correctly.

stack design queue

Problem Statement

Design a class MyStack that simulates a last-in-first-out (LIFO) stack using only standard queue operations. Your implementation should support push, pop, top, and empty functions while adhering strictly to queue constraints.

Implement the following methods: push(x) to add an element to the top, pop() to remove the top element, top() to retrieve the top element without removing it, and empty() to check whether the stack has no elements. All operations must operate through queues, and multiple method calls must maintain correct LIFO ordering.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

Input ["MyStack", "push", "push", "top", "pop", "empty"] [[], [1], [2], [], [], []] Output [null, null, null, 2, 2, false]

Explanation MyStack myStack = new MyStack(); myStack.push(1); myStack.push(2); myStack.top(); // return 2 myStack.pop(); // return 2 myStack.empty(); // return False

Constraints

1 <= x <= 9
At most 100 calls will be made to push, pop, top, and empty.
All the calls to pop and top are valid.

Solution Approach

Two-Queue Approach

Use two queues, one as the main stack storage and the other as a temporary holder. On push, enqueue the new element into the empty queue and then move all elements from the main queue to this queue, swapping references afterward. Pop and top operations then directly operate on the primary queue, ensuring LIFO order.

Single-Queue Rotation

Maintain one queue and push new elements to the back. After each push, rotate the queue by dequeuing all previous elements and enqueuing them at the back, effectively moving the new element to the front. This guarantees that the front of the queue always represents the stack top, allowing pop and top in O(1) time.

Tracking Top Optimization

Keep a separate variable to track the top element when performing push operations. This avoids rotating the entire queue just to access the top. When popping, update the top variable by checking the next front element or using auxiliary storage, reducing unnecessary queue manipulations and improving efficiency.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time and space complexity depend on the chosen approach: the two-queue method results in O(n) push and O(1) pop/top, whereas the single-queue rotation method has O(n) push with O(1) pop/top. Space is O(n) in both cases for queue storage.

What Interviewers Usually Probe

Ask candidates to implement a stack with strict queue-only operations to test understanding of LIFO vs FIFO behavior.
Check if the candidate optimizes push or pop; performance trade-offs reveal problem-solving depth.
Listen for discussion about top element tracking or queue rotation as a method to preserve stack order.

Common Pitfalls or Variants

Common pitfalls

Attempting to access the last element directly without rotation or auxiliary storage violates queue-only rules.
Confusing push and pop time complexity and not accounting for O(n) rotations in single-queue approaches.
Neglecting to update the top variable when popping can lead to incorrect top() results.

Follow-up variants

Implement a stack using only a single queue without auxiliary variables.
Optimize for frequent top() calls while minimizing rotations on push().
Design a double-ended stack using two queues to allow both front and back LIFO operations.

FAQ

What is the easiest method to implement a stack using queues?

The simplest method is the two-queue approach, where you maintain the new element in an empty queue and transfer all previous elements to it, preserving LIFO order.

Can I implement this stack using only one queue?

Yes, using single-queue rotation: enqueue the new element and rotate all existing elements behind it so the front always represents the top.

How do I efficiently retrieve the top element without rotating the queue every time?

Track the top element with a separate variable updated on push and pop operations, which avoids unnecessary rotations.

What is the time complexity for push and pop operations in this problem?

For the two-queue approach, push is O(n) and pop/top is O(1). For the single-queue rotation, push is O(n) and pop/top is O(1). Space is O(n) in both methods.

Are there common mistakes when implementing stack using queues?

Yes, common mistakes include trying to access the last element directly, ignoring top updates, and miscalculating push or pop complexity.

terminal

Solution

Solution 1: Two Queues

We use two queues $q_1$ and $q_2$, where $q_1$ is used to store the elements in the stack, and $q_2$ is used to assist in implementing the stack operations.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

class MyStack:
    def __init__(self):
        self.q1 = deque()
        self.q2 = deque()

    def push(self, x: int) -> None:
        self.q2.append(x)
        while self.q1:
            self.q2.append(self.q1.popleft())
        self.q1, self.q2 = self.q2, self.q1

    def pop(self) -> int:
        return self.q1.popleft()

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

    def empty(self) -> bool:
        return len(self.q1) == 0


# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()

Continue Practicing

#232 implement queue using stacks #341 flatten nested list iterator #173 binary search tree iterator