1911. A Stack Built From Queues

Build a stack using only queue operations: add to the back, remove from the front, and read the size. You may not index into the storage, and you may not remove from the back.

Operations arrive one per line:

push x put x on top pop remove the top and print it top print the top without removing it empty print YES if the stack is empty, otherwise NO

pop and top on an empty stack print EMPTY and leave the structure usable.

## What most people try first

Two queues, and a shuffle between them on every pop: move everything except the last element across, hand back what is left, then swap the roles. That works, but it is the expensive half of the trade made in the wrong place, and it is easy to get the "except the last" count wrong by one. The deeper mistake is assuming two containers are needed at all.

## Pay on push, in one queue

A queue hands back the oldest element and a stack needs the newest, so one of the two operations has to reverse the order. Decide which one pays. Making push expensive keeps pop, top and empty at constant cost, which is the better trade because reads outnumber writes in nearly every use of a stack.

Add the new element at the back, then rotate every element that was already there from the front to the back:

push 1 queue: 1 push 2 append 2 -> 1 2 rotate 1 element -> 2 1 push 3 append 3 -> 2 1 3 rotate 2 elements -> 3 2 1 pop front is 3, which is the newest

## Why it is correct

Claim: after every push, the queue holds the elements newest first.

It holds trivially for the first push. Suppose it holds for a queue of size m. Appending the new element gives newest-first order followed by the new element at the back. Rotating exactly m elements moves that whole prefix behind the new element and preserves its internal order, because a rotation is order preserving. The new element is therefore at the front and the rest are still newest first, which is the claim for size m + 1. So the front of the queue is always the top of the stack, and pop and top are plain reads.

## The boundary that breaks a careless implementation

Rotate m + 1 elements instead of m and the new element travels all the way back round to the end, so the structure behaves as a queue again and the very first sample fails.

The other trap is underflow. An empty pop must print EMPTY and advance nothing. A raw read cursor that moves anyway is still correct for that one line and then silently loses the next value pushed, which is why there is a test that over-pops twice and then pushes again.

## Overflow

A value reaches 1000000000 in magnitude, which fits in a signed 32 bit integer, and the structure never adds two values together: it only stores, copies and prints them. So the element type needs no widening.

The count of element moves is a different matter. If you instrument the rotation and total the moves, that total is quadratic in the number of pushes and a 32 bit counter is the wrong type for it.

## Cost

push is O(size), and pop, top and empty are O(1). Over q operations the total is O(q^2) in the worst case, about 2 * 10^6 element moves at the stated limit, which is why the limit is 2000 rather than the 100000 a constant time structure would allow. The judge cannot enforce a per-operation bound, so a solution that reverses on pop instead also passes; it is the same total work moved to the other side, and the point of the problem is choosing the side deliberately.

Constraints - `1 ≤ q ≤ 2000` - `-1000000000 ≤ x ≤ 1000000000` - `push` runs in `O(size)` and `pop`, `top` and `empty` in `O(1)`.