Next, we present another 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 and , backtoback so that operations are fast at either end.
List<T> front; List<T> back;
A DualArrayDeque does not explicitly store the number, , of elements it contains. It doesn't need to, since it contains elements. Nevertheless, when analyzing the DualArrayDeque we will still use to denote the number of elements it contains.
int size() { return front.size() + back.size(); }
The ArrayStack contains list elements with indices , but stores them in reverse order. The ArrayStack contains list elements with indices in the normal order. In this way, and translate into appropriate calls to or on either or , which take time per operation.
T get(int i) { if (i < front.size()) { return front.get(front.size()i1); } else { return back.get(ifront.size()); } } T set(int i, T x) { if (i < front.size()) { return front.set(front.size()i1, x); } else { return back.set(ifront.size(), x); } }
Note that, if an index , then it corresponds to the element of at position , since the elements of are stored in reverse order.
Adding and removing elements from a DualArrayDeque is illustrated in Figure 2.4. The operation manipulates either or , as appropriate:

void add(int i, T x) { if (i < front.size()) { front.add(front.size()i, x); } else { back.add(ifront.size(), x); } balance(); }
The method performs rebalancing of the two ArrayStacks and , by calling the method. The implementation of is described below, but for now it is sufficient to know that ensures that, unless , and do not differ by more than a factor of 3. In particular, and .
Next we analyze the cost of , ignoring the cost of the operation. If , then becomes . Since is an ArrayStack, the cost of this is
Notice that the first case (2.1) occurs when . The second case (2.2) occurs when . When , we can't be sure whether the operation affects or , but in either case, the operation takes time, since and . Summarizing the situation, we have
The operation, and its analysis, is similar to the operation.
T remove(int i) { T x; if (i < front.size()) { x = front.remove(front.size()i1); } else { x = back.remove(ifront.size()); } balance(); return x; }
Finally, we study the operation performed by and . This operation is used to ensure that neither nor gets too big (or too small). It ensures that, unless there are fewer than 2 elements, each of and contain at least elements. If this is not the case, then it moves elements between them so that and contain exactly elements and elements, respectively.
void balance() { int n = size(); if (3*front.size() < back.size()) { int s = n/2  front.size(); List<T> l1 = newStack(); List<T> l2 = newStack(); l1.addAll(back.subList(0,s)); Collections.reverse(l1); l1.addAll(front); l2.addAll(back.subList(s, back.size())); front = l1; back = l2; } else if (3*back.size() < front.size()) { int s = front.size()  n/2; List<T> l1 = newStack(); List<T> l2 = newStack(); l1.addAll(front.subList(s, front.size())); l2.addAll(front.subList(0, s)); Collections.reverse(l2); l2.addAll(back); front = l1; back = l2; } }
There is not much to analyze. If the operation does rebalancing, then it moves elements and this takes time. This is bad, since is called with each call to and . However, the following lemma shows that, on average, only spends a constant amount of time per operation.
We will perform our analysis using a technique knows as the potential method. Define the potential, , of the DualArrayDeque as the difference in size between and :
Observe that, immediately after a call to that shifts elements, the potential, , is at most 1, since
Consider the situation immediately before a call to
that
shifts elements and suppose, without loss of generality, that
is shifting elements because
.
Notice that, in this case,
The following theorem summarizes the performance of a DualArrayStack
opendatastructures.org