Implement Stack using Queues easy

Description

Implement a last-in-first-out (LIFO) stack using only queues. The stack should support:

• push(x) — push x onto the top of the stack
• pop() — remove and return the top element
• top() — peek at the top
• empty() — return whether the stack is empty

You may only use the standard queue operations: push to back, pop from front, peek front, size, isEmpty.

Examples

s.push(1)
s.push(2)
s.top()      # -> 2
s.pop()      # -> 2
s.empty()    # -> False

Constraints

• All calls to pop and top are on a non-empty stack.

Intuition

A queue gives you the oldest element. A stack wants the newest. We have to invert that somehow.

There are two natural designs:

• Two queues. Use one as the “main” queue, the other as a scratch space.
• One queue, expensive push. After every push, rotate the queue so the just-pushed element ends up at the front.

The one-queue version is simpler — let’s do that.

One-queue trick

Push the new element, then rotate the queue: dequeue size - 1 items and re-enqueue them at the back. The just-pushed element is now at the front, where pop and peek can reach it directly.

start:        []
push(1):     [1]               (no rotation needed)
push(2):     [2, 1]            after pushing 2 then rotating (move 2 to end? no — see trace below)

Trace push(2) carefully:

before push:        [1]
after enqueue(2):   [1, 2]
rotate (size-1 = 1 time): dequeue 1, enqueue 1
                    [2, 1]    ← 2 is now at the front

That’s the magic. Every push is O(n), but pop and top are O(1).

Code

#include <queue>
using namespace std;
 
class MyStack {
    queue<int> q;
public:
    void push(int x) {
        q.push(x);
        int n = q.size();
        for (int i = 0; i < n - 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(); }
};

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

import java.util.Queue;
import java.util.ArrayDeque;
 
class MyStack {
    private Queue<Integer> q = new ArrayDeque<>();
 
    public void push(int x) {
        q.offer(x);
        int n = q.size();
        for (int i = 0; i < n - 1; i++) q.offer(q.poll());
    }
 
    public int pop()    { return q.poll(); }
    public int top()    { return q.peek(); }
    public boolean empty() { return q.isEmpty(); }
}

Explanation

• After enqueueing the new element, the queue looks like [old_front, …, old_back, new_x].
• Rotating n-1 times brings new_x to the front: [new_x, old_front, …, old_back].
• That makes the rest of the operations trivially O(1).

Analysis

• Time: push is O(n). pop, top, empty are O(1).
• Space: O(n).