Subsections


2.1 ArrayStack: Fast Stack Operations Using an Array

An ArrayStack implements the list interface using an array $ \mathtt{a}$, called the backing array. The list element with index $ \mathtt{i}$ is stored in $ \mathtt{a[i]}$. At most times, $ \mathtt{a}$ is larger than strictly necessary, so an integer $ \mathtt{n}$ is used to keep track of the number of elements actually stored in $ \mathtt{a}$. In this way, the list elements are stored in $ \mathtt{a[0]}$,..., $ \mathtt{a[n-1]}$ and, at all times, $ \ensuremath{\mathtt{a.length}} \ge \ensuremath{\mathtt{n}}$.

    T[] a;
    int n;
    int size() {
        return n;
    }

2.1.1 The Basics

Accessing and modifying the elements of an ArrayStack using $ \mathtt{get(i)}$ and $ \mathtt{set(i,x)}$ is trivial. After performing any necessary bounds-checking we simply return or set, respectively, $ \mathtt{a[i]}$.

    T get(int i) {
        if (i < 0 || i > n - 1) throw new IndexOutOfBoundsException();
        return a[i];
    }
    T set(int i, T x) {
        if (i < 0 || i > n - 1) throw new IndexOutOfBoundsException();
        T y = a[i];
        a[i] = x;
        return y;
    }

The operations of adding and removing elements from an ArrayStack are illustrated in Figure 2.1. To implement the $ \mathtt{add(i,x)}$ operation, we first check if $ \mathtt{a}$ is already full. If so, we call the method $ \mathtt{resize()}$ to increase the size of $ \mathtt{a}$. How $ \mathtt{resize()}$ is implemented will be discussed later. For now, it is sufficient to know that, after a call to $ \mathtt{resize()}$, we can be sure that $ \ensuremath{\mathtt{a.length}}
> \ensuremath{\mathtt{n}}$. With this out of the way, we now shift the elements $ \ensuremath{\mathtt{a[i]}},\ldots,\ensuremath{\mathtt{a[n-1]}}$ right by one position to make room for $ \mathtt{x}$, set $ \mathtt{a[i]}$ equal to $ \mathtt{x}$, and increment $ \mathtt{n}$.

Figure 2.1: A sequence of $ \mathtt{add(i,x)}$ and $ \mathtt{remove(i)}$ operations on an ArrayStack. Arrows denote elements being copied. Operations that result in a call to $ \mathtt{resize()}$ are marked with an asterisk.
\includegraphics{figs/arraystack}

    void add(int i, T x) {
        if (i < 0 || i > n) throw new IndexOutOfBoundsException();
        if (n + 1 > a.length) resize();
        for (int j = n; j > i; j--) 
            a[j] = a[j-1];
        a[i] = x;
        n++;
    }
If we ignore the cost of the potential call to $ \mathtt{resize()}$, the cost of the $ \mathtt{add(i,x)}$ operation is proportional to the number of elements we have to shift to make room for $ \mathtt{x}$. Therefore the cost of this operation (ignoring the cost of resizing $ \mathtt{a}$) is $ O(\ensuremath{\mathtt{n}}-\ensuremath{\mathtt{i}}+1)$.

Implementing the $ \mathtt{remove(i)}$ operation is similar. We shift the elements $ \ensuremath{\mathtt{a[i+1]}},\ldots,\ensuremath{\mathtt{a[n-1]}}$ left by one position (overwriting $ \mathtt{a[i]}$) and decrease the value of $ \mathtt{n}$. After doing this, we check if $ \mathtt{n}$ is getting much smaller than $ \mathtt{a.length}$ by checking if $ \ensuremath{\mathtt{a.length}} \ge 3\ensuremath{\mathtt{n}}$. If so, we call $ \mathtt{resize()}$ to reduce the size of $ \mathtt{a}$.

    T remove(int i) {
        if (i < 0 || i > n - 1) throw new IndexOutOfBoundsException();
        T x = a[i];
        for (int j = i; j < n-1; j++) 
            a[j] = a[j+1];
        n--;
        if (a.length >= 3*n) resize();
        return x;
    }
If we ignore the cost of the $ \mathtt{resize()}$ method, the cost of a $ \mathtt{remove(i)}$ operation is proportional to the number of elements we shift, which is $ O(\ensuremath{\mathtt{n}}-\ensuremath{\mathtt{i}})$.

2.1.2 Growing and Shrinking

The $ \mathtt{resize()}$ method is fairly straightforward; it allocates a new array $ \mathtt{b}$ whose size is $ 2\ensuremath{\mathtt{n}}$ and copies the $ \mathtt{n}$ elements of $ \mathtt{a}$ into the first $ \mathtt{n}$ positions in $ \mathtt{b}$, and then sets $ \mathtt{a}$ to $ \mathtt{b}$. Thus, after a call to $ \mathtt{resize()}$, $ \ensuremath{\mathtt{a.length}} = 2\ensuremath{\mathtt{n}}$.

    void resize() {
        T[] b = newArray(Math.max(n*2,1));
        for (int i = 0; i < n; i++) {
            b[i] = a[i];
        }
        a = b;
    }

Analyzing the actual cost of the $ \mathtt{resize()}$ operation is easy. It allocates an array $ \mathtt{b}$ of size $ 2\ensuremath{\mathtt{n}}$ and copies the $ \mathtt{n}$ elements of $ \mathtt{a}$ into $ \mathtt{b}$. This takes $ O(\ensuremath{\mathtt{n}})$ time.

The running time analysis from the previous section ignored the cost of calls to $ \mathtt{resize()}$. In this section we analyze this cost using a technique known as amortized analysis. This technique does not try to determine the cost of resizing during each individual $ \mathtt{add(i,x)}$ and $ \mathtt{remove(i)}$ operation. Instead, it considers the cost of all calls to $ \mathtt{resize()}$ during a sequence of $ m$ calls to $ \mathtt{add(i,x)}$ or $ \mathtt{remove(i)}$. In particular, we will show:

Lemma 2..1   If an empty ArrayList is created and any sequence of $ m\ge 1$ calls to $ \mathtt{add(i,x)}$ and $ \mathtt{remove(i)}$ are performed, then the total time spent during all calls to $ \mathtt{resize()}$ is $ O(m)$.

Proof. We will show that anytime $ \mathtt{resize()}$ is called, the number of calls to $ \mathtt{add}$ or $ \mathtt{remove}$ since the last call to $ \mathtt{resize()}$ is at least $ \ensuremath{\mathtt{n}}/2-1$. Therefore, if $ \ensuremath{\mathtt{n}}_i$ denotes the value of $ \mathtt{n}$ during the $ i$th call to $ \mathtt{resize()}$ and $ r$ denotes the number of calls to $ \mathtt{resize()}$, then the total number of calls to $ \mathtt{add(i,x)}$ or $ \mathtt{remove(i)}$ is at least

$\displaystyle \sum_{i=1}^{r} (\ensuremath{\mathtt{n}}_i/2-1) \le m \enspace ,
$

which is equivalent to

$\displaystyle \sum_{i=1}^{r} \ensuremath{\mathtt{n}}_i \le 2m + 2r \enspace .
$

On the other hand, the total time spent during all calls to $ \mathtt{resize()}$ is

$\displaystyle \sum_{i=1}^{r} O(\ensuremath{\mathtt{n}}_i) \le O(m+r) = O(m) \enspace ,
$

which will prove the lemma since $ r$ is not more than $ m$. All that remains is to show that the number of calls to $ \mathtt{add(i,x)}$ or $ \mathtt{remove(i)}$ between the $ (i-1)$th and the $ i$th call to $ \mathtt{resize()}$ is at least $ \ensuremath{\mathtt{n}}_i/2$.

There are two cases to consider. In the first case, $ \mathtt{resize()}$ is being called by $ \mathtt{add(i,x)}$ because the backing array $ \mathtt{a}$ is full, i.e., $ \ensuremath{\mathtt{a.length}} = \ensuremath{\mathtt{n}}=\ensuremath{\mathtt{n}}_i$. Consider the previous call to $ \mathtt{resize()}$: After this previous call, the size of $ \mathtt{a}$ was $ \mathtt{a.length}$, but the number of elements stored in $ \mathtt{a}$ was at most $ \ensuremath{\mathtt{a.length}}/2=\ensuremath{\mathtt{n}}_i/2$. But now the number of elements stored in $ \mathtt{a}$ is $ \ensuremath{\mathtt{n}}_i=\ensuremath{\mathtt{a.length}}$, so there must have been at least $ \ensuremath{\mathtt{n}}_i/2$ calls to $ \mathtt{add(i,x)}$ since the previous call to $ \mathtt{resize()}$.

The second case to consider is when $ \mathtt{resize()}$ is being called by $ \mathtt{remove(i)}$ because $ \ensuremath{\mathtt{a.length}} \ge 3\ensuremath{\mathtt{n}}=3\ensuremath{\mathtt{n}}_i$. Again, after the previous call to $ \mathtt{resize()}$ the number of elements stored in $ \mathtt{a}$ was at least $ \ensuremath{\mathtt{a.length/2}}-1$.1 Now there are $ \ensuremath{\mathtt{n}}_i\le\ensuremath{\mathtt{a.length}}/3$ elements stored in $ \mathtt{a}$. Therefore, the number of $ \mathtt{remove(i)}$ operations since the last call to $ \mathtt{resize()}$ is at least

$\displaystyle \ensuremath{\mathtt{a.length}}/2 - 1 - \ensuremath{\mathtt{a.leng...
...emath{\mathtt{a.length}}/3)/2 - 1\ge \ensuremath{\mathtt{n}}_i/2 -1\enspace .
$

In either case, the number of calls to $ \mathtt{add(i,x)}$ or $ \mathtt{remove(i)}$ that occur between the $ (i-1)$th call to $ \mathtt{resize()}$ and the $ i$th call to $ \mathtt{resize()}$ is at least $ \ensuremath{\mathtt{n}}_i/2-1$, as required to complete the proof. $ \qedsymbol$

2.1.3 Summary

The following theorem summarizes the performance of an ArrayStack:

Theorem 2..1   An ArrayStack implements the List interface. Ignoring the cost of calls to $ \mathtt{resize()}$, an ArrayStack supports the operations Furthermore, beginning with an empty ArrayStack, any sequence of $ m$ $ \mathtt{add(i,x)}$ and $ \mathtt{remove(i)}$ operations results in a total of $ O(m)$ time spent during all calls to $ \mathtt{resize()}$.

The ArrayStack is an efficient way to implement a Stack. In particular, we can implement $ \mathtt{push(x)}$ as $ \mathtt{add(n,x)}$ and $ \mathtt{pop()}$ as $ \mathtt{remove(n-1)}$, in which case these operations will run in $ O(1)$ amortized time.



Footnotes

....1
The $ {}-1$ in this formula accounts for the special case that occurs when $ \ensuremath{\mathtt{n}}=0$ and $ \ensuremath{\mathtt{a.length}} = 1$.
opendatastructures.org