栈的数组实现

ArrayStack 概述

接下来，我们将研究使用数组作为底层数据存储的 List 和 Queue 接口实现，该数组被称为后备数组。下表总结了这些数据结构的操作运行时间：

优点与局限性

通过单一数组存储数据的数据结构具有许多共同的优点和局限性：

• 数组支持对任意位置元素的常数时间访问。这使得 get(i) 和 set(i, x) 操作能够以常数时间运行。

• 数组的动态性较差。在列表中间附近添加或删除元素时，需要移动大量元素来腾出空间或填补空缺。因此，add(i, x) 和 remove(i) 操作的运行时间依赖于 $n$ 和 $i$。

• 数组无法自动扩展或收缩。当数据结构中的元素数量超过后备数组大小时，必须分配一个新数组，并将旧数组中的数据复制到新数组中。这是一个代价较高的操作。

第三点尤为重要。上表中列出的运行时间并未包含扩容和缩容后备数组的成本。我们将会看到，如果管理得当，扩容和缩容的代价并不会显著增加平均操作的成本。更准确地说，如果我们从一个空的数据结构开始，执行任意序列的 $m$ 次 add(i, x) 或 remove(i) 操作，那么在整个操作序列中，扩容和缩容后备数组的总成本为 $O(m)$。虽然某些单个操作成本较高，但将其摊销到全部 $m$ 次操作后，每次操作的摊销成本仅为 $O(1)$。

ArrayStack：使用数组实现快速栈操作

ArrayStack 使用数组 a（称为后备数组）来实现列表接口。索引为 i 的列表元素存储在 a[i]。大多数情况下，a 的大小会大于实际所需，因此用整数 n 来记录实际存储的元素数量。这样，列表元素存储在 $\text{a}[0], \ldots, \text{a}[n - 1]$ 中，且始终满足 $\text{a.length} \ge n$。

1T[] a;
2int n;
3int size() {
4  return n;
5}

基本操作

使用 get(i) 和 set(i, x) 访问和修改 ArrayStack 中的元素非常简单。在完成必要的边界检查后，直接返回或设置 a[i] 即可。

1T get(int i) {
2  return a[i];
3}
4
5T set(int i, T x) {
6  T y = a[i];
7  a[i] = x;
8  return y;
9}

ArrayStack 上的 add(i, x) 和 remove(i) 操作如下图所示。箭头表示元素被复制。导致调用 resize() 的操作用星号标记。

实现 add(i, x) 操作时，首先检查数组 a 是否已满。如果是，则调用 resize() 方法扩大数组大小。resize() 的具体实现稍后讨论。目前只需知道，在调用 resize() 后，可以确保 $\text{a.length} > n$。之后，将元素 $\text{a}[i], \ldots, \text{a}[n - 1]$ 向右整体移动一位以腾出空间，然后将 x 放入 a[i]，最后将 n 加一。

1void add(int i, T x) {
2  if (n + 1 > a.length) resize();
3  for (int j = n; j > i; j--)
4    a[j] = a[j - 1];
5  a[i] = x;
6  n++;
7}

忽略可能调用 resize() 的成本，add(i, x) 操作的成本与为插入 x 而需移动的元素数量成正比。因此，忽略扩容成本时，该操作的时间复杂度为 $O(n - i)$。

remove(i) 操作的实现类似。我们将元素 $\text{a}[i+1], \ldots, \text{a}[n-1]$ 向左整体移动一位（覆盖 a[i]），并将 n 减一。之后检查 n 是否远小于 a.length，即是否满足 $\text{a.length} \ge 3n$。若是，则调用 resize() 缩小数组。

1T remove(int i) {
2  T x = a[i];
3  for (int j = i; j < n - 1; j++)
4    a[j] = a[j + 1];
5  n--;
6  if (a.length >= 3 * n) resize();
7  return x;
8}

忽略 resize() 方法的成本，remove(i) 操作的成本与移动的元素数量成正比，为 $O(n - i)$。

扩容与缩容

resize() 方法实现较为简单：它分配一个大小为 $2n$ 的新数组 b，将 a 中的 n 个元素复制到 b 的前 n 个位置，然后将 a 指向 b。因此，调用 resize() 后，$\text{a.length} = 2n$。

1void resize() {
2  T[] b = newArray(max(n * 2, 1));
3  for (int i = 0; i < n; i++) {
4    b[i] = a[i];
5  }
6  a = b;
7}

分析 resize() 操作的实际成本很容易。它分配了一个大小为 $2n$ 的数组 b，并将 a 中的 n 个元素复制到 b 中，耗时 $O(n)$。

前一节的运行时间分析忽略了 resize() 调用的成本。本节将使用一种称为 摊销分析 的技术来分析这一成本。该技术不试图确定每次 add(i, x) 和 remove(i) 操作中 resize() 的具体成本，而是考虑在 $m$ 次 add(i, x) 或 remove(i) 操作序列中所有 resize() 调用的总成本。特别地，我们将证明：

引理：若创建一个空的 ArrayStack，并执行任意长度为 $m \ge 1$ 的 add(i, x) 与 remove(i) 操作序列，则所有 resize() 调用的总耗时为 $O(m)$。

证明：我们将证明，每次调用 resize() 时，自上次调用 resize() 以来，add 或 remove 的调用次数至少为 $n/2 - 1$。设 $n_i$ 为第 $i$ 次调用 resize() 时的 n 值，$r$ 为 resize() 的调用次数，则总的 add 或 remove 操作次数至少为

$$\sum_{i=1}^{r} (n_i/2 - 1) \leq m$$

等价于

$$\sum_{i=1}^{r} n_i \leq 2m + 2r$$

另一方面，所有 resize() 调用的总耗时为

$$\sum_{i=1}^{r} O(n_i) \leq O(m + r) = O(m)$$

因为 $r \leq m$。剩下的工作是证明：在第 $(i-1)$ 次和第 $i$ 次调用 resize() 之间，add(i, x) 或 remove(i) 的调用次数至少为 $n_i / 2$。

有两种情况需要考虑：

• 情况一：resize() 由 add(i, x) 调用，因为后备数组 a 已满，即 $\text{a.length} = n = n_i$。考虑上一次调用 resize() 之后的情况：当时数组大小为 a.length，但存储的元素数量最多为 $\text{a.length}/2 = n_i/2$。而现在存储的元素数量为 $n_i = \text{a.length}$，因此自上次调用 resize() 以来，至少有 $n_i / 2$ 次 add(i, x) 调用。

• 情况二：resize() 由 remove(i) 调用，因为 $\text{a.length} \ge 3n = 3n_i$。同样，在上一次调用 resize() 之后，存储的元素数量至少为 $\text{a.length}/2 - 1$。

注意：上述公式中的 -1 是为了处理 n = 0 且 a.length = 1 的特殊情况。

现在，a 中存储的元素数量为 $n_i \le \text{a.length}/3$。因此，自上次调用 resize() 以来，remove(i) 操作的次数至少为

$$\begin{split} R & \geq \text{a.length}/2 - 1 - \text{a.length}/3 \\ & = \text{a.length}/6 - 1 \\ & = (\text{a.length}/3)/2 - 1 \\ & = n_i / 2 - 1 \end{split}$$

在任一情况下，自第 $(i-1)$ 次调用 resize() 到第 $i$ 次调用 resize() 之间，add 或 remove 的调用次数至少为 $n_i / 2 - 1$，这完成了证明。

ArrayStack 的分析

以下定理总结了 ArrayStack 的性能：

定理：ArrayStack 实现了 List 接口。忽略 resize() 调用的成本，ArrayStack 支持以下操作：

• get(i) 与 set(i, x) 每次操作耗时 $O(1)$；
• add(i, x) 与 remove(i) 每次操作耗时 $O(1 + n - i)$。

此外，从一个空的 ArrayStack 开始，执行任意 $m$ 次 add(i, x) 与 remove(i) 操作，所有 resize() 调用的总耗时为 $O(m)$。

ArrayStack 是实现栈的一种高效方式。特别是，我们可以将 push(x) 实现为 add(n, x)，将 pop() 实现为 remove(n - 1)，此时这两个操作的摊销时间均为 $O(1)$。

说明

让我们从 main.java 文件中 main() 函数的开头部分进行解释：

• 第 61 行：创建了一个名为 stack 的新 ArrayStack，类型为整数，用于存储元素。
• 第 63–65 行：向 stack 添加三个元素。add(n, x) 方法的第一个参数是插入位置的索引，第二个参数是元素的值。
• 第 67 行：使用 size() 方法打印当前 stack 的大小。
• 第 69–70 行：从 stack 的索引 1（即第二个元素）处移除一个元素，并打印被移除元素的值。
• 第 72–75 行：使用 for 循环打印 stack 中剩余的元素。通过 get() 方法按索引访问元素，并使用 println() 方法输出。

FastArrayStack：优化版 ArrayStack

ArrayStack 的大部分工作涉及数据的移动（由 add(i, x) 与 remove(i) 完成）和复制（由 resize() 完成）。在上述实现中，这些操作通过 for 循环完成。实际上，许多编程环境提供了专门用于高效复制和移动数据块的函数。在 C 语言中，有 memcpy(d, s, n) 与 memmove(d, s, n) 函数；在 C++ 中，有 std::copy(a0, a1, b) 算法；在 Java 中，有 System.arraycopy(s, i, d, j, n) 方法。

1void resize() {
2  T[] b = newArray(max(2 * n, 1));
3  System.arraycopy(a, 0, b, 0, n);
4  a = b;
5}
6
7void add(int i, T x) {
8  if (n + 1 > a.length) resize();
9  System.arraycopy(a, i, a, i + 1, n - i);
10  a[i] = x;
11  n++;
12}
13
14T remove(int i) {
15  T x = a[i];
16  System.arraycopy(a, i + 1, a, i, n - i - 1);
17  n--;
18  if (a.length >= 3 * n) resize();
19  return x;
20}

这些函数通常高度优化，甚至可能使用特殊的机器指令，使复制速度远超手动 for 循环。尽管使用这些函数不会在渐近意义上降低运行时间，但仍是一种值得的优化。

在本示例的 Java 实现中，使用原生的 System.arraycopy(s, i, d, j, n) 方法带来了 2 到 3 倍的速度提升，具体取决于所执行的操作类型。实际效果可能因情况而异。