Queue Implementation Using Two Stacks

In this problem, you are given a sequence of operations to simulate a queue using two stacks. The queue should support two operations:

1. Enqueue: Add an element to the back of the queue.
2. Dequeue: Remove and return the element at the front of the queue. If the queue is empty, return -1.

Your task is to implement the queue using two stacks. Use the two-stack approach to transfer elements when needed in order to mimic the FIFO (first in, first out) behavior of a queue. All input will be provided through standard input (stdin) and all output should be written to standard output (stdout).

The underlying idea is to use one stack for enqueue operations and another stack to reverse the order when performing a dequeue operation. This method ensures that each element is processed correctly according to its arrival order.

inputFormat

The first line contains an integer (Q) representing the number of operations. Each of the following (Q) lines contains an operation in one of the following formats:

1 x (enqueue (x) to the queue) or
2 (dequeue the front element from the queue and print it).

Note: For each dequeue operation, you should print the dequeued element on a new line.

outputFormat

For every dequeue operation (operation type 2), output the element removed from the queue on a new line. If the queue is empty when attempting to dequeue, print (-1).## sample

9
1 1
1 2
1 3
2
2
1 4
2
2
2

1
2
3
4
-1