資料結構及演算法

(5%) A queue is implemented using two stacks, $S_{in}$ and $S_{out}$. The implementation ensures the FIFO property by defining the operations as follows:

• Enqueue: The new element is simply pushed onto $S_{in}$.
• Dequeue:
  • If $S_{out}$ is not empty, the top element is popped from $S_{out}$.
  • If $S_{out}$ is empty, all elements are first transferred from $S_{in}$ to $S_{out}$ (by repeatedly popping from $S_{in}$ and pushing onto $S_{out}$), and then the top element is popped from $S_{out}$.

What is the amortized time complexity of the dequeue operation?