栈的数组实现

ArrayStack 概述

List 和 Queue 接口可以通过将底层数据存储在数组中来实现，这个数组被称为后备数组。下表总结了这些数据结构的操作运行时间：

优点与局限性

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

• 数组支持对任意位置元素的常数时间访问。这使得 get(i) 和 set(i, x) 能够在常数时间内完成。

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

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

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

在本模块及整个课程中，使用能够跟踪自身大小的数组会非常方便。标准 C++ 数组不具备这一功能，因此我们定义了一个名为 array 的类，用于维护其长度。该类的实现很简单：它由一个标准 C++ 数组 a 和一个整型变量 length 组成：

1T *a;
2int length;

数组的大小在创建时指定：

1array(int len) {
2  length = len;
3  a = new T[length];
4}

数组元素可通过索引访问：

1T& operator[](int i) {
2   assert(i >= 0 && i < length);
3   return a[i];
4}

当一个数组被赋值给另一个数组时，只需进行指针操作，耗时为常数：

1 array<T>& operator=(array<T> &b) {
2   if (a != NULL) delete[] a;
3   a = b.a;
4   b.a = NULL;
5   length = b.length;
6   return *this;
7 }

ArrayStack：使用数组实现高效的栈操作

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

1 array<T> a;
2 int n;
3 int size() {
4return n; }

基础操作

通过 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() 后，可以确保 a.length > n。之后，将元素 a[i], ..., 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) 操作的实现类似。我们将元素 a[i+1], ..., 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   array<T> b(max(2 * n, 1));
3   for (int i = 0; i < n; i++)
4     b[i] = a[i];
5   a = b;
6}

分析 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() 调用：那次调用后，数组大小为 $\text{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$ 次调用之间，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)$。

1#include "ArrayStack.h"
2
3#include "utils.h"
4
5
6namespace ods {
7
8    template ArrayStack < int > ::ArrayStack();
9    template ArrayStack < int > ::~ArrayStack();
10    template void ArrayStack < int > ::add(int, int);
11    template int ArrayStack < int > ::remove(int);
12
13    template ArrayStack < int * > ::ArrayStack();
14    template ArrayStack < int * > ::~ArrayStack();
15    template void ArrayStack < int * > ::add(int, int * );
16    template int * ArrayStack < int * > ::remove(int);
17
18} /* namespace ods */

说明

让我们从 main.cpp 文件中 main() 函数的开头开始解释。

• 第 126 行：此行将整型变量 n 初始化为 100000。

• 第 127 行：此行将字符串 ArrayStack<int> 输出到控制台，前后均带有换行符 endl。

• 第 128 行：此行创建了一个 ArrayStack 类的实例，并使用默认构造函数初始化。尖括号内的 int 指定了栈所存储的元素类型（此处为整数）。

• 第 129 行：此行调用名为 listTests() 的函数，并传入三个参数：as（刚刚创建的 ArrayStack 实例）、n（之前初始化的整型变量）以及 RA（作为 listTests() 函数的标志位）。

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) 算法，以及 std::copy_backward(a0, a1, b) 方法。

1void resize() {
2   array<T> b(max(1, 2*n));
3   std::copy(a+0, a+n, b+0);
4   a = b;
5 }
6 void add(int i, T x) {
7   if (n + 1 > a.length) resize();
8   std::copy_backward(a+i, a+n, a+n+1);
9   a[i] = x;
10  n++; 
11  }

这些函数通常高度优化，甚至可能使用特殊的机器指令，使复制速度远超手动编写 for 循环。尽管使用这些函数不会改变渐近时间复杂度，但仍是一种值得采纳的优化手段。

在本课程的 C++ 实现中，使用原生 std::copy(a0, a1, b) 使性能提升了 2 到 3 倍，具体提升幅度取决于操作类型。实际效果可能因环境而异。