Algorithm

Implement Stack using Queues

Design Pattern

Stack using Queues

Implement a last in first out (LIFO) stack using only two queues. The implemented stack should support push, top, pop and empty. void push(int x) pushes element x to the top. int pop() removes and returns the top element. int top() returns the top element. boolean empty() returns true if the stack is empty. Each operation must only use standard queue operations (enqueue to back, dequeue from front, size, isEmpty).

CONSTRAINTS
  • 1 <= x <= 9
  • At most 100 calls to push, pop, top, and empty
  • All calls to pop and top are valid
EXAMPLE 1
Input: push(1), push(2), top(), pop(), empty()
Output: 2, 2, false
1 then 2 are pushed; after push(2) the queue front is 2 (the newest). top and pop both return 2. 1 remains, so empty is false — LIFO order holds.
EXAMPLE 2
Input: push(3), pop(), push(5), top()
Output: 3, 5
3 is pushed and immediately popped → 3. Then 5 is pushed and is the only element, so top returns 5.
Can I do this with a single queue, or do I need two?
A single queue is enough: rotating the older elements behind each newcomer keeps the newest at the front. A two-queue version exists but does the same amount of work — one queue is simpler.
Where does the cost go, push or pop?
On push — each one rotates up to N elements, so push is O(N) while pop and top are O(1). This is the opposite trade from Queue using Stacks, which pushes cheaply and pays on pop.
Why rotate len(q) - 1 times exactly?
You only move the elements that existed before the newcomer. Since you append the newcomer first, that count is len(q) - 1. One too many sends the newcomer to the back and breaks the ordering.

This is the mirror image of Queue using Stacks, and it pays to state both structures plainly first. A queue is a line: you join at the back (enqueue) and leave from the front (dequeue) — first in, first out. A stack is a pile: you add and remove from the same top — last in, first out. We're given only queues and must behave like a stack. So the element we must serve first is the newest, but a queue always hands back its oldest. The gap between "newest" and "what the queue gives me" is the whole problem.

The reframe: make the queue's front be the newest

A queue will only ever return whatever sits at its front. So instead of fighting that, arrange for the most recently pushed element to be the front. When a new value arrives, enqueue it at the back as usual — then immediately rotate every older element around behind it. Concretely: if there were N elements already, dequeue them one at a time from the front and re-enqueue them at the back, N times. Each old element loops from front to back, and when the loop finishes the newcomer — which started at the back — has been carried all the way to the front. Now the queue's natural front-dequeue is stack order.

One queue, all the work at push time

This means push does the heavy lifting and pop/top become trivial — they just read the front, which we've already made correct.

python
from collections import deque

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

    def push(self, x):
        self.q.append(x)                 # newcomer enters at the back
        for _ in range(len(self.q) - 1): # rotate the OLDER elements behind it
            self.q.append(self.q.popleft())
        # now x is at the front

    def pop(self):
        return self.q.popleft()          # front is the newest → stack top

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

    def empty(self):
        return not self.q
Crucial Noterotate exactly len(q) - 1 times, not len(q). You want to move only the elements that were there before the new one — the newcomer itself must stay put at the front. Rotate one time too many and the newcomer loops back to the rear, breaking the ordering; one too few and an old element is left blocking the front. Since we append the newcomer first, the count of older elements is exactly len(q) - 1.
Worked Example:each push re-sorts the front
- push(1) → append: [1]. Rotate len-1 = 0 times. Queue [1] (front 1).
- push(2) → append: [1, 2]. Rotate 1 time: dequeue 1, enqueue 1 → [2, 1] (front 2, the newest).
- push(3) → append: [2, 1, 3]. Rotate 2 times: move 2 to back → [1, 3, 2], move 1 to back → [3, 2, 1] (front 3).
- top() → read front → 3, the last pushed. pop() → remove front → 3. Queue [2, 1].
- pop() → 2. empty() → false (1 remains). Perfect LIFO out of a FIFO structure.
The trade, and the pairing to remember

Here the expense lands on push — each one rotates up to N elements, so push is O(N) — while pop and top are O(1). Contrast Queue using Stacks, which pushed cheaply and paid an amortized cost on pop. That's the real lesson of this pair: when you simulate one ordering with its opposite, someone pays for the reversal — your only choice is which operation eats the cost. Pick based on which call your workload does more often: rotate-on-push (this design) if you pop far more than you push, or push cheaply and defer if the reverse. Recognizing that the cost is movable, not removable, is the transferable idea.

Interactive Strategy Visualization
STACK EMULATION INSIGHT

Circular Queue Rotation for LIFO behavior

Circular Hub

The Front-Loading Insight

When pushing a new element, it goes to the back. To make it the top, we rotate all existing elements around it until the new element reaches the front.

O(N) PUSH / O(1) POPEvery push involves N-1 rotations, ensuring the Stack Top is always at the Queue Front.
Operation1 / 7
[INITIALIZE]LIFO (Stack) vs FIFO (Queue): How to make the last element exit first?

Design Trade-off

By doing the work during Push, we keep Pop and Peek extremely fast (O(1)).

O(N) Push Rotation · O(1) Pop and Top
→
Cost Moved onto Push