= Three-stack deque
{title2=$\Phi=3\bigl||F|-|B|\bigr|$}
A <deque> can use two permanent <stacks> holding the front and back portions, plus an empty temporary <stack>. When removal encounters an empty side, park the top half of the other side in the temporary <stack>, reverse its remaining half into the empty side, and restore the parked half. This preserves order and balances the permanent <stacks>. The <potential method> with $\Phi=3\bigl||F|-|B|\bigr|$ pays for the <linear time> transfer from the previous size imbalance, giving constant <amortized cost> for all four endpoint operations with only a fixed number of size counters.
Back to article page
