CODEWITHSUNDEEP
stackqueuecomplexity-theoryasymptotic-complexityamortized-analysis
Dubby
Dubby

Reputation: 1144

Constant amortized complexity for implementing a queue using two stacks

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.

Upvotes: 4

Views: 9570

Answers (2)

sdm
sdm

Reputation: 1246

The key idea here is that an item moves from stack1 to stack2 just once in its whole lifetme i.e. its pushed in stack1, gets moved to stack2 and then popped out. There's no going back and forth whatsoever. So it can undergo 4 operations at the most in its life cycle

  1. (First push) Initial push in stack1 on enqueue
  2. (First pop) When popped for movement from stack 1 to stack2
  3. (Second push) When pushed in stack 2 for movement from stack 1 to stack2
  4. (Second pop) When popped out on dequeue

Let's say each push/pop operation costs $1. So an item would consume $4 right from getting enqueued to getting dequeued. So if you were running this enqueue/dequeue business, your business would break even ($0 profit or loss) if you started charging $4 for each enqueue and dequeue operation. Hence a $4 amortised cost for each enqueue/dequeue combined operation.

Rather if you were running an enqueue only business, you could just charge $1 since you have only 1 push to do and your job is done. Hence a $1 amortised cost for each enqueue operation.

And if you were running a dequeue only business, you would charge $3 for each dequeue operation as you would have to pop twice and push once as described in the steps above. Hence a $3 amortised cost for each dequeue operation.

Upvotes: 6

frow
frow

Reputation: 874

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.

Upvotes: 6

Related Questions