= Solution
Use two permanent <stacks>, $F$ and $B$, and one temporary <stack>, $T$. At operation boundaries $T$ is empty. Maintain the <representation invariant> that the <deque>, read from front to back, is the top-to-bottom contents of $F$ followed by the bottom-to-top contents of $B$. Thus the tops of $F$ and $B$ are the two accessible ends. Maintain their sizes using two counters, requiring only $O(1)$ additional storage in <Big O notation>.
Adding at the front pushes onto $F$; adding at the back pushes onto $B$. Removing at an end whose permanent <stack> is nonempty simply pops that <stack>. If both permanent <stacks> are empty, report an empty <deque>.
Suppose a front removal finds $F$ empty and $B$ contains $m>0$ elements. Rebalance as follows:
* Move the top $\lfloor m/2\rfloor$ elements of $B$ onto $T$.
* Move all remaining $\lceil m/2\rceil$ elements of $B$ onto $F$.
* Move all elements of $T$ back onto $B$.
* Pop and return the top of $F$.
The parked elements are the back half of the <deque>; the unparked elements are the front half. Moving the front half onto $F$ reverses their <stack> order and exposes the correct front element. Parking and restoring the back half reverses it twice, preserving its original order in $B$. The temporary <stack> is empty again. For a back removal with $B$ empty, exchange the roles of $F$ and $B$ throughout. \b[Rebalance approximately half the elements, so both ends retain accessible elements after a large transfer.]
For the <amortized analysis>, count each push or pop as one unit and use the <potential method> with
$$
\Phi=3\bigl||F|-|B|\bigr|.
$$
Initially the <deque> is empty, so $\Phi=0$, and $\Phi$ is always nonnegative. An ordinary insertion or removal costs one unit and changes the size difference by at most one, giving <amortized cost> at most $4$.
For a rebalancing removal, let $h=\lfloor m/2\rfloor$. The parked half makes two transfers per element and the other half makes one; each transfer is a pop and a push. Including the final removal, the actual cost is
$$
c=4h+2(m-h)+1=2m+2h+1\leq3m+1.
$$
Before rebalancing the absolute size difference is $m$. Immediately after the split it is at most $1$, and after the removal it is at most $2$. Hence
$$
\widehat c=c+\Delta\Phi\leq(3m+1)+3(2-m)=7.
$$
Size tests and counter updates change only these constants. Summing the <amortized costs> and using nonnegative final potential proves \b[$O(1)$ amortized running time for all four operations, with three <stacks> and $O(1)$ additional storage]. An individual rebalancing operation can still take <linear time> in the current size.
Back to article page
