Design a Queue using Two Stacks

The problem. Implement a first-in-first-out queue using only two stacks. Your class MyQueue must support push(x) (add x at the back), pop() (remove and return the front item), peek() (return the front item) and empty(). You may only use standard stack operations: push to the top, look at or pop the top, size and is-empty. pop and peek are only called when the queue isn't empty.

Example

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

A stack hands back its newest item; a queue must hand back its oldest. The one tool we have is in the picture above: pouring a stack into another reverses it, which brings the oldest item to the top.

In JavaScript a plain array is a perfect stack — push and pop both work at the end in O(1) — so there's no hidden cost here.