Implement Stack using Queues: LIFO from FIFO

May 14, 20264 min read

leetcodeproblemeasystacksdesign

LeetCode's Implement Stack using Queues (problem 225) asks you to build a LIFO stack using only queue operations. A queue gives you FIFO ordering, so the challenge is flipping that around. The cleanest approach uses a single queue: every time you push, you append the new element and then rotate all the previous elements behind it. That way the newest element always sits at the front, and pop becomes a simple dequeue.

Single-queue stack: after appending, rotate all previous elements to the back so the newest element sits at the front. Pop and top are then O(1).

The approach: rotate on push

A queue lets you add to the back and remove from the front. A stack needs the opposite: the most recently added element should come out first. You can bridge that gap with one simple trick.

When you push a new element, append it to the back of the queue. Then, one by one, dequeue each of the elements that were already in the queue and re-enqueue them at the back. After rotating all the old elements, the new element is sitting at the front.

This means push does O(n) work, but pop and top become O(1). You pay the cost once during insertion and get constant-time retrieval. For problems where you call pop and top more often than push, this tradeoff works well.

The key observation: after every push, the queue is ordered from newest to oldest, front to back. That is exactly LIFO order.

Practice this pattern

The solution

from collections import deque

class MyStack:
    def __init__(self):
        self.q = deque()

    def push(self, x: int) -> None:
        self.q.append(x)
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())

    def pop(self) -> int:
        return self.q.popleft()

    def top(self) -> int:
        return self.q[0]

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

__init__: creates a single deque to serve as the underlying queue.
push: appends the new element, then rotates len(q) - 1 elements from the front to the back. After the loop, the new element is at the front of the queue.
pop: removes and returns the front element. Since the queue is maintained in LIFO order, the front is always the most recently pushed element.
top: peeks at the front element without removing it.
empty: returns True when the queue has no elements.

Step-by-step walkthrough

Step 1: push(1)

Queue has one element. No rotation needed since there are no previous elements.

Step 2: push(2) -- append then rotate

Append 2, then move 1 to the back. Now 2 (newest) is at the front.

Step 3: push(3) -- append then rotate twice

Append 3, then move 2 to back, then move 1 to back. Now 3 is at the front.

Step 4: top() returns 3

The front of the queue is 3, the most recently pushed element. O(1) access.

Step 5: pop() returns 3

Popleft removes 3 from the front. Queue becomes [2, 1]. Next pop returns 2.

Drill this with spaced repetition

Complexity analysis

Metric	Value	Why
Time (push)	O(n)	Each push rotates all existing elements to maintain LIFO order at the front
Time (pop/top)	O(1)	The front of the queue is always the most recent element, so removal and peek are constant time
Space	O(n)	The queue stores all n elements currently in the stack

Building blocks

Queue rotation. Dequeuing from the front and re-enqueuing at the back cycles elements through the queue. This rotation technique shows up whenever you need to reorder elements within a queue without extra storage. The number of rotations controls which element ends up at the front.

Invariant maintenance on insert. Instead of doing work at read time, you reorganize the data structure during every write so that reads are trivial. This is the opposite of the "lazy transfer" strategy in the mirror problem (Implement Queue using Stacks), where writes are cheap and reads occasionally pay for a bulk transfer.

FIFO-to-LIFO conversion. Understanding how to convert between access patterns is a recurring theme in data structure design questions. If you can implement a stack from queues, you can reason about any "implement X using Y" variant.

Edge cases

Single element. push(1), top(), pop(). No rotation happens during push because len(q) - 1 is 0. The loop body never executes.
Immediate pop after push. push(1), pop(), push(2), pop(). Each push-pop pair works independently. The queue is always empty between pairs, so each push rotates zero elements.
Multiple pushes then multiple pops. push(1), push(2), push(3), pop(), pop(), pop(). Returns 3, 2, 1. Confirms the full LIFO ordering is correct across a batch of operations.
Interleaved push and pop. push(1), push(2), pop(), push(3), pop(). Returns 2, then 3. After popping 2, pushing 3 and rotating yields [3, 1] at the front.
Empty check after draining. push(1), pop(), empty(). Should return True. Verify the queue is actually empty after removing the last element.

The rotation count is always len(q) - 1, not len(q). If you rotate all elements including the new one, you end up right back where you started and the new element is still at the back.

From understanding to recall

The single-queue stack is short, maybe ten lines of real logic. But the details matter. Is the rotation count len(q) - 1 or len(q)? Do you use popleft or pop? Do you rotate on push or on pop? Getting any of those wrong breaks the LIFO invariant in subtle ways that only show up on specific test sequences.

Spaced repetition drilling locks in these details. You write the implementation from scratch at increasing intervals until the rotation logic, the popleft calls, and the loop bound are all automatic. That is the difference between "I know you rotate elements" and "I can write it correctly in sixty seconds."

Build recall with CodeBricks