Implement Stack Using Queue in DSA Python - Time & Space Complexity

Time Complexity: Implement Stack Using Queue

O(n)

Understanding Time Complexity

We want to understand how long it takes to perform stack operations when using a queue to build it.

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

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class StackUsingQueue:
    def __init__(self):
        self.q = []

    def push(self, x):
        self.q.append(x)
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.pop(0))

    def pop(self):
        return self.q.pop(0) if self.q else None

    def top(self):
        return self.q[0] if self.q else None

    def empty(self):
        return len(self.q) == 0
    

This code uses one queue to simulate a stack. The push operation rotates the queue to keep the newest element at the front.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop inside the push method that moves elements from front to back.
• How many times: It runs (n-1) times where n is the current number of elements in the queue.

How Execution Grows With Input

Each push moves almost all existing elements to the back of the queue to keep the newest element at front.

Input Size (n)	Approx. Operations in push
10	9 moves
100	99 moves
1000	999 moves

Pattern observation: The number of moves grows linearly as the stack grows.

Final Time Complexity

Time Complexity: O(n)

This means pushing an item takes longer as the stack gets bigger, roughly proportional to the number of items.

Common Mistake

[X] Wrong: "Push operation is always O(1) because we just add one item to the queue."

[OK] Correct: Because after adding, we rotate all other items to keep stack order, which takes O(n) time.

Interview Connect

Understanding how to build one data structure using another and analyzing its time helps you think flexibly and solve problems creatively.

Self-Check

"What if we used two queues instead of one? How would the time complexity of push and pop change?"