2.5 DualArrayDeque: Building a Deque from Two Stacks

Next, we present a data structure, the DualArrayDeque that achieves the same performance bounds as an ArrayDeque by using two ArrayStacks. Although the asymptotic performance of the DualArrayDeque is no better than that of the ArrayDeque, it is still worth studying, since it offers a good example of how to make a sophisticated data structure by combining two simpler data structures.

A DualArrayDeque represents a list using two ArrayStacks. Recall that an ArrayStack is fast when the operations on it modify elements near the end. A DualArrayDeque places two ArrayStacks, called $\ensuremath{\ensuremath{\mathit{front}}}$ and $\ensuremath{\ensuremath{\mathit{back}}}$ , back-to-back so that operations are fast at either end.

$\begin{leftbar} \begin{flushleft} \hspace*{1em} \ensuremath{\mathrm{initialize}(... ...ets \ensuremath{\mathrm{\mathrm{ArrayStack}}()}}\\ \end{flushleft}\end{leftbar}$

A DualArrayDeque does not explicitly store the number, $\ensuremath{\ensuremath{\mathit{n}}}$ , of elements it contains. It doesn't need to, since it contains $\ensuremath{\ensuremath{\ensuremath{\mathit{n}}}}=\ensuremath{\ensuremath{\ens... ...ize}()}} + \ensuremath{\ensuremath{\ensuremath{\mathit{back}}.\mathrm{size}()}}$ elements. Nevertheless, when analyzing the DualArrayDeque we will still use $\ensuremath{\ensuremath{\mathit{n}}}$ to denote the number of elements it contains.

$\begin{leftbar} \begin{flushleft} \hspace*{1em} \ensuremath{\mathrm{size}()}\\ ... ...() + \ensuremath{\mathit{back}}.\mathrm{size}()}\\ \end{flushleft}\end{leftbar}$

The $\ensuremath{\ensuremath{\mathit{front}}}$ ArrayStack stores the list elements that whose indices are $0,\ldots,\ensuremath{\ensuremath{\ensuremath{\mathit{front}}.\mathrm{size}()}}-1$ , but stores them in reverse order. The $\ensuremath{\ensuremath{\mathit{back}}}$ ArrayStack contains list elements with indices in $\ensuremath{\ensuremath{\ensuremath{\mathit{front}}.\mathrm{size}()}},\ldots,\ensuremath{\ensuremath{\mathrm{size}()}}-1$ in the normal order. In this way, $\ensuremath{\mathrm{get}(\ensuremath{\mathit{i}})}$ and $\ensuremath{\mathrm{set}(\ensuremath{\mathit{i}},\ensuremath{\mathit{x}})}$ translate into appropriate calls to $\ensuremath{\mathrm{get}(\ensuremath{\mathit{i}})}$ or $\ensuremath{\mathrm{set}(\ensuremath{\mathit{i}},\ensuremath{\mathit{x}})}$ on either $\ensuremath{\ensuremath{\mathit{front}}}$ or $\ensuremath{\ensuremath{\mathit{back}}}$ , which take

time per operation.

$\begin{leftbar} \begin{flushleft} \hspace*{1em} \ensuremath{\mathrm{get}(\ensure... ...\ensuremath{\mathit{front}}.\mathrm{size}(), x})\\ \end{flushleft}\end{leftbar}$

Note that if an index $\ensuremath{\ensuremath{\ensuremath{\mathit{i}}}}<\ensuremath{\ensuremath{\ensuremath{\mathit{front}}.\mathrm{size}()}}$ , then it corresponds to the element of $\ensuremath{\ensuremath{\mathit{front}}}$ at position $\ensuremath{\ensuremath{\ensuremath{\mathit{front}}.\mathrm{size}()}}-\ensuremath{\ensuremath{\ensuremath{\mathit{i}}}}-1$ , since the elements of $\ensuremath{\ensuremath{\mathit{front}}}$ are stored in reverse order.

Adding and removing elements from a DualArrayDeque is illustrated in Figure 2.4. The $\ensuremath{\mathrm{add}(\ensuremath{\mathit{i}},\ensuremath{\mathit{x}})}$ operation manipulates either $\ensuremath{\ensuremath{\mathit{front}}}$ or $\ensuremath{\ensuremath{\mathit{back}}}$ , as appropriate:

**Figure 2.4:** A sequence of $\ensuremath{\mathrm{add}(\ensuremath{\mathit{i}},\ensuremath{\mathit{x}})}$ and $\ensuremath{\mathrm{remove}(\ensuremath{\mathit{i}})}$ operations on a DualArrayDeque. Arrows denote elements being copied. Operations that result in a rebalancing by $\ensuremath{\mathrm{balance}()}$ are marked with an asterisk.
$\includegraphics[scale=0.90909]{figs-python/dualarraydeque}$

$\begin{leftbar} \begin{flushleft} \hspace*{1em} \ensuremath{\mathrm{add}(\ensure... ...m} \hspace*{1em} \ensuremath{\mathrm{balance}()}\\ \end{flushleft}\end{leftbar}$

The $\ensuremath{\mathrm{add}(\ensuremath{\mathit{i}},\ensuremath{\mathit{x}})}$ method performs rebalancing of the two ArrayStacks $\ensuremath{\ensuremath{\mathit{front}}}$ and $\ensuremath{\ensuremath{\mathit{back}}}$ , by calling the $\ensuremath{\mathrm{balance}()}$ method. The implementation of $\ensuremath{\mathrm{balance}()}$ is described below, but for now it is sufficient to know that $\ensuremath{\mathrm{balance}()}$ ensures that, unless $\ensuremath{\ensuremath{\mathrm{size}()}}<2$ , $\ensuremath{\ensuremath{\mathit{front}}.\mathrm{size}()}$ and $\ensuremath{\ensuremath{\mathit{back}}.\mathrm{size}()}$ do not differ by more than a factor of 3. In particular, $3\cdot\ensuremath{\ensuremath{\ensuremath{\mathit{front}}.\mathrm{size}()}} \ge \ensuremath{\ensuremath{\ensuremath{\mathit{back}}.\mathrm{size}()}}$ and $3\cdot\ensuremath{\ensuremath{\ensuremath{\mathit{back}}.\mathrm{size}()}} \ge \ensuremath{\ensuremath{\ensuremath{\mathit{front}}.\mathrm{size}()}}$ .

Next we analyze the cost of $\ensuremath{\mathrm{add}(\ensuremath{\mathit{i}},\ensuremath{\mathit{x}})}$ , ignoring the cost of calls to $\ensuremath{\mathrm{balance}()}$ . If $\ensuremath{\ensuremath{\ensuremath{\mathit{i}}}}<\ensuremath{\ensuremath{\ensuremath{\mathit{front}}.\mathrm{size}()}}$ , then $\ensuremath{\mathrm{add}(\ensuremath{\mathit{i}},\ensuremath{\mathit{x}})}$ gets implemented by the call to $\ensuremath{\ensuremath{\ensuremath{\mathit{front}}.\mathrm{add}(\ensuremath{\mathit{front}}.\mathrm{size}()-\ensuremath{\mathit{i}}-1,x})}$ . Since $\ensuremath{\ensuremath{\mathit{front}}}$ is an ArrayStack, the cost of this is

Notice that the first case (2.1) occurs when $\ensuremath{\ensuremath{\ensuremath{\mathit{i}}}}<\ensuremath{\ensuremath{\ensuremath{\mathit{n}}}}/4$ . The second case (2.2) occurs when $\ensuremath{\ensuremath{\ensuremath{\mathit{i}}}}\ge 3\ensuremath{\ensuremath{\ensuremath{\mathit{n}}}}/4$ . When $\ensuremath{\ensuremath{\ensuremath{\mathit{n}}}}/4\le\ensuremath{\ensuremath{\ensuremath{\mathit{i}}}}<3\ensuremath{\ensuremath{\ensuremath{\mathit{n}}}}/4$ , we cannot be sure whether the operation affects $\ensuremath{\ensuremath{\mathit{front}}}$ or $\ensuremath{\ensuremath{\mathit{back}}}$ , but in either case, the operation takes $O(\ensuremath{\ensuremath{\ensuremath{\mathit{n}}}})=O(\ensuremath{\ensuremath... ...th{\ensuremath{\mathit{n}}}}-\ensuremath{\ensuremath{\ensuremath{\mathit{i}}}})$ time, since $\ensuremath{\ensuremath{\ensuremath{\mathit{i}}}}\ge \ensuremath{\ensuremath{\ensuremath{\mathit{n}}}}/4$ and $\ensuremath{\ensuremath{\ensuremath{\mathit{n}}}}-\ensuremath{\ensuremath{\ensuremath{\mathit{i}}}}> \ensuremath{\ensuremath{\ensuremath{\mathit{n}}}}/4$ . Summarizing the situation, we have

The $\ensuremath{\mathrm{remove}(\ensuremath{\mathit{i}})}$ operation and its analysis resemble the $\ensuremath{\mathrm{add}(\ensuremath{\mathit{i}},\ensuremath{\mathit{x}})}$ operation and analysis.

$\begin{leftbar} \begin{flushleft} \hspace*{1em} \ensuremath{\mathrm{remove}(\ens... ...bf{return}} \ensuremath{\ensuremath{\mathit{x}}}\\ \end{flushleft}\end{leftbar}$

2.5.1 Balancing

Finally, we turn to the $\ensuremath{\mathrm{balance}()}$ operation performed by $\ensuremath{\mathrm{add}(\ensuremath{\mathit{i}},\ensuremath{\mathit{x}})}$ and $\ensuremath{\mathrm{remove}(\ensuremath{\mathit{i}})}$ . This operation ensures that neither $\ensuremath{\ensuremath{\mathit{front}}}$ nor $\ensuremath{\ensuremath{\mathit{back}}}$ becomes too big (or too small). It ensures that, unless there are fewer than two elements, each of $\ensuremath{\ensuremath{\mathit{front}}}$ and $\ensuremath{\ensuremath{\mathit{back}}}$ contain at least $\ensuremath{\ensuremath{\ensuremath{\mathit{n}}}}/4$ elements. If this is not the case, then it moves elements between them so that $\ensuremath{\ensuremath{\mathit{front}}}$ and $\ensuremath{\ensuremath{\mathit{back}}}$ contain exactly $\lfloor\ensuremath{\ensuremath{\ensuremath{\mathit{n}}}}/2\rfloor$ elements and $\lceil\ensuremath{\ensuremath{\ensuremath{\mathit{n}}}}/2\rceil$ elements, respectively.

$\begin{leftbar} \begin{flushleft} \hspace*{1em} \ensuremath{\mathrm{balance}()}\... ...\ensuremath{\mathit{back}} \gets \ensuremath{b}}\\ \end{flushleft}\end{leftbar}$

Here there is little to analyze. If the $\ensuremath{\mathrm{balance}()}$ operation does rebalancing, then it moves $O(\ensuremath{\ensuremath{\ensuremath{\mathit{n}}}})$ elements and this takes $O(\ensuremath{\ensuremath{\ensuremath{\mathit{n}}}})$ time. This is bad, since $\ensuremath{\mathrm{balance}()}$ is called with each call to $\ensuremath{\mathrm{add}(\ensuremath{\mathit{i}},\ensuremath{\mathit{x}})}$ and $\ensuremath{\mathrm{remove}(\ensuremath{\mathit{i}})}$ . However, the following lemma shows that, on average, $\ensuremath{\mathrm{balance}()}$ only spends a constant amount of time per operation.

Proof. We will show that, if $\ensuremath{\mathrm{balance}()}$ is forced to shift elements, then the number of $\ensuremath{\mathrm{add}(\ensuremath{\mathit{i}},\ensuremath{\mathit{x}})}$ and $\ensuremath{\mathrm{remove}(\ensuremath{\mathit{i}})}$ operations since the last time any elements were shifted by $\ensuremath{\mathrm{balance}()}$ is at least $\ensuremath{\ensuremath{\ensuremath{\mathit{n}}}}/2-1$ . As in the proof of Lemma 2.1, this is sufficient to prove that the total time spent by $\ensuremath{\mathrm{balance}()}$ is

We will perform our analysis using a technique knows as the potential method. Define the potential, $\Phi$ , of the DualArrayDeque as the difference in size between $\ensuremath{\ensuremath{\mathit{front}}}$ and $\ensuremath{\ensuremath{\mathit{back}}}$ :

$\displaystyle \Phi = \vert\ensuremath{\ensuremath{\ensuremath{\mathit{front}}.\... ...emath{\ensuremath{\ensuremath{\mathit{back}}.\mathrm{size}()}}\vert \enspace .$

The interesting thing about this potential is that a call to $\ensuremath{\mathrm{add}(\ensuremath{\mathit{i}},\ensuremath{\mathit{x}})}$ or $\ensuremath{\mathrm{remove}(\ensuremath{\mathit{i}})}$ that does not do any balancing can increase the potential by at most 1.

Observe that, immediately after a call to $\ensuremath{\mathrm{balance}()}$ that shifts elements, the potential, $\Phi_0$ , is at most 1, since

$\displaystyle \Phi_0 = \left\vert\lfloor\ensuremath{\ensuremath{\ensuremath{\ma... ...remath{\ensuremath{\ensuremath{\mathit{n}}}}/2\rceil\right\vert\le 1 \enspace .$

Consider the situation immediately before a call to $\ensuremath{\mathrm{balance}()}$ that shifts elements and suppose, without loss of generality, that $\ensuremath{\mathrm{balance}()}$ is shifting elements because $3\ensuremath{\ensuremath{\ensuremath{\mathit{front}}.\mathrm{size}()}} < \ensuremath{\ensuremath{\ensuremath{\mathit{back}}.\mathrm{size}()}}$ . Notice that, in this case,

$\displaystyle \ensuremath{\ensuremath{\ensuremath{\mathit{n}}}}$	$\displaystyle =$	$\displaystyle \ensuremath{\ensuremath{\ensuremath{\mathit{front}}.\mathrm{size}()}}+\ensuremath{\ensuremath{\ensuremath{\mathit{back}}.\mathrm{size}()}}$
	$\displaystyle <$	$\displaystyle \ensuremath{\ensuremath{\ensuremath{\mathit{back}}.\mathrm{size}()}}/3+\ensuremath{\ensuremath{\ensuremath{\mathit{back}}.\mathrm{size}()}}$
	$\displaystyle =$	$\displaystyle \frac{4}{3}\ensuremath{\ensuremath{\ensuremath{\mathit{back}}.\mathrm{size}()}}$

Furthermore, the potential at this point in time is

$\displaystyle \Phi_1$	$\displaystyle =$	$\displaystyle \ensuremath{\ensuremath{\ensuremath{\mathit{back}}.\mathrm{size}()}} - \ensuremath{\ensuremath{\ensuremath{\mathit{front}}.\mathrm{size}()}}$
	$\displaystyle >$	$\displaystyle \ensuremath{\ensuremath{\ensuremath{\mathit{back}}.\mathrm{size}()}} - \ensuremath{\ensuremath{\ensuremath{\mathit{back}}.\mathrm{size}()}}/3$
	$\displaystyle =$	$\displaystyle \frac{2}{3}\ensuremath{\ensuremath{\ensuremath{\mathit{back}}.\mathrm{size}()}}$
	$\displaystyle >$	$\displaystyle \frac{2}{3}\times\frac{3}{4}\ensuremath{\ensuremath{\ensuremath{\mathit{n}}}}$
	$\displaystyle =$	$\displaystyle \ensuremath{\ensuremath{\ensuremath{\mathit{n}}}}/2$

Therefore, the number of calls to $\ensuremath{\mathrm{add}(\ensuremath{\mathit{i}},\ensuremath{\mathit{x}})}$ or $\ensuremath{\mathrm{remove}(\ensuremath{\mathit{i}})}$ since the last time $\ensuremath{\mathrm{balance}()}$ shifted elements is at least $\Phi_1-\Phi_0 > \ensuremath{\ensuremath{\ensuremath{\mathit{n}}}}/2-1$ . This completes the proof. $\qedsymbol$

2.5.2 Summary

Theorem 2..4 A DualArrayDeque implements the List interface. Ignoring the cost of calls to $\ensuremath{\mathrm{resize}()}$ and $\ensuremath{\mathrm{balance}()}$ , a DualArrayDeque supports the operations

$\ensuremath{\mathrm{get}(\ensuremath{\mathit{i}})}$ and $\ensuremath{\mathrm{set}(\ensuremath{\mathit{i}},\ensuremath{\mathit{x}})}$ in time per operation; and
$\ensuremath{\mathrm{add}(\ensuremath{\mathit{i}},\ensuremath{\mathit{x}})}$ and $\ensuremath{\mathrm{remove}(\ensuremath{\mathit{i}})}$ in $O(1+\min\{\ensuremath{\ensuremath{\ensuremath{\mathit{i}}}},\ensuremath{\ensur... ...{\ensuremath{\mathit{n}}}}-\ensuremath{\ensuremath{\ensuremath{\mathit{i}}}}\})$ time per operation.

Furthermore, beginning with an empty DualArrayDeque, any sequence of $\ensuremath{\mathrm{add}(\ensuremath{\mathit{i}},\ensuremath{\mathit{x}})}$ and $\ensuremath{\mathrm{remove}(\ensuremath{\mathit{i}})}$ operations results in a total of time spent during all calls to $\ensuremath{\mathrm{resize}()}$ and $\ensuremath{\mathrm{balance}()}$ .