Implement Queue using Stacks

A queue is first-in, first-out: elements leave in the order they arrived, like a line at a shop. A stack is the opposite (last-in, first-out). Curiously, two stacks can simulate a queue: reversing a stack into another stack flips its order.

Implement a class MyQueue using only two Python lists used as stacks (you may only append to the end, pop from the end, read the last element and check emptiness). Provide these methods:

• push(x) – add x to the back of the queue.
• pop() – remove and return the element at the front.
• peek() – return the element at the front without removing it.
• empty() – return True if the queue is empty, otherwise False.

pop and peek are only called on a non-empty queue. The tests call the methods in sequence with run_ops and compare the list of return values (None for methods that return nothing).

Examples

Input:  ops  = ["MyQueue", "push", "push", "peek", "pop", "empty"]
        args = [[],        [1],    [2],    [],     [],    []]
Output: [None, None, None, 1, 1, False]
Explanation: after pushing 1 then 2 the front is 1; pop removes 1; the queue still holds 2.

Constraints

• At most 100 operations per test
• 1 <= x <= 100

Goals

• Explain the difference between FIFO (queue) and LIFO (stack) order
• Build one data structure out of another and keep state across method calls
• Move elements between stacks lazily so that each element is transferred at most once