Queue Implementation Using Two Stacks

You are required to implement a queue using two stacks. The queue should support the following operations:

1. (enqueue(x)): Insert element (x) to the end of the queue.
2. (dequeue()): Remove and return the element from the front of the queue.
3. (peek()): Retrieve the front element of the queue without removing it.
4. (empty()): Return whether the queue is empty.

The common technique is to use two stacks (S_1) and (S_2). When performing dequeue or peek operations, if (S_2) is empty, you should transfer all elements from (S_1) to (S_2) (thereby reversing the order). This guarantees that the front of the queue is on the top of (S_2), allowing you to perform the required operations in (O(1)) amortized time.

Implement your solution according to the specification below, ensuring that your solution reads from standard input (stdin) and writes to standard output (stdout).

inputFormat

The input begins with an integer (Q) indicating the number of operations to perform. Each of the following (Q) lines contains one operation in one of the following formats:

• enqueue x : Add integer (x) to the queue.
• dequeue : Remove and print the element from the front of the queue.
• peek : Print the element at the front of the queue.
• empty : Print true if the queue is empty, otherwise print false.

Only the operations dequeue, peek, and empty produce output.

outputFormat

For each operation that produces an output (dequeue, peek, and empty), print the corresponding result on a separate line. The outputs should appear in the same order as the operations in the input.## sample

4
enqueue 1
peek
dequeue
empty

1
1
false