Implement Stack using Queues

easy stack queue design

Problem

Implement a LIFO stack using only one FIFO queue. Support push, pop, top, and empty.

Inputpush(1); push(2); top(); pop();

Output2, 2

After push(x), rotate the queue (size-1) times so the new element sits at the front.

ops (semicolon-separated)

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 not self.q

class MyStack {
  constructor() { this.q = []; }
  push(x) {
    this.q.push(x);
    for (let i = 0; i < this.q.length - 1; i++) this.q.push(this.q.shift());
  }
  pop()  { return this.q.shift(); }
  top()  { return this.q[0]; }
  empty(){ return this.q.length === 0; }
}

class MyStack {
    Deque<Integer> q = new ArrayDeque<>();
    public void push(int x) {
        q.addLast(x);
        for (int i = 0; i < q.size() - 1; i++) q.addLast(q.pollFirst());
    }
    public int pop()  { return q.pollFirst(); }
    public int top()  { return q.peekFirst(); }
    public boolean empty() { return q.isEmpty(); }
}

class MyStack {
    queue<int> q;
public:
    void push(int x) {
        q.push(x);
        for (int i = 0; i < (int)q.size() - 1; i++) { q.push(q.front()); q.pop(); }
    }
    int pop()  { int v = q.front(); q.pop(); return v; }
    int top()  { return q.front(); }
    bool empty() { return q.empty(); }
};

Explanation

A queue is first-in-first-out, but a stack is last-in-first-out — the opposite. The clever trick here is to rotate the queue after every push so the newest item always sits at the front, where the queue lets us reach it cheaply.

When you call push(x), you first append x to the back. Then you take every other item that was already there and move it from front to back, one at a time. After this rotation, x has bubbled all the way to the front.

Because the top of the stack is always parked at the front of the queue, pop(), top(), and empty() become trivial — just read or remove the front. All the heavy lifting happens during push.

Example: push 1 → queue is [1]. Push 2: append to get [1, 2], then rotate once (move 1 to back) → [2, 1]. Now top() reads 2 and pop() removes 2, exactly like a stack.

So push costs O(n) work for the rotation, while the other three operations are O(1).

Time: push O(n), others O(1) Space: O(n)