Implement Stack using Queues

Problem

Some runtimes expose only a queue primitive but legacy code expects a stack interface. Implement a last-in-first-out stack using a single queue: push(x), pop(), top(), and empty() must all behave exactly like a stack's.

Example 1:

Input: push(4); push(9); push(2); top(); pop(); pop(); top()
Output: 2, 2, 9, 4
Explanation: after pushes 4, 9, 2 the top is 2; popping yields 2 then 9, leaving 4 as the only element and the top.

Example 2:

Input: push(4); push(9); push(2); pop(); push(7); top()
Output: 2, 7
Explanation: pop removes 2; pushing 7 puts it on top of the remaining 9 and 4.

Constraints:

• 1 <= x <= 9 for every push in the tests; element counts are small.
• All operations combined are at most 200 calls.
• pop() and top() are never called on an empty stack.

Solution Breakdown

Approach - one queue, rotated at write time so the front is always the stack top.

A queue hands out elements in insertion order while a stack needs the newest first - the two orders are opposed, so some operation must pay to invert them. Paying at push time keeps every read free. push(x) appends x at the back, then transfers the len - 1 older elements from the front to the back one by one; when the rotation finishes, x sits at the front and the remaining elements preserve their previous relative order behind it. That is the whole invariant: front = top. Every subsequent pop() (dequeue the front), top() (peek the front), and empty() (length check) is O(1) with zero reordering, because the push already did the sorting.

Trace push(4), push(9), push(2): after 4 the queue is [4] (zero rotations needed); appending 9 gives [4, 9], one transfer rotates it to [9, 4]; appending 2 gives [9, 4, 2], two transfers rotate it to [2, 9, 4]. top() reads 2, pop() takes 2, leaving [9, 4] - and a later push(7) rotates just the live elements: [9, 4, 7] -> [7, 9, 4]. The rotation count always comes from the current length, so the invariant re-establishes itself over whatever the stack actually holds, no history bookkeeping.

Edge cases - the first push and pushes onto a single element rotate zero times (the len - 1 loop bounds itself); interleaved push-after-pop sequences work because each push re-establishes the invariant over the remaining elements; the empty check is a plain length test and the constraints promise no pop/top on empty.

Complexity - O(n) per push (the rotation touches every older element once), O(1) for pop, top, and empty; O(n) space for the queue. The mirrored design - O(1) push, O(n) pop - is equally valid; this one is preferred because stack consumers typically pop less often than they push. A deque with popleft is the honest O(1)-dequeue queue; a plain list's pop(0) adds an hidden shifting cost that only matters at large n.