Stack Implementation using Queue

The problem. Implement a last-in-first-out stack using only queues. Your class MyStack must support push(x), pop() (remove and return the top), top() (return the top) and empty(). You may only use standard queue operations: add to the back, remove from the front, look at the front, size and is-empty. Calls to pop and top are always made on a non-empty stack.

Example

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

A queue always releases its oldest item; a stack must release its newest. Every solution is about getting the newest item to the front of a queue — either at pop time or at push time.