資料結構與演算法

(4 points) A queue $Q$ is implemented using two stacks $S_{\text{in}}$ and $S_{\text{out}}$ as follows. If each $\textsc{Push}$ or $\textsc{Pop}$ with the stack has a cost of $\Theta(1)$, what is the amortized cost per operation over a sequence of $m$ legal queue operations, starting from an empty state with the first operation being $\textsc{Enqueue}$?

ENQUEUE(Q, x):
1   PUSH(Q.S_in, x)

DEQUEUE(Q):
1   if Q.S_out is not empty
2       return POP(Q.S_out)
3   while Q.S_in is not empty
4       PUSH(Q.S_out, POP(Q.S_in))
5   return POP(Q.S_out)