Constant amortized complexity for implementing a queue using two stacks

Question

METHOD: Maintain two stacks A and B. Push into A. To pop look at B. If B is empty then pop A completely and push it into B and then pop from B. Otherwise simply pop from B.

QUESTION : 1)What is the difference between running time and amortized running time? 2)Why is the amortized running time constant here? Will it not increase with the increasing number of input and when we decide to pop from it? Because if we keep pushing then A fills up quite a lot while B is empty. Now if we decided to pop from B then I need to copy all of A and then pop.

Answer 1

When looking at amortized cost, you don't look at a single operation but on multiple operations which occur during program execution. The idea is that, if you have a lot of operations which are very cheap (like a single push or pop), and few operations which are expensive (like popping all items from A and pushing it to B) you can "distribute" the cost of the expensive operations to the inexpensive ones. This gives you a "overall" cost compared to the worst case O(n) for a single dequeue.

In your example, you can show that each element is pushed to a stack two times at max (once for adding and once for pushing it to the other stack) and popped max. two times (once for popping it from the stack and once for popping it to remove it from the queue). So for an enqueue operation, the amortized max. cost is 3 (because when an element is pushed and never popped it might still be popped and pushed to the other stack) and 1 for a dequeue which is both constant.