Implement Stack Using Queue in DSA Python

Mental Model

Use a queue to act like a stack by rearranging elements so the last added is always at the front.

Analogy: Imagine a line of people where the newest person always moves to the front by asking everyone else to step back, so you can always pick the newest person first.

Queue: front -> [1] -> 2 -> 3 -> rear
Stack: top -> 3 -> 2 -> 1 -> bottom

Dry Run Walkthrough

Input: Push 1, push 2, push 3, then pop once

Goal: Simulate stack push and pop using a single queue so pop returns the last pushed element

Step 1: Push 1 into empty queue

front -> [1] -> rear

Why: First element goes directly into queue

Step 2: Push 2: enqueue 2, then rotate queue to move 2 to front

front -> [2] -> 1 -> rear

Why: Rotate so newest element is at front to simulate stack top

Step 3: Push 3: enqueue 3, then rotate queue to move 3 to front

front -> [3] -> 2 -> 1 -> rear

Why: Newest element must be at front for stack pop

Step 4: Pop: dequeue front element (3)

front -> [2] -> 1 -> rear

Why: Pop returns last pushed element, which is at front

Result:

front -> [2] -> 1 -> rear
Pop returned 3

Annotated Code

DSA Python

from collections import deque

class StackUsingQueue:
    def __init__(self):
        self.queue = deque()

    def push(self, x: int) -> None:
        self.queue.append(x)  # add new element at rear
        # rotate queue to move new element to front
        for _ in range(len(self.queue) - 1):
            self.queue.append(self.queue.popleft())  # move front to rear

    def pop(self) -> int:
        return self.queue.popleft()  # remove front element which is stack top

    def top(self) -> int:
        return self.queue[0]  # front element is stack top

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

# Driver code
stack = StackUsingQueue()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())  # should print 3
print(stack.top())  # should print 2
print(stack.empty())  # should print False

self.queue.append(x) # add new element at rear

enqueue new element at rear of queue

for _ in range(len(self.queue) - 1): self.queue.append(self.queue.popleft()) # move front to rear

rotate queue to move newly added element to front

return self.queue.popleft() # remove front element which is stack top

pop returns front element which simulates stack top

return self.queue[0] # front element is stack top

top returns front element without removing

Output

3

2

False

Complexity Analysis

Time: O(n) for push because we rotate the queue to move new element to front; O(1) for pop and top

Space: O(n) because all elements are stored in the queue

vs Alternative: Naive approach using two queues can have O(1) push but O(n) pop; this approach optimizes pop to O(1) at cost of O(n) push

Edge Cases

Pop or top on empty stack

Raises IndexError because queue is empty

DSA Python

return self.queue.popleft()  # remove front element which is stack top

Push single element then pop

Works normally, pop returns that element

DSA Python

for _ in range(len(self.queue) - 1):

Push duplicate elements

Duplicates are handled normally, order preserved as stack

DSA Python

self.queue.append(x)  # add new element at rear

When to Use This Pattern

When you need to implement a stack but only have a queue available, use queue rotation to simulate stack behavior by keeping the newest element at the front.

Common Mistakes

Mistake: Not rotating the queue after push, so pop returns oldest element instead of newest
Fix: Rotate the queue after each push by moving all elements before the new one to the back

Mistake: Using two queues unnecessarily when one queue with rotation suffices
Fix: Use a single queue and rotate it after push to keep newest element at front

Summary

Implements a stack using a single queue by rotating elements after each push.

Use when only queue data structure is available but stack behavior is needed.

The key insight is to rotate the queue so the newest element is always at the front, simulating stack top.

Practice

1. What is the main idea behind implementing a stack using a queue?

easy

A. Use a stack to implement queue operations

B. Use a queue to sort elements in ascending order

C. Use one or two queues to simulate stack operations like push and pop

D. Use two stacks to implement a queue

Solution

1. Step 1: Understand stack and queue differences

   A stack follows Last-In-First-Out (LIFO), while a queue follows First-In-First-Out (FIFO).

2. Step 2: Simulate stack using queue(s)

   By using one or two queues cleverly, we can reorder elements to behave like a stack for push and pop operations.

3. Final Answer:

   Use one or two queues to simulate stack operations like push and pop -> Option C

4. Quick Check:

   Stack via queue = simulate push/pop [OK]

Hint: Remember stack is LIFO, queue is FIFO; simulate LIFO with queue [OK]

Common Mistakes:

• Confusing stack and queue order
• Trying to sort queue instead of simulating stack
• Using stack to implement queue instead

2. Which of the following is the correct syntax to initialize an empty queue in Python using collections.deque?

easy

A. queue = deque()

B. queue = []

C. queue = Queue()

D. queue = queue()

Solution

1. Step 1: Recall Python queue initialization

   collections.deque() is the correct way to create a double-ended queue in Python.

2. Step 2: Check options

   Only queue = deque() uses deque() correctly; others are either list or undefined.

3. Final Answer:

   queue = deque() -> Option A

4. Quick Check:

   collections.deque() creates queue [OK]

Hint: Use deque() from collections for queue in Python [OK]

Common Mistakes:

• Using list [] instead of deque
• Calling undefined Queue() class
• Using lowercase queue() which is not defined

3. What will be the output of the following code implementing push and pop using one queue?

from collections import deque

class Stack:
    def __init__(self):
        self.q = deque()

    def push(self, x):
        self.q.append(x)
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())

    def pop(self):
        return self.q.popleft() if self.q else None

s = Stack()
s.push(10)
s.push(20)
s.push(30)
print(s.pop())
print(s.pop())
print(s.pop())

medium

A. 20\n30\n10

B. 10\n20\n30

C. 30\n10\n20

D. 30\n20\n10

Solution

1. Step 1: Understand push operation

   Push appends element then rotates queue so new element is at front.

2. Step 2: Trace push and pop calls

   Push 10: queue=[10]
   Push 20: queue=[20,10]
   Push 30: queue=[30,20,10]
   Pop removes front: 30, then 20, then 10.

3. Final Answer:

   30 20 10 -> Option D

4. Quick Check:

   Stack pop order = 30,20,10 [OK]

Hint: Push rotates queue to front; pop removes front [OK]

Common Mistakes:

• Ignoring rotation in push
• Assuming pop removes last element instead of front
• Confusing queue order with stack order

4. Find the error in this stack implementation using two queues:

from collections import deque

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

    def push(self, x):
        self.q1.append(x)

    def pop(self):
        while len(self.q1) > 1:
            self.q2.append(self.q1.popleft())
        return self.q1.popleft()
        self.q1, self.q2 = self.q2, self.q1

medium

A. The queues are not swapped after pop, so q1 becomes empty

B. The pop method does not remove the last element

C. The push method should append to q2 instead of q1

D. The pop method should return from q2 instead of q1

Solution

1. Step 1: Analyze pop method flow

   Pop moves all but last from q1 to q2, then pops last from q1.

2. Step 2: Identify missing swap

   After popping, q1 is empty but queues are not swapped, so next push/pop fail.

3. Final Answer:

   The queues are not swapped after pop, so q1 becomes empty -> Option A

4. Quick Check:

   Missing swap causes empty q1 [OK]

Hint: Swap queues after pop to keep q1 as main queue [OK]

Common Mistakes:

• Not swapping queues after pop
• Returning before swapping queues
• Appending to wrong queue in push

5. You want to implement a stack using a single queue with minimal operations. Which approach correctly achieves this for the push operation to maintain stack order?

hard

A. Use two queues to enqueue the new element in the empty queue

B. Append the new element, then rotate the queue by dequeuing and enqueuing all previous elements

C. Dequeue all elements, enqueue the new element, then enqueue all dequeued elements

D. Append the new element and do nothing else

Solution

1. Step 1: Understand stack order with one queue

   To simulate LIFO, after adding new element, rotate queue so new element is front.

2. Step 2: Compare approaches

   Append the new element, then rotate the queue by dequeuing and enqueuing all previous elements rotates queue after append, maintaining stack order. Append the new element and do nothing else does not reorder. Dequeue all elements, enqueue the new element, then enqueue all dequeued elements is inefficient but correct logically. Use two queues to enqueue the new element in the empty queue uses two queues, not single.

3. Final Answer:

   Append the new element, then rotate the queue by dequeuing and enqueuing all previous elements -> Option B

4. Quick Check:

   Rotate after push keeps stack order [OK]

Hint: Rotate queue after push to keep new element on top [OK]

Common Mistakes:

• Not rotating queue after push
• Using two queues when only one is allowed
• Appending without reordering elements