179. Implement Stack using Queues

A queue is FIFO, but a stack needs LIFO. After enqueueing a new element, rotate all the older elements behind it so the newest sits at the front — then front-of-queue behaves like top-of-stack.

Make push do the work

Keep one queue. On push(x):

1. Enqueue x at the back.
2. Move every element that was already there (there are size - 1 of them) from front to back, one at a time.

Now x is at the front, and every subsequent element is in reverse insertion order — exactly stack order. pop and top just read/remove the front; empty checks the size.

push(x): q.add(x); repeat size-1 times: q.add(q.poll())
pop():   return q.poll()
top():   return q.peek()
empty(): return q.isEmpty()

Worked example

push 1 → [1]; push 2 → enqueue 2 [1,2], rotate once [2,1]. Now top() = 2, pop() = 2.

Complexity

• Time: push O(n); pop/top/empty O(1).
• Space: O(n).

import java.util.LinkedList;
import java.util.Queue;

class MyStack {
    private Queue<Integer> q = new LinkedList<>();

    public MyStack() {
    }

    public void push(int x) {
        q.add(x);
        for (int i = 0; i < q.size() - 1; i++) {
            q.add(q.poll());  // rotate older elements behind the new one
        }
    }

    public int pop() {
        return q.poll();
    }

    public int top() {
        return q.peek();
    }

    public boolean empty() {
        return q.isEmpty();
    }
}