Design a Stack using Two Queues

The problem. Implement a last-in-first-out stack using only two 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. pop and top are only called when the stack isn't empty.

Example

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

A queue only ever releases its oldest item; a stack must release its newest. Every solution has to dig the newest item out of the back of a queue — the only question is when to do the digging, at pop time or at push time.

In JavaScript each queue below is a plain array used only with push (add at the back) and shift (remove from the front), so the queue operations are easy to see. shift is itself O(n) on large arrays; as the problem intends, we count queue operations.