Assume that we have a data type $stack$ which has two operation $push$ and $pop$, both operations' time complexity is $O(1)$ in worst case. The $stack$ also has a property $size$ indicate how many elements are in the $stack$, and can be accessed in constant time.
I want to emulate a $queue$ by using two stacks $queue = (stack_{push}, stack_{pop})$ with two operations $insert$ and $remove$
$insert(queue, e)$ is implemented as:
insert(queue, e) {
push(stack_push, e)
}
$remove(queue)$ is implemented as:
remove(queue) {
if (stack_pop.size > 0) {
pop(stack_pop)
} else {
while(stack_push.size > 0) {
push(stack_pop, pop(stack_push))
}
pop(stack_pop)
}
}
It is obviously that $insert$ takes constant time and $remove$ takes $O(n)$ time in worst case. (where n is the size of the queue).
Now considering an sequence of queue operation with length $n$ (pop an empty stack is allowed), I want to get the amortized time complexity of this queue structure. My guess is that the amortized time complexity is $O(1)$, since it seems that the worst case of the sequence is first $insert$ n-1 elements then $remove$, so the total cost is $O(n)$ then the amortized time is $O(n)/n = O(1)$. However I cannot figure out how to prove it.
My question is that is the amortized time complexity of the queue's operation really $O(1)$ and how to prove it?