Implement Queue using Stacks

Easy · Stack & Monotonic Stack · about 10 minutes

Asked at Microsoft, Google, Amazon, Bloomberg, Apple, Samsung.

Implement a FIFO queue using only two stacks (push to top, pop/peek from top, size, empty).

• MyQueue() creates the queue.
• push(x) adds x to the back; pop() removes and returns the front; peek() returns the front;

empty() reports whether the queue is empty.

Calls to pop and peek are always valid. Aim for amortized O(1) per operation.