Queue Implementation using Two Stacks

In this problem, you are required to implement a queue using two stacks. The queue must support the following operations:

• enqueue x: Insert the integer x into the queue.
• dequeue: Remove the front element from the queue and output its value. If the queue is empty, output -1.
• front: Output the front element of the queue without removing it. If the queue is empty, output -1.

You are expected to simulate the FIFO behavior of a queue using two LIFO stacks. When performing a dequeue or front operation, if the second stack is empty, transfer all elements from the first stack to the second. This process reverses the order of the elements so that the element that was inserted first in the enqueue operations becomes accessible. The FIFO property can be formally expressed as: $$ Q = \{x_1, x_2, \ldots, x_n\} $$ where \( x_1 \) is the front element.

inputFormat

The first line of input contains an integer n (1 ≤ n ≤ 10⁵), the number of operations to perform. Each of the following n lines contains one of the following operations:

• enqueue x - Enqueue the integer x (|x| ≤ 10⁹) into the queue.
• dequeue - Dequeue the front element of the queue.
• front - Output the front element of the queue without removing it.

outputFormat

For each dequeue or front operation, output the result on a new line. If the queue is empty when processing these operations, output -1.

6
enqueue 2
enqueue 3
front
dequeue
front
dequeue

2
2
3