Queue Using Two Stacks in DSA Python - Time & Space Complexity

Time Complexity: Queue Using Two Stacks

O(1) amortized

Understanding Time Complexity

We want to understand how fast operations run when we build a queue using two stacks.

Specifically, how does the time to add or remove items grow as we add more items?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

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

    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() if self.stack_out else None

This code adds items to one stack and removes items from another, moving items only when needed.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Moving all items from stack_in to stack_out when stack_out is empty.
• How many times: This move happens only when stack_out is empty, not on every dequeue.

How Execution Grows With Input

Adding items is always quick, but removing items sometimes requires moving many items.

Input Size (n)	Approx. Operations
10	About 10 moves when stack_out empties
100	About 100 moves occasionally, but mostly 1 per dequeue
1000	About 1000 moves occasionally, but mostly 1 per dequeue

Pattern observation: Most dequeues are fast, but occasionally a slow step moves many items all at once.

Final Time Complexity

Time Complexity: O(1) amortized per operation

This means on average, each add or remove takes a constant amount of time, even if some removals take longer.

Common Mistake

[X] Wrong: "Each dequeue always takes time proportional to the number of items."

[OK] Correct: Because items are moved only once from stack_in to stack_out, so the cost spreads out over many dequeues.

Interview Connect

Understanding this helps you explain how clever data structures can make slow steps rare, keeping average speed fast.

Self-Check

What if we moved items from stack_in to stack_out on every dequeue, even if stack_out is not empty? How would the time complexity change?