0
$\begingroup$

A deque is implemented with 3 stacks. one for the head, one for the tail and one is always empty. Pushing is therefor O(1), light popping (in case the head/tail respectively aren't empty) is also O(1). A 'heavy pop' is in a scenario when we have k elements, only in 1 stack and we wish to pop the other stack. For example, n elements in head and we want to pop the tail. In this case, we push all elements from head stack to the empty stack, than push n/2 elements to the tail and the remaining n/2 back to the head.

I'm having troubles finding the potential function for this solution, or the amortized value for that case. If I define the potential function to be the number of current elements in the deque, I get linear time. I don't know if this is true but I feel like it's not.

$\endgroup$
0
$\begingroup$

The intuition is following: the "bad" case when you have to do expensive operation is when one of the stacks is empty, and the other one is big. You need to compensate its real cost with a potential decrease. Thus, you can define potential function as $2 \lvert \operatorname{size}(head) - \operatorname{size}(tail) \rvert$.

(For simplicity I represent hard pop as combination of two operations - rearrangement of elements using the third stack and a light pop)

Before the rearrangement, one of the stacks is empty, and other one contains $k$ elements, and right after both contains $\frac{k}{2}$. Therefore, the potential decreases on $2k$ and amortized cost of rearrangement is

$(k + \frac{k}{2} + \frac{k}{2}) + (-2k) = 0 = O(1)$

The amortized costs of light pop and push are clearly $O(1)$ as well as potential increases on $2$ at most.

$\endgroup$
2
  • $\begingroup$ Amazing! could you explain why is it okay to multiply by 2 in the potential function? $\endgroup$ – Nix Mar 29 '20 at 23:45
  • 1
    $\begingroup$ @Nix Well, because nobody's stopping us :) The only restriction on potential function is non-negativity (for more details you can see CLRS book). $\endgroup$ – Vladislav Mar 30 '20 at 0:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.