Subsections


2.1 $ \mathtt{ArrayStack}$: Fast Stack Operations Using an Array

An $ \mathtt{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}}$.

  array<T> a;
  int n;
  int size() {
    return n;
  }

2.1.1 The Basics

Accessing and modifying the elements of an $ \mathtt{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) {
    return a[i];
  }
  T set(int i, T x) {
    T y = a[i];
    a[i] = x;
    return y;
  }

The operations of adding and removing elements from an $ \mathtt{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 $ \mathtt{ArrayStack}$. Arrows denote elements being copied. Operations that result in a call to $ \mathtt{resize()}$ are marked with an asterisk.
\includegraphics[scale=0.90909]{figs/arraystack}

  void add(int i, T x) {
    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()}$, then 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}})$.

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, then we call $ \mathtt{resize()}$ to reduce the size of $ \mathtt{a}$.

  T remove(int i) {
      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() {
    array<T> b(max(2 * n, 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 $ \mathtt{ArrayStack}$ 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 any time $ \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 ,
$

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 occurs 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$.2.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 R$ $\displaystyle \ge \ensuremath{\mathtt{a.length}}/2 - 1 - \ensuremath{\mathtt{a.length}}/3$    
  $\displaystyle = \ensuremath{\mathtt{a.length}}/6 - 1$    
  $\displaystyle = (\ensuremath{\mathtt{a.length}}/3)/2 - 1$    
  $\displaystyle \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 $ \mathtt{ArrayStack}$:

Theorem 2..1   An $ \mathtt{ArrayStack}$ implements the $ \mathtt{List}$ interface. Ignoring the cost of calls to $ \mathtt{resize()}$, an $ \mathtt{ArrayStack}$ supports the operations Furthermore, beginning with an empty $ \mathtt{ArrayStack}$ and performing 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 $ \mathtt{ArrayStack}$ is an efficient way to implement a $ \mathtt{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

....2.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