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.