Queue Using Two Stacks in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of enqueue and dequeue operations

What is the printed state of the queue after these operations using two stacks?

DSA Python

class QueueUsingStacks:
    def __init__(self):
        self.stack_in = []
        self.stack_out = []

    def enqueue(self, x):
        self.stack_in.append(x)

    def dequeue(self):
        if not self.stack_out:
            while self.stack_in:
                self.stack_out.append(self.stack_in.pop())
        if self.stack_out:
            return self.stack_out.pop()
        return None

q = QueueUsingStacks()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.dequeue()
q.enqueue(4)
result = []
while True:
    val = q.dequeue()
    if val is None:
        break
    result.append(val)
print(result)

A [1, 3, 4]

B [1, 2, 3, 4]

C [3, 4]

D [2, 3, 4]

💡 Hint

Remember that dequeue moves elements from stack_in to stack_out only when stack_out is empty.

After enqueueing 1, 2, 3, the queue is [1, 2, 3]. The first dequeue removes 1. Then enqueue 4 adds it to stack_in. The remaining elements dequeued are 2, 3, 4.

❓ Predict Output

intermediate

Resulting queue after multiple dequeues

What is the output after these operations on a queue implemented with two stacks?

DSA Python

class QueueUsingStacks:
    def __init__(self):
        self.stack_in = []
        self.stack_out = []

    def enqueue(self, x):
        self.stack_in.append(x)

    def dequeue(self):
        if not self.stack_out:
            while self.stack_in:
                self.stack_out.append(self.stack_in.pop())
        if self.stack_out:
            return self.stack_out.pop()
        return None

q = QueueUsingStacks()
q.enqueue(10)
q.enqueue(20)
q.enqueue(30)
print(q.dequeue())
print(q.dequeue())
q.enqueue(40)
print(q.dequeue())
print(q.dequeue())

A

10
20
40
None

B

10
20
30
40

C

10
20
40
30

D

None
None
None
None

💡 Hint

Dequeue empties stack_out before moving elements from stack_in.

Dequeues remove 10 and 20 first. Then enqueue 40. Next dequeue removes 30, then 40.

🔧 Debug

advanced

Identify the error in dequeue method

What error will this code raise when calling dequeue on an empty queue?

DSA Python

class QueueUsingStacks:
    def __init__(self):
        self.stack_in = []
        self.stack_out = []

    def enqueue(self, x):
        self.stack_in.append(x)

    def dequeue(self):
        if not self.stack_out:
            while self.stack_in:
                self.stack_out.append(self.stack_in.pop())
        return self.stack_out.pop()

q = QueueUsingStacks()
print(q.dequeue())

A IndexError

B TypeError

C None

D SyntaxError

💡 Hint

What happens if you pop from an empty list?

When both stacks are empty, popping from stack_out causes IndexError.

🧠 Conceptual

advanced

Time complexity of dequeue operation

What is the average time complexity of the dequeue operation in a queue implemented using two stacks?

A O(n) for every dequeue

B O(log n)

C O(1) amortized time

D O(n^2)

💡 Hint

Consider how often elements move between stacks.

Each element is moved at most twice: once into stack_in and once into stack_out, so average dequeue is O(1).

❓ Predict Output

expert

Final state of stacks after operations

After executing the following code, what is the content of stack_in and stack_out?

DSA Python

class QueueUsingStacks:
    def __init__(self):
        self.stack_in = []
        self.stack_out = []

    def enqueue(self, x):
        self.stack_in.append(x)

    def dequeue(self):
        if not self.stack_out:
            while self.stack_in:
                self.stack_out.append(self.stack_in.pop())
        if self.stack_out:
            return self.stack_out.pop()
        return None

q = QueueUsingStacks()
q.enqueue(5)
q.enqueue(10)
q.enqueue(15)
q.dequeue()
q.enqueue(20)
q.dequeue()

A stack_in: [20], stack_out: [15]

B stack_in: [], stack_out: [10, 15]

C stack_in: [], stack_out: [15]

D stack_in: [20], stack_out: [5]

💡 Hint

Trace each enqueue and dequeue step carefully.

After first dequeue, stack_out has [10, 5] (top is 5 popped). After second dequeue, 10 is popped from stack_out leaving [15]. stack_in has 20 from last enqueue.

Practice

1. What is the main idea behind implementing a Queue using two stacks?

easy

A. Use two stacks to reverse the order twice to maintain FIFO

B. Use two stacks to store elements in sorted order

C. Use one stack for enqueue and another for dequeue operations

D. Use one stack and a queue together

Solution

1. Step 1: Understand queue order

   A queue follows FIFO (First In First Out), meaning the first element added is the first removed.

2. Step 2: Use two stacks to reverse order twice

   One stack reverses the order when pushing elements, and the second stack reverses it back when popping, preserving FIFO.

3. Final Answer:

   Use two stacks to reverse the order twice to maintain FIFO -> Option A

4. Quick Check:

   Two stacks reverse order twice = FIFO queue [OK]

Hint: Two reversals with stacks simulate queue order [OK]

Common Mistakes:

• Thinking one stack alone can maintain FIFO
• Confusing stack sorting with queue behavior
• Using a queue inside the stack implementation

2. Which of the following is the correct syntax to push an element x onto a stack named stack1 in Python?

easy

A. stack1.push(x)

B. stack1.append(x)

C. stack1.insert(x)

D. stack1.add(x)

Solution

1. Step 1: Recall Python list methods for stack

   Python lists use append() to add elements at the end, simulating stack push.

2. Step 2: Check other options

   push() and add() are not list methods; insert() requires an index.

3. Final Answer:

   stack1.append(x) -> Option B

4. Quick Check:

   Python stack push = append() [OK]

Hint: Use append() to push on Python list stack [OK]

Common Mistakes:

• Using push() which is not a Python list method
• Using insert() without index argument
• Confusing add() with set method

3. What will be the output of the following code implementing dequeue operation in a queue using two stacks?

stack1 = [1, 2, 3]
stack2 = []

if not stack2:
    while stack1:
        stack2.append(stack1.pop())

print(stack2.pop())

medium

A. 1

B. 3

C. 2

D. IndexError

Solution

1. Step 1: Transfer elements from stack1 to stack2

   Elements pop from stack1 in order 3, 2, 1 and append to stack2, so stack2 becomes [3, 2, 1].

2. Step 2: Pop from stack2

   Popping from stack2 removes last element, which is 1, the first element enqueued.

3. Final Answer:

   1 -> Option A

4. Quick Check:

   Two stacks reverse order, first out is 1 [OK]

Hint: Pop from second stack after transfer gives queue front [OK]

Common Mistakes:

• Assuming pop from stack1 directly returns front
• Confusing order after transfer
• Expecting 3 instead of 1

4. Identify the error in the following dequeue method of a queue implemented using two stacks:

def dequeue():
    if stack2.is_empty():
        while stack1:
            stack2.append(stack1.pop())
    return stack1.pop()

medium

A. Using stack2.is_empty() instead of checking if stack2 is empty

B. Using append() instead of push() on stack2

C. Popping from stack1 instead of stack2 after transfer

D. Not checking if both stacks are empty before popping

Solution

1. Step 1: Check stack transfer logic

   Elements are moved from stack1 to stack2 when stack2 is empty to reverse order.

2. Step 2: Identify pop operation error

   After transfer, popping should be from stack2 to get the correct queue front, but code pops from stack1 incorrectly.

3. Final Answer:

   Popping from stack1 instead of stack2 after transfer -> Option C

4. Quick Check:

   Pop from stack2 after transfer, not stack1 [OK]

Hint: Pop from stack2 after transfer, not stack1 [OK]

Common Mistakes:

• Popping from wrong stack after transfer
• Using non-existent is_empty() method on list
• Ignoring empty queue check

5. You want to implement a queue using two stacks where enqueue and dequeue operations are both efficient. Which approach below achieves amortized O(1) time per operation?

hard

A. Push elements to stack1; on dequeue, pop directly from stack1

B. Push elements alternately to stack1 and stack2; pop from the other stack

C. Push elements to stack2; on dequeue, pop from stack1

D. Push all elements to stack1 on enqueue; on dequeue, transfer all to stack2 if empty, then pop from stack2

Solution

1. Step 1: Understand enqueue operation

   All new elements are pushed onto stack1, which is fast (O(1)).

2. Step 2: Understand dequeue operation

   When stack2 is empty, transfer all elements from stack1 to stack2 (reversing order), then pop from stack2. This transfer happens only when needed, spreading cost.

3. Step 3: Analyze amortized time

   Each element moves at most twice (push to stack1, move to stack2), so average cost per operation is O(1).

4. Final Answer:

   Push all elements to stack1 on enqueue; on dequeue, transfer all to stack2 if empty, then pop from stack2 -> Option D

5. Quick Check:

   Amortized O(1) by lazy transfer from stack1 to stack2 [OK]

Hint: Transfer only when needed for amortized O(1) dequeue [OK]

Common Mistakes:

• Transferring elements on every dequeue causing O(n) each time
• Popping directly from stack1 breaking queue order
• Alternating pushes causing confusion