CODEWITHSUNDEEP
algorithmdata-structuresstackdequeamortized-analysis
Elior
Elior

Reputation: 3266

Implementing Deque using 3 Stacks (Amortized time O(1))

I have this question for howmework:

Implement a Deque using 3 Stacks. The Deque have those operations : InsertHead, InsertTail, DeleteHead,DeleteTail. Prove that the amortized time for each operation is O(1).

What I've tried is to look at the problem as Hanoi problem. So lets call the Stacks as: L(left), M (middle), R(right).

Pseudo-code Implementations:

InsertHead(e):
     L.push(e);

DeleteHead(e):
     L is empty:

       while R is not empty:
          pop and insert the element to M;
       pop M;
       while M is not empty:
         pop and insert the element to R;

     L is not empty:    
       L.pop(e);

InsertTail and DeleteTail are on the same principle of the above implementations. How can I prove that the amortized time is O(1)? because there can be N elements in L and the wile loop will take O(n), now if I'll call the deleteHead N times to calculate an amortized time the complexity will not be O(n^2)?

can someone help me how can I prove that the above implementations take O(1) in amortized time?

Deque from 3 Stacks: DeleteHead operation of Deque

Upvotes: 4

Views: 5774

Answers (1)

user2513351
user2513351

Reputation:

We proceed using the potential method; define

Phi = C |L.size - R.size|

For some constant C for which we will pick a value later. Let Phi_t denote the potential after t operations. Note that in a "balanced" state where both stacks have equal size, the data structure has potential 0.

The potential at any time is a constant times the difference in the number of elements in each stack. Note that Phi_0 = 0 so the potential is zero when the structure is initialised.

It is clear that a push operation increases the potential by at most C. A pop operation which does not miss (i.e. where the relevant stack is nonempty) also alters the potential by at most C. Both of these operations have true cost 1, hence they have amortised cost 1 + C.

When a pop operation occurs and causes a miss (when the stack we want to pop from is empty), the true cost of the operation is 1 + 3/2 * R.size for when we are trying to pop from L, and vice versa for when we are popping from R. This is because we move half of R's elements to M and back, and the other half of R's elements to L. The +1 is needed because of the final pop from L after this rebalancing operation is done.

Hence if we take C := 3/2, then the pop operation when a miss occurs has amortised cost 1, because the potential reduces from 3/2 * R.size to 0 due to the rebalancing, and then we may incur an additional cost of 3/2 from the pop which occurs after the rebalance.

In other words, each operation has an amortised cost bounded by a constant.

Finally, because the initial potential is 0, and the potential is always nonnegative, each operation is amortised cost O(1), as required.

Upvotes: 2

Related Questions