# Amortized time complexity for double stack emulated queue

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?

• yes, the amortized complexity is still O(1) because the worst case always occurs when the stack_pop is empty. – Navjot Singh Mar 12 '19 at 9:07

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)$$.