Next: 2.6 : A Space-Efficient Up: 2. Array-Based Lists Previous: 2.4 : Fast Deque Contents
: Building a Deque from Two Stacks
Next, we present another data structure, the
that
achieves the same performance bounds as an
by using
two
s. Although the asymptotic performance of the
is no better than that of the
, 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
represents a list using two
s. Recall that
an
is fast when the operations on it modify elements near
the end. A
places two
s, called
and
, back-to-back so that operations are fast at either end.
ArrayStack<T> front; ArrayStack<T> back;
A
does not explicitly store the number,
,
of elements it contains. It doesn't need to, since it contains
elements. Nevertheless, when
analyzing the
we will still use
to denote the number
of elements it contains.
int size() {
return front.size() + back.size();
}
The
contains list elements with indices
, but stores them in reverse order.
The
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() - i - 1);
} else {
return back.get(i - front.size());
}
}
T set(int i, T x) {
if (i < front.size()) {
return front.set(front.size() - i - 1, x);
} else {
return back.set(i - front.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
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(i - front.size(), x);
}
balance();
}
The
method performs rebalancing of the two
s
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
, the cost of this is
, then
becomes
.
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
(ignoring the cost of the call to
) is
.
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()-i-1);
} else {
x = back.remove(i-front.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() {
if (3*front.size() < back.size()
|| 3*back.size() < front.size()) {
int n = front.size() + back.size();
int nf = n/2;
array<T> af(max(2*nf, 1));
for (int i = 0; i < nf; i++) {
af[nf-i-1] = get(i);
}
int nb = n - nf;
array<T> ab(max(2*nb, 1));
for (int i = 0; i < nb; i++) {
ab[i] = get(nf+i);
}
front.a = af;
front.n = nf;
back.a = ab;
back.n = nb;
}
}
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.
is created and any sequence of 
calls
to
and
are performed, then the total time spent
during all calls to
is 
.
is forced to shift elements,
then the number of
and
operations since the
last time
shifted any elements is at least
.
As in the proof of Lemma 2.1, this is sufficient
to prove that the total time spent by
is .
We will perform our analysis using a technique knows as the
potential method. Define the potential, 
, of the
as the difference in size between
and
:
or
that does not do any balancing can increase the potential
by at most 1.
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,
 |
 |
 |
|
 |
 |
||
|
 |
 |
|
 |
|
 |
 |
||
|
 |
||
|
 |
||
|
 |
or
since
the last time
shifted elements is at least
. This completes the proof.
The following theorem summarizes the performance of a
implements the
interface. Ignoring the
cost of calls to
and
, a
supports the operations
and
in time per operation; and
and
in
time
per operation.
, any sequence of 
and
operations results in a total of
time spent during all calls to
and
.opendatastructures.org