栈的数组实现

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$ 来记录实际存储的元素数量。这样，列表元素存储在 a[0], ..., a[n−1] 中，且始终满足 $\text{a.length} \ge n$。

1class ArrayStack(BaseList):
2    def __init__(self, iterable=[]):
3        self._initialize()
4        self.add_all(iterable)
5        
6    def _initialize(self):
7        self.a = new_array(1)
8        self.n = 0

基本操作

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

1class ArrayStack(BaseList):
2    def __init__(self, iterable=[]):
3        self._initialize()
4        self.add_all(iterable)
5        
6    def _initialize(self):
7        self.a = new_array(1)
8        self.n = 0
9
10    def get(self, i):
11        if i < 0 or i >= self.n: raise IndexError()
12        return self.a[i]
13
14    def set(self, i, x):
15        if i < 0 or i >= self.n: raise IndexError()
16        y = self.a[i]
17        self.a[i] = x
18        return y

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$。

1class ArrayStack(BaseList):
2    def __init__(self, iterable=[]):
3        self._initialize()
4        self.add_all(iterable) 
5    def add(self, i, x): 
6        if i < 0 or i > self.n: raise IndexError()
7        if self.n == len(self.a): self._resize()
8        self.a[i+1:self.n+1] = self.a[i:self.n]
9        self.a[i] = x
10        self.n += 1

忽略可能调用 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() 缩小数组大小。

1class ArrayStack(BaseList):
2    def __init__(self, iterable=[]):
3        self._initialize()
4        self.add_all(iterable) 
5    def remove(self, i): 
6        if i < 0 or i >= self.n: raise IndexError()
7        x = self.a[i]
8        self.a[i:self.n-1] = self.a[i+1:self.n]
9        self.n -= 1
10        if len(self.a) >= 3*self.n: self._resize()
11        return x

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

扩容与缩容

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

1class ArrayStack(BaseList):
2    def __init__(self, iterable=[]):
3        self._initialize()
4        self.add_all(iterable) 
5    def _resize(self):
6        b = new_array(max(1, 2*self.n))
7        b[0:self.n] = self.a[0:self.n]
8        self.a = b

分析 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$ 的大小为 $\text{a.length}$，但其中存储的元素数量最多为 $\text{a.length}/2 = n_i/2$。而现在 $a$ 中的元素数量为 $n_i = \text{a.length}$，因此自上次调用 resize() 以来，至少有 $n_i / 2$ 次 add(i, x) 操作。

• 情况二：resize() 由 remove(i) 调用，因为 $\text{a.length} \ge 3n = 3n_i$。同样，上一次调用 resize() 后，$a$ 中存储的元素数量至少为 $\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(i, x) 或 remove(i) 的调用次数至少为 $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)$。

1from utils import new_array
2from base import BaseList
3
4class ArrayStack(BaseList):
5    def __init__(self, iterable=[]):
6        self._initialize()
7        self.add_all(iterable)
8    # 初始化函数
9    def _initialize(self):
10        self.a = new_array(1)
11        self.n = 0
12    # 获取值的函数
13    def get(self, i):
14        if i < 0 or i >= self.n: raise IndexError()
15        return self.a[i]
16    # 设置值的函数
17    def set(self, i, x):
18        if i < 0 or i >= self.n: raise IndexError()
19        y = self.a[i]
20        self.a[i] = x
21        return y
22    # 向 arraystack 添加值的函数
23    def add(self, i, x): 
24        if i < 0 or i > self.n: raise IndexError()
25        if self.n == len(self.a): self._resize()
26        self.a[i+1:self.n+1] = self.a[i:self.n]
27        self.a[i] = x
28        self.n += 1
29    # 从 arraystack 移除值的函数
30    def remove(self, i): 
31        if i < 0 or i >= self.n: raise IndexError()
32        x = self.a[i]
33        self.a[i:self.n-1] = self.a[i+1:self.n]
34        self.n -= 1
35        if len(self.a) >= 3*self.n: self._resize()
36        return x
37    # 调整 arraystack 大小的 resize 方法
38    def _resize(self):
39        b = new_array(max(1, 2*self.n))
40        b[0:self.n] = self.a[0:self.n]
41        self.a = b
42    
43if __name__ == "__main__":
44    # 对象创建
45    stack = ArrayStack()
46    # 添加值
47    stack.add(0, 1)
48    stack.add(1, 2)
49    stack.add(2, 3)
50    print("栈大小: ", stack.size())
51    # 移除值
52    removed_element = stack.remove(1)
53    print("移除的元素: ", removed_element)
54    # 更新后的栈
55    print("栈中的元素:")
56    for i in range(stack.size()):
57        print(stack.get(i))

说明

让我们从 main.py 文件中的 main() 函数开始解释：

• 第45行：创建一个用于存储整数的 ArrayStack 对象 stack。
• 第47–49行：向 stack 中添加三个元素。add() 方法的第一个参数是插入位置的索引，第二个参数是元素的值。
• 第50行：使用 size() 方法打印当前栈的大小。
• 第52–53行：从索引 1（即第二个元素）处移除一个元素，并打印被移除元素的值。
• 第55–57行：使用 for 循环遍历并打印栈中剩余的元素。通过 get() 方法按索引访问元素，并使用 print() 输出。

FastArrayStack：优化版 ArrayStack

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

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

在我们的 C++ 和 Java 实现中，使用快速数组复制函数带来了 2 到 3 倍的速度提升，具体取决于操作类型。实际效果可能因环境而异。