Implement a stack using two queues.

Problem. Implement a LIFO stack using only two queues — push, pop, top, empty — with the queues' FIFO operations as your only primitives.

The idea

A queue preserves arrival order; to get LIFO you must force the most recently added element to the front of a queue so it dequeues first. You can pay that cost on push or on pop — both are valid; the choice just shifts where the O(n) lands.

Two-queue, costly push — O(n) push, O(1) pop

On each push, enqueue the new element into the empty helper queue, then drain the main queue behind it. Swap the references. The newest element is now at the front, so pop is a plain dequeue.

One-queue rotation — simpler, same cost

A single queue suffices: after enqueuing, rotate the queue by moving the older elements (size − 1 of them) to the back, which spins the new element to the front.

class MyStack {
    private final Deque<Integer> q = new ArrayDeque<>();

    public void push(int x) {
        q.offer(x);                       // add at back (FIFO enqueue)
        for (int i = q.size() - 1; i > 0; i--)
            q.offer(q.poll());            // rotate older elements behind x
    }                                     // now x is at the front

    public int pop()  { return q.poll();  }   // O(1): newest is at front
    public int top()  { return q.peek();  }
    public boolean empty() { return q.isEmpty(); }
}

Each push rotates size elements, so push is O(n); pop and top are O(1). (The two-queue version has the same asymptotics; this one is less code and easier to get right.)