Implement Queue Using Two Stacks

You are required to implement a queue using two stacks, $\text{stack1}$ and $\text{stack2}$. The queue must support the following operations:

1. $\text{enqueue}(x)$: Insert the integer $x$ into the queue.
2. $\text{dequeue}()$: Remove the element from the front of the queue and return it. If the queue is empty, return $-1$.

When performing a dequeue operation, if $\text{stack2}$ is empty, transfer all elements from $\text{stack1}$ to $\text{stack2}$ and then pop from $\text{stack2}$. Otherwise, simply pop from $\text{stack2}$.

Process a series of commands provided via standard input as described below.

inputFormat

The first line contains an integer $N$, representing the total number of operations. Each of the next $N$ lines contains a command. A command is either:

• enqueue x where x is an integer to be inserted into the queue.
• dequeue which indicates that a dequeue operation should be performed.

For each dequeue command, output the result on a new line.

outputFormat

For every dequeue operation, output the returned integer on a separate line. If the queue is empty when a dequeue is requested, output -1.## sample

7
enqueue 2
enqueue 3
dequeue
enqueue 4
dequeue
dequeue
dequeue

2
3
4
-1