数组是最基础、也最常用的数据结构之一。它把一组元素按照顺序存放，并允许程序通过下标快速找到其中任意一个元素。
原书中的底层例子主要使用 C 语言。本文改用 Python 来讲解：Python 没有暴露固定长度数组的全部细节，但它的 list 在算法分析上可以看作一种动态数组。理解这层关系后，就能同时读懂 Python 的使用方式和数组背后的原理。
数组的核心取舍是：随机访问很快，但中间插入和删除通常需要移动后面的元素。
1. 数组的基本模型
假设有一个包含 5 个整数的数组：
下标： 0 1 2 3 4
数据： 12 7 25 3 18
第 i 个元素可以通过 a[i] 访问。因为数组元素按顺序存放，程序可以根据起始位置和下标计算出目标位置：
元素位置 = 起始位置 + i × 单个元素占用的空间
所以，访问任意位置都不需要从头查找，时间复杂度通常是：
O(1)
这里的 O(1) 表示操作次数不会随着数组长度 n 的增长而增长。
2. Python 中的数组：list 和 array
2.1 Python 的 list
最常用的数组式容器是 list：
scores = [12, 7, 25, 3, 18]
print(scores[2]) # 25
scores[2] = 100
print(scores) # [12, 7, 100, 3, 18]
Python 的下标同样从 0 开始，最后一个元素的下标是 len(scores) - 1。
for score in scores:
print(score)
和 C 语言固定类型数组不同，Python 的 list 可以保存不同类型的对象：
values = [10, "hello", 3.14, True]
不过在算法分析中，通常假设列表中的元素具有相同的逻辑类型，这样才能清楚地讨论排序、搜索和比较。
2.2 同类型数组：array.array
如果确实需要保存同一种基础数值类型，可以使用标准库中的 array：
from array import array
scores = array("i", [12, 7, 25, 3, 18])
print(scores[2]) # 25
日常编程中，list 更常用、更灵活；array.array 更接近“同类型数组”的概念。本文后面的示例主要使用 list，因为它更适合展示 Python 中常见的数据结构操作。
2.3 二维数组
二维数组可以表示表格或矩阵：
matrix = [
[1, 2, 3],
[4, 5, 6],
]
print(matrix[1][2]) # 6
for row in matrix:
for value in row:
print(value, end=" ")
print()
如果矩阵有 n 行、n 列，完整遍历需要访问 n² 个元素，因此复杂度是 O(n²)。
3. 数组的基本操作和复杂度
以下复杂度以 Python list 为例：
| 操作 | 典型复杂度 | 原因 |
|---|---|---|
| 按下标读取 | O(1) |
可以直接定位 |
| 按下标修改 | O(1) |
可以直接定位 |
len(data) |
O(1) |
列表保存了长度信息 |
| 线性搜索 | O(n) |
可能要逐个检查 |
| 有序列表二分搜索 | O(log n) |
每次排除一半范围 |
末尾 append |
摊销 O(1) |
列表会预留部分空间 |
中间 insert |
O(n) |
后面的元素需要后移 |
末尾 pop() |
摊销 O(1) |
只删除最后一个元素 |
开头 pop(0) |
O(n) |
后面的元素需要前移 |
| 整体遍历 | O(n) |
每个元素都要访问 |
“摊销 O(1)”的意思是：某一次扩容可能很慢，但连续进行很多次追加时，平均到每次操作上的成本仍然接近常数。
4. 在数组中插入元素
假设列表为：
12 7 25 3 18
现在要在下标 2 的位置插入 99。为了给新元素腾出位置，需要把后面的元素向右移动：
原来：12 7 25 3 18
移动：12 7 25 3 18
结果：12 7 99 25 3 18
Python 已经提供了现成的方法：
scores = [12, 7, 25, 3, 18]
scores.insert(2, 99)
print(scores) # [12, 7, 99, 25, 3, 18]
insert 很方便，但它隐藏了“后移元素”的过程。下面手动写一个版本：
def insert_at(data, position, value):
if not 0 <= position <= len(data):
raise IndexError("插入位置越界")
# 先增加一个空出的末尾位置
data.append(0)
# 从后往前移动，避免覆盖尚未移动的数据
for index in range(len(data) - 1, position, -1):
data[index] = data[index - 1]
data[position] = value
numbers = [12, 7, 25, 3, 18]
insert_at(numbers, 2, 99)
print(numbers) # [12, 7, 99, 25, 3, 18]
如果插入位置接近开头，可能需要移动大量元素，因此最坏复杂度是 O(n)。
5. 从数组中删除元素
删除下标 2 的元素后，需要把后面的元素向左移动：
原来：12 7 25 3 18
删除：12 7 3 18
结果：12 7 3 18
Python 可以直接使用 pop：
numbers = [12, 7, 25, 3, 18]
removed = numbers.pop(2)
print(removed) # 25
print(numbers) # [12, 7, 3, 18]
为了看清移动过程，可以手动实现：
def remove_at(data, position):
if not 0 <= position < len(data):
raise IndexError("删除位置越界")
removed = data[position]
for index in range(position, len(data) - 1):
data[index] = data[index + 1]
data.pop()
return removed
numbers = [12, 7, 25, 3, 18]
print(remove_at(numbers, 2)) # 25
print(numbers) # [12, 7, 3, 18]
如果不要求保持元素顺序，可以用最后一个元素覆盖被删除的位置：
def remove_unordered(data, position):
if not 0 <= position < len(data):
raise IndexError("删除位置越界")
removed = data[position]
data[position] = data[-1]
data.pop()
return removed
numbers = [12, 7, 25, 3, 18]
remove_unordered(numbers, 1)
print(numbers) # [12, 18, 25, 3]
这种做法可以把删除降为 O(1)，但会改变元素顺序。复杂度分析必须先确认：程序是否要求保持顺序。
6. 线性搜索与二分搜索
6.1 线性搜索
线性搜索从头到尾检查列表：
def linear_search(data, target):
for index, value in enumerate(data):
if value == target:
return index
return -1
print(linear_search([12, 7, 25, 3, 18], 25)) # 2
最好情况是第一个元素匹配，为 O(1)；最坏情况需要检查全部元素，为 O(n)。
6.2 二分搜索
如果列表已经按升序排列，可以每次检查中间元素：
1 4 7 12 18 25 31 40
↑
根据比较结果，可以排除左半部分或右半部分：
def binary_search(data, target):
left = 0
right = len(data) - 1
while left <= right:
middle = (left + right) // 2
if data[middle] == target:
return middle
if data[middle] < target:
left = middle + 1
else:
right = middle - 1
return -1
numbers = [1, 4, 7, 12, 18, 25, 31, 40]
print(binary_search(numbers, 25)) # 5
每一轮把搜索范围缩小一半，因此复杂度为 O(log n)。
二分搜索有两个前提：
- 数据已经有序；
- 可以快速访问中间位置。
如果为了保持有序，每次插入都要移动 O(n) 个元素，那么搜索很快，并不代表整体操作一定很快。
7. 动态数组和扩容
固定长度数组的容量在创建时确定。动态数组则允许在空间不足时扩容。
Python 的 list 会自动完成扩容，因此我们只需要不断追加：
items = []
for value in range(10):
items.append(value)
print(items)
底层通常会预留比当前元素数量更多的空间。当预留空间用完时，列表会申请更大的空间并复制旧元素：
容量：8 → 16 → 32 → 64 → ...
单次扩容可能复制 O(n) 个元素，但如果容量按倍数增长，连续追加 n 个元素的总成本可以摊销为 O(n)，平均每次追加接近 O(1)。
这就是动态数组的摊销复杂度：某一次操作可能很贵，但一长串操作的平均成本仍然很低。
8. 用列表实现栈
栈遵循后进先出（LIFO）：最后放入的元素最先取出。
push(10) → push(20) → pop() 得到 20
Python 列表的末尾追加和末尾删除都很适合实现栈：
stack = []
stack.append(10) # push
stack.append(20)
print(stack.pop()) # 20
print(stack.pop()) # 10
可以把它封装成一个简单的类：
class Stack:
def __init__(self):
self._items = []
def push(self, value):
self._items.append(value)
def pop(self):
if not self._items:
raise IndexError("栈为空")
return self._items.pop()
def is_empty(self):
return not self._items
只在列表末尾进行压入和弹出，所以 push 和 pop 都是摊销 O(1)。
栈可以用于：
- 函数调用和递归；
- 括号匹配；
- 深度优先搜索；
- 逆波兰表达式求值；
- 撤销操作。
9. 用数组思想实现队列
队列遵循先进先出（FIFO）：先进入的元素先离开。
不推荐用列表的 pop(0) 实现队列，因为它需要把后面的元素整体前移：
queue = [10, 20, 30]
first = queue.pop(0) # 结果是 10，但复杂度为 O(n)
通常应该使用 collections.deque：
from collections import deque
queue = deque([10, 20])
queue.append(30) # 入队
print(queue.popleft()) # 10，出队
print(queue) # deque([20, 30])
如果希望直接观察环形队列的实现，可以用列表保存固定容量的槽位：
class CircularQueue:
def __init__(self, capacity):
if capacity <= 0:
raise ValueError("容量必须大于 0")
self._data = [None] * capacity
self._front = 0
self._rear = 0
self._size = 0
def enqueue(self, value):
if self._size == len(self._data):
raise OverflowError("队列已满")
self._data[self._rear] = value
self._rear = (self._rear + 1) % len(self._data)
self._size += 1
def dequeue(self):
if self._size == 0:
raise IndexError("队列为空")
value = self._data[self._front]
self._data[self._front] = None
self._front = (self._front + 1) % len(self._data)
self._size -= 1
return value
def __len__(self):
return self._size
queue = CircularQueue(3)
queue.enqueue(10)
queue.enqueue(20)
print(queue.dequeue()) # 10
环形队列的入队和出队都是 O(1)，代价是容量固定。
10. 数组适合什么时候？
数组或 Python list 适合：
- 需要频繁按下标访问；
- 主要操作是遍历、读取和修改；
- 数据数量相对稳定，或可以接受自动扩容；
- 需要较好的缓存局部性；
- 希望结构简单、额外链接少；
- 需要用列表方便地实现栈。
数组不太适合：
- 经常在开头或中间插入和删除；
- 需要频繁从两端出队；
- 需要频繁合并、拆分数据；
- 数据本质上是复杂的层级关系。
11. 常见错误
负数下标带来的误解
Python 中 data[-1] 表示最后一个元素，这不是越界。写算法时，如果下标来自用户输入，最好先明确检查范围：
def get_at(data, index):
if not 0 <= index < len(data):
raise IndexError("下标越界")
return data[index]
二维列表的别名问题
下面的写法会让两行指向同一个列表：
wrong = [[0] * 3] * 2
wrong[0][0] = 1
print(wrong) # [[1, 0, 0], [1, 0, 0]]
应该为每一行分别创建列表：
right = [[0] * 3 for _ in range(2)]
right[0][0] = 1
print(right) # [[1, 0, 0], [0, 0, 0]]
用列表的头部模拟队列
pop(0) 和 insert(0, value) 都会移动大量元素。需要队列时，优先考虑 deque。
遍历时直接修改列表
在遍历列表的同时删除元素，容易跳过元素。可以先建立新列表，或倒序删除。
只看单次操作
一次扩容可能很慢，但 append 的长期平均成本仍然接近 O(1)。分析动态数组时，要区分最坏单次复杂度和摊销复杂度。
12. 栈应用：逆波兰表达式
后缀表达式 3 4 + 2 * 表示 (3+4)*2。读取数字时压栈；读二元运算符时先弹右操作数，再弹左操作数，计算后把结果压回。减法与除法不能交换两次弹出值的次序。
def evaluate_postfix(expression):
operators = {"+": lambda a, b: a+b, "-": lambda a, b: a-b,
"*": lambda a, b: a*b, "/": lambda a, b: a/b}
stack = []
for token in expression.split():
if token in operators:
if len(stack) < 2:
raise ValueError("操作数不足")
right = stack.pop()
left = stack.pop()
stack.append(operators[token](left, right))
else:
stack.append(float(token))
if len(stack) != 1:
raise ValueError("表达式未产生唯一结果")
return stack[0]
print(evaluate_postfix("3 4 + 2 *")) # 14.0
print(evaluate_postfix("10 3 -")) # 7.0
除数为零时 Python 抛出 ZeroDivisionError。该示例支持空格分隔的数字和四种二元运算，不处理变量、一元负号语法或括号；负数作为一个数字 token 可使用。
13. 环形队列的指针约定
本教材队列的 front 指向下一读取项，rear 指向下一写入槽，size 区分空与满。空时 size=0，满时 size=capacity。满队列和空队列都可能 front==rear，不能只检查两个指针是否相等。
原书还讨论保留一个空槽的方案：空满条件和有效容量会变化。使用前要确定是哪一种约定，不要把两套条件混用。
14. 小结
- 数组把元素按顺序存放，按下标访问通常是
O(1)； - Python
list可以看作一种自动扩容的动态数组； - 中间插入和删除通常是
O(n)； - 有序列表可以使用
O(log n)的二分搜索； append和末尾pop适合实现栈；- 队列不应使用
list.pop(0)，通常应使用deque； - 环形队列可以用固定数组槽位实现
O(1)的入队和出队； - 选择数组时，要重点考虑访问模式、插入位置和是否要求保持顺序。