Design a Stack using a Single Queue

The problem. Implement a stack — push(x), pop(), top() and empty() — using only one queue. As before, you may only add at the back, remove from the front, look at the front, and ask for the size or whether it's empty. pop and top are only called on a non-empty stack.

Example

push(1)   push(2)   push(3)   pop() -> 3   top() -> 2   empty() -> false

The last problem used a second queue as a parking space while digging out the newest item. One queue can park items in itself: dequeue the front and enqueue it again at the back. This rotation — the same move as in hot potato — moves an item from the front to the back without losing it.

Rotate a queue of n items k times and the first k items move to the back, in the same order. Rotate it n times and it is exactly as it started. Every solution below is built from that one fact.