Queue Using Two Stacks in DSA Python

Mental Model

Use two stacks to mimic the behavior of a queue by reversing the order twice.

Analogy: Imagine two trays where you put plates in one tray stacked on top, then flip them onto the second tray to get the plates in the original order to serve first in, first out.

stack_in: []
stack_out: []

Dry Run Walkthrough

Input: enqueue 1, enqueue 2, enqueue 3, dequeue, enqueue 4, dequeue

Goal: Simulate a queue using two stacks and show the order of elements after each operation

Step 1: enqueue 1 by pushing onto stack_in

stack_in: [1]
stack_out: []

Why: New elements go into stack_in to keep insertion order

Step 2: enqueue 2 by pushing onto stack_in

stack_in: [1, 2]
stack_out: []

Why: Keep adding new elements on top of stack_in

Step 3: enqueue 3 by pushing onto stack_in

stack_in: [1, 2, 3]
stack_out: []

Why: Stack_in holds all new elements in order

Step 4: dequeue: stack_out empty, move all from stack_in to stack_out reversing order

stack_in: []
stack_out: [3, 2, 1]

Why: Reversing stack_in to stack_out makes oldest element on top for dequeue

Step 5: pop from stack_out to dequeue element 1

stack_in: []
stack_out: [3, 2]

Why: Pop from stack_out gives the oldest element in queue order

Step 6: enqueue 4 by pushing onto stack_in

stack_in: [4]
stack_out: [3, 2]

Why: New elements always go to stack_in

Step 7: dequeue: pop from stack_out element 2

stack_in: [4]
stack_out: [3]

Why: stack_out still has elements, so pop directly

Result:

stack_in: [4]
stack_out: [3]
Dequeued elements in order: 1, 2

Annotated Code

DSA Python

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

    def enqueue(self, value):
        # Push new element onto stack_in
        self.stack_in.append(value)

    def dequeue(self):
        # If stack_out is empty, move all elements from stack_in to stack_out
        if not self.stack_out:
            while self.stack_in:
                # Pop from stack_in and push onto stack_out to reverse order
                self.stack_out.append(self.stack_in.pop())
        # Pop from stack_out if not empty
        if self.stack_out:
            return self.stack_out.pop()
        else:
            return None  # Queue is empty

# Driver code to test the queue
queue = QueueUsingTwoStacks()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(queue.dequeue())  # Expected 1
queue.enqueue(4)
print(queue.dequeue())  # Expected 2

self.stack_in.append(value)

Add new element to stack_in to keep insertion order

if not self.stack_out:

Check if stack_out is empty to decide if we need to reverse stack_in

self.stack_out.append(self.stack_in.pop())

Move elements from stack_in to stack_out reversing order for dequeue

return self.stack_out.pop()

Pop from stack_out to dequeue the oldest element

Output

1

2

Complexity Analysis

Time: O(1) amortized because each element is moved at most twice between stacks

Space: O(n) because all elements are stored in two stacks combined

vs Alternative: Compared to a simple queue using a list where dequeue is O(n) due to shifting, this approach achieves O(1) amortized dequeue by using two stacks

Edge Cases

dequeue from empty queue

Returns None indicating queue is empty

DSA Python

if self.stack_out:

enqueue then dequeue immediately

Works correctly by moving element to stack_out if needed

DSA Python

if not self.stack_out:

multiple enqueues before any dequeue

All elements accumulate in stack_in until first dequeue

DSA Python

while self.stack_in:

When to Use This Pattern

When you need a queue but only have stacks, use two stacks to reverse order twice and simulate FIFO behavior efficiently.

Common Mistakes

Mistake: Not moving elements from stack_in to stack_out when stack_out is empty before dequeue
Fix: Add a check to transfer all elements from stack_in to stack_out only when stack_out is empty

Mistake: Popping from stack_in directly on dequeue
Fix: Always pop from stack_out after transferring elements to maintain correct order

Summary

Implements a queue using two stacks by reversing element order twice.

Use when you want queue behavior but only have stack operations available.

The key insight is that reversing twice restores the original order for FIFO.

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