Implement Stack Using Queue in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Push and Pop Operations on Stack Implemented Using One Queue

What is the output of the following code that uses one queue to implement a stack?

DSA Python

from collections import deque

class StackUsingQueue:
    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):
        if self.q:
            return self.q.popleft()
        return None

stack = StackUsingQueue()
stack.push(10)
stack.push(20)
stack.push(30)
print(stack.pop())
print(stack.pop())
print(stack.pop())

A 30\n10\n20

B 10\n20\n30

C 30\n20\n10

D 20\n30\n10

💡 Hint

Think about how the queue is rotated after each push to simulate stack behavior.

The push method rotates the queue so the last pushed element is always at the front, making pop remove the last pushed element first, mimicking stack LIFO behavior.

🧠 Conceptual

intermediate

Understanding Time Complexity of Stack Operations Using Two Queues

If a stack is implemented using two queues where push operation is costly and pop operation is cheap, what is the time complexity of push and pop respectively?

A Push: O(n), Pop: O(1)

B Push: O(n), Pop: O(n)

C Push: O(1), Pop: O(n)

D Push: O(1), Pop: O(1)

💡 Hint

Consider which operation involves moving all elements between queues.

In the costly push approach, push moves all elements to the other queue to maintain order, taking O(n). Pop just dequeues from the front, O(1).

🔧 Debug

advanced

Identify the Error in Stack Using Queue Implementation

What error will the following code produce when calling pop on an empty stack implemented using one queue?

DSA Python

from collections import deque

class StackUsingQueue:
    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()

stack = StackUsingQueue()
print(stack.pop())

A AttributeError

B IndexError: pop from an empty deque

C None

D IndexError

💡 Hint

What happens when you pop from an empty deque?

Calling popleft() on an empty deque raises IndexError with message 'pop from an empty deque'.

❓ Predict Output

advanced

Output of Mixed Push and Pop Operations Using Two Queues

What is the output of the following code implementing stack with two queues where pop is costly?

DSA Python

from collections import deque

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

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

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

stack = StackUsingTwoQueues()
stack.push(5)
stack.push(10)
print(stack.pop())
stack.push(15)
print(stack.pop())
print(stack.pop())

A 10\n15\n5

B 5\n10\n15

C 15\n10\n5

D 10\n5\n15

💡 Hint

Pop removes the last pushed element by moving all but last to the other queue.

Pop removes 10 first, then after pushing 15, pop removes 15, then finally 5 remains.

🧠 Conceptual

expert

Minimum Number of Queues to Implement a Stack with O(1) Amortized Push and Pop

What is the minimum number of standard FIFO queues required to implement a stack with both push and pop operations having O(1) amortized time complexity?

A Two queues

B One queue

C Three queues

D Impossible with any finite number of queues

💡 Hint

Consider the fundamental difference between FIFO and LIFO behaviors and the cost of rearranging elements.

It is proven that implementing a stack with both push and pop in O(1) amortized time using only FIFO queues is impossible due to their ordering constraints.