Implement Queue Using Two Stacks

Implement Queue Using Two Stacks

Implement a queue's enqueue and dequeue operations using only two stacks.

Input format

The first line contains Q. Each of the next Q lines is one of: push x, pop, peek. Use only two stacks internally.

Output format

For each pop print the removed value and for each peek print the front value, one per line (-1 when empty).

Constraints

• Values fit in a 64-bit signed integer
• Trailing whitespace and a trailing newline are ignored by the judge

Read from stdin, write to stdout. Sample cases below show the exact format.

9
pop
peek
push 39
peek
push 45
pop
push 79
push 93
peek

-1
-1
39
39
45

7
pop
peek
peek
peek
pop
pop
peek

-1
-1
-1
-1
-1
-1
-1