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.

Queues are naturally First-In-First-Out, but we want Last-In-First-Out. To turn a flat line into a stack, we need a way to force the newest person to jump all the way to the front of the line.

Think of it as a Line Jumper. When a new person arrives at the back of the queue, we tell everyone in front of them to leave and rejoin the line behind them. By the time everyone has moved, the newcomer is at the very front, ready to be served first.

The Line Jumper

- Push: This is where all the work happens. We enqueue the new item like normal. Then, we find out how many people were already in line (N). We dequeue those N people one by one and immediately re-enqueue them at the back. Now, our newest item is sitting at the head of the queue.
- Pop/Top: Since we did all the heavy lifting during the Push, these become simple, fast operations. The person at the front of the queue is always the person who arrived last.

Code Blueprint
text
CLASS MyStack:
    queue = []

    FUNCTION push(x):
        queue.ENQUEUE(x)
        FOR i from 1 to queue.SIZE - 1:
            queue.ENQUEUE(queue.DEQUEUE())

    FUNCTION pop():
        RETURN queue.DEQUEUE()

    FUNCTION top():
        RETURN queue.PEEK()
Worked Example:each push re-sorts the front
0
1
Front/Top
push(1): Enqueue 1. Queue is [1]. Front/Top is 1.
0
2
Front/Top
1
1
push(2): Enqueue 2 -> [1, 2]. Rotate queue size-1 times: dequeue 1, enqueue 1 -> [2, 1]. Top element 2 is now at front.
0
3
Front/Top
1
2
2
1
push(3): Enqueue 3 -> [2, 1, 3]. Rotate queue size-1 times: dequeue 2 and enqueue 2, dequeue 1 and enqueue 1 -> [3, 2, 1]. Top is 3.
0
2
Front/Top
1
1
pop(): Dequeue front element 3. Queue is now [2, 1]. LIFO top popped successfully!
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