Implement Queue using Stacks

Implement a first-in-first-out (FIFO) queue using only two last-in-first-out (LIFO) stacks. Implement the MyQueue class:

• MyQueue() creates an empty queue.
• push(x) adds x to the back of the queue.
• pop() removes the item at the front of the queue and returns it.
• peek() returns the item at the front without removing it.
• empty() returns true if the queue holds no items, and false otherwise.

The classic two-stack trick: push to an inbox stack; when pop/peek is called and the outbox stack is empty, drain the inbox into the outbox (which reverses the order), then serve from the outbox top.

Each example lists the calls in order, then each call's arguments, then each call's result (null for the constructor and for push, which returns nothing).

Constraints

• 1 ≤ x ≤ 10⁹
• At most 10⁴ calls are made in total to push, pop, peek and empty.
• pop and peek are only called on a non-empty queue.