Queue Made of Two Stacks

A queue is first in, first out. Build one from two stacks (Python lists used only with append and pop() from the end) so that every operation takes O(1) on average. ops is a list of operations written as text: "push x", "pop" (remove and return the front), "peek" (return the front) and "empty" (return 1 if the queue is empty, otherwise 0).

Run them from an empty queue and return the results of every pop, peek and empty, in order. pop and peek are only used on a non-empty queue.

For ["push 1", "push 2", "peek", "pop", "empty"] the answer is [1, 1, 0].

Examples

Example 1

Input:

queue_with_two_stacks(['push 1', 'push 2', 'peek', 'pop', 'empty'])

Output:

[1, 1, 0]

Example 2

Input:

queue_with_two_stacks(['empty', 'push 5', 'empty'])

Output:

[1, 0]

Constraints

• 0 <= len(ops) <= 200000
• -10**9 <= x <= 10**9