Stack Implementation Using Queues

You are required to implement a stack using two queues. In this problem, you must design a data structure that supports the following operations:

• push x: Push the integer x onto the stack.
• pop: Remove the element on top of the stack and output it. If the stack is empty, output None.
• top: Output the element on top of the stack without removing it. If the stack is empty, output None.

You must implement the stack using two queues. One possible method is to use the following idea: When performing a push, enqueue the new element into an empty secondary queue and then move all the elements from the primary queue to the secondary queue, and finally swap the two queues. This ensures that the front element of the primary queue is always the top of the stack.

The operations pop and top should operate in O(1) time on average.

Note: If a pop or top operation is called on an empty stack, print None.

For clarity, the abstract idea behind the push operation using two queues is given by the formula below in LaTeX:

$$\text{After } push(x): \quad Q_1 = \{ x, a_1, a_2, \dots, a_k \} $$

where \(a_1, a_2, \dots, a_k\) were the elements previously in the stack.

inputFormat

The first line of input contains an integer n (\(1 \leq n \leq 10^4\)) representing the number of operations. Each of the following n lines contains one operation, which is one of the following commands:

• push x where x is an integer.
• pop
• top

Input is read from standard input (stdin).

outputFormat

For each pop or top operation, output the result on a separate line. The results are printed to standard output (stdout). If an operation is attempted on an empty stack, output None.

## sample

6
push 1
push 2
top
pop
top
pop

2
2
1
1

</p>