Amortized value of dequeue with potential function

Question

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.

Answer 1

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.