Amortized time complexity for double stack emulated queue

Question

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?

Answer 1

In the remove operation, every iteration of the while loop pops an element from stack_push, and this dominates the running time of remove. We can charge each such iteration to the insert operation which pushed the very same element to stack_push. This way we deduce that the amortized running time of both operations is $O(1)$.

You can formalize the above argument in various ways. As an example, if you perform $A$ insert operations and $B$ remove operations, then the argument above shows that you push at most $2A$ elements and pop at most $A+B$ elements. Hence the total running time is $O(A+B) = A \cdot O(1) + B \cdot O(1)$.