Implement Stack Using a Single Queue

Implement Stack Using a Single Queue

Implement a stack's push and pop operations using only a single queue.

Input format

The first line contains Q. Each of the next Q lines is one of: push x, pop, top. Use only a single queue internally.

Output format

For each pop print the removed value and for each top print the top 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
push 4
push 5
push 68
pop
top
push 78
pop
top

-1
68
5
78
5

7
push 81
top
pop
top
pop
top
top

81
81
-1
-1
-1
-1