Stack Using Queues

Implement Stack using Queues is a classic data-structure puzzle: build a LIFO stack when the only tool you have is a FIFO queue. It forces you to think about how the order of operations can reshape a structure that pulls from the wrong end.

The slow way first

A queue hands you elements in the order they arrived: oldest first. A stack needs the opposite — newest first. So if you naively keep everything in one queue, pop() would have to walk all the way to the back to reach the newest item, dequeuing and re-enqueuing every other element each time. That is O(n) per pop, and it repeats the same shuffling work on every call.

The question to ask: which operation do I want to be cheap? If we make pop() and top() the cheap ones (O(1)), we can afford to pay the cost up front, during push.

The idea: rotate after every push

Keep a single queue, but maintain an invariant: the front of the queue is always the most recently pushed value. To preserve it, every push(x) does two things — enqueue x at the back, then rotate: dequeue and re-enqueue each of the other elements one at a time. After those rotations, x has bubbled to the front and the rest trail behind in stack order.

With that invariant held, top() is just peeking the front and pop() is a single dequeue — both O(1). The whole cost of being a stack moves into push.

Walk through it

Step through the animation. Each push enqueues the new value at the back, then you watch the older elements rotate around so the newest slides to the front. After push(1), push(2), push(3) the queue reads [3, 2, 1] — newest first. Then top() peeks 3 and pop() dequeues 3, leaving 2 as the new top.

Pseudocode

push(x):
    enqueue x at the back
    repeat (size - 1) times:           # rotate the older elements around
        move the front element to the back (dequeue then enqueue)
    # now x is at the front
 
pop():
    return dequeue (remove the front)   # the newest value
 
top():
    return the front element (peek)     # the newest value
 
empty():
    return whether the queue has no elements

The Python solution

from collections import deque
 
class MyStack:
    def __init__(self):
        self.q = deque()
 
    def push(self, x):
        self.q.append(x)
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())
 
    def pop(self):
        return self.q.popleft()
 
    def top(self):
        return self.q[0]
 
    def empty(self):
        return len(self.q) == 0

• self.q is a single deque used as a FIFO queue: append adds to the back, popleft removes the front.
• In push, line 8 enqueues x at the back.
• Lines 9 and 10 are the rotation: len(self.q) - 1 times, take the front element and move it to the back. This walks every older element behind x, leaving x at the front.
• pop is a plain popleft — the front is already the newest value, so removing it is O(1).
• top peeks self.q[0], the front, also O(1).
• empty reports whether the queue holds nothing.

Complexity

We deliberately make push expensive (O(n)) so that pop and top stay O(1). The total space is O(n) for the single queue holding the elements.

When this pattern shows up

Practice