序列、栈、队列、树与堆

接口语义先于存储形状

抽象数据类型规定“能做什么”和“结果意味着什么”，具体实现规定“如何存”。例如栈接口要求最后压入的元素最先弹出，但可以用动态数组或链表实现。接口不应承诺内存连续，也不应暴露内部节点。

每个实现还需要表示不变量。动态数组要求逻辑长度不超过容量，前 $n$ 个槽恰好存放序列元素；链表要求头指针沿 next 最终到达空节点且没有意外环；二叉搜索树要求每个子树的键满足顺序政策；堆要求父节点优先级不劣于子节点。操作只有在开始时假设不变量、结束时恢复不变量，后续接口才可信。

成本模型要说明计数单位。本章用随机访问、比较、指针跟随和元素移动等基本操作的渐近数量描述时间，用额外槽或节点数量描述空间。大 $O$ 给增长上界，不是某台机器的秒数；缓存和分配器会影响实测，但不改变接口正确性。

表示不变量也是定位错误的工具。可以在每个公开操作前写清前置条件，在返回前检查逻辑长度、首尾引用、父子次序和容量关系。以队列为例，空队列应同时满足长度为零与首尾状态一致；入队后长度增加一，原有元素相对顺序不变；出队只移除最早元素。随机操作序列测试可把实现结果同一个简单参考模型逐步比较，并在每一步检查不变量。这样的检查不能替代复杂度证明，却能把“返回值偶然正确”和“内部状态可继续安全使用”区分开。分析成本时还要计入为恢复不变量而发生的移动、旋转或交换，不能只数接口表面的一次调用。

动态数组与链表

动态数组把序列元素放在可按索引定位的连续逻辑区域。已知索引访问通常为 $O(1)$；在中间插入或删除需要移动后缀，最坏为 $O(n)$。容量满时申请更大区域并复制已有元素，单次扩容是 $O(n)$，但若容量按固定大于 1 的比例增长，连续末尾追加的总复制次数形成几何级数，所以每次追加的摊还成本为 $O(1)$。摊还不表示每次都快，某一次仍可能触发复制。

单向链表节点保存值和后继引用。给定头节点寻找第 $i$ 个元素需要沿链前进，成本 $O(i)$；若已持有待插位置的前驱节点，插入可改常数个引用，成本 $O(1)$。只给一个键而没有节点引用时，仍要先线性搜索。双向链表增加前驱引用，使已知节点删除和反向移动方便，但占用更多引用并增加维护不变量。

链表不是自动优于数组。顺序遍历时数组通常具有更简单的地址模式，链表则需要跟随引用；但这些常数和硬件效果必须测量。本章能可靠承诺的是渐近操作数和表示语义。

栈与队列是操作顺序契约

栈遵循后进先出：push 加入顶部，pop 删除并返回顶部，peek 只查看。队列遵循先进先出：enqueue 在尾部加入，dequeue 从头部删除。两者对空结构操作都要定义失败，不能随意返回一个可能与合法元素冲突的特殊值。

用动态数组实现栈时，末尾 push 具有摊还 $O(1)$，末尾 pop 为 $O(1)$。队列若每次从数组头删除会移动全部剩余元素；可用环形缓冲区维护 head、tail 和 size，使入队出队为 $O(1)$。环形实现的不变量要区分空与满，单靠 head 等于 tail 不够时需额外长度或保留空槽。

def brackets_balanced(text):
    opening = {"(": ")", "[": "]", "{": "}"}
    stack = []

    for position, symbol in enumerate(text):
        if symbol in opening:
            stack.append((symbol, position))
        elif symbol in opening.values():
            if len(stack) == 0:
                return Failure("closing bracket without opener", position)
            left, left_position = stack.pop()
            if opening[left] != symbol:
                return Failure("mismatched bracket", position)

    if len(stack) != 0:
        left, position = stack[-1]
        return Failure("unclosed bracket", position)
    return Success()

队列常用于按到达次序或按层处理对象。图的广度优先遍历会把新发现顶点入队，并按发现顺序出队；若误用栈，就会得到深度优先式顺序，算法性质随之改变。

二叉树与递归遍历

二叉树节点至多有 left、right 两个孩子。树是递归结构：空树是基本情形，非空树由根和两个子树组成。遍历也自然递归：

def inorder(node, visit):
    if node is None:
        return
    inorder(node.left, visit)
    visit(node.value)
    inorder(node.right, visit)

前序在子树前访问根，后序在子树后访问根，中序把根放在左右子树之间。每个节点只访问一次，时间 $\Theta(n)$；递归调用栈深度等于树高 $h$，额外空间 $O(h)$。退化链会有 $h=n$，不仅搜索慢，也可能超过递归深度或内存边界。显式栈可避免语言调用栈限制，但仍需 $O(h)$ 状态。

二叉搜索树与平衡必要性

设键互异，二叉搜索树不变量为：任一节点左子树键都小于该键，右子树键都大于该键。若允许重复，必须另定“计数存在节点内”或“相等总去一侧”的政策，并让插入、搜索和删除一致。

搜索从根开始，每次比较后只进入一个子树，成本 $O(h)$。插入先按同一路径找到空位置，再接入叶节点。删除有三种情况：无孩子直接移除；一个孩子让父节点绕过它；两个孩子可用中序后继替换，再删除后继。每步都要恢复顺序不变量。

平衡搜索树通过旋转等局部变换把高度限制为 $O(\log n)$。旋转保持中序键序，却改变父子形状；具体 AVL、红黑或其他平衡政策是实现选择。映射接口只应承诺键值语义和经过证明的复杂度界，不要求调用者依赖某次旋转后的根键。

堆与优先队列

优先队列接口支持 insert、peek-min 和 extract-min。二叉最小堆用完全二叉树表示，并保持每个父键不大于孩子键。完全形状让它可紧凑存于数组；从零开始索引时，节点 $i$ 的孩子是 $2i+1,2i+2$，非根父节点是 $\lfloor(i-1)/2\rfloor$。

插入先放到数组末尾保持完全形状，再与父节点比较并上浮，最多经过树高 $O(\log n)$。取最小值直接读根，成本 $O(1)$。删除最小值时用末元素填根，再与较小孩子交换并下沉，成本 $O(\log n)$。堆序只保证祖先不大于后代，不保证数组整体排序。

从 $n$ 个无序元素逐个插入建堆需 $O(n\log n)$ 上界；自底向上对所有内部节点下沉可在 $O(n)$ 完成，因为多数节点靠近叶部、下沉距离短。这个线性结论需要按各层节点数求和，不能只用“有 $n$ 个节点，每个都可能下沉 $\log n$”的松上界否定。

不要混淆接口、表示和用途

栈、队列与优先队列是抽象接口；数组、链表、树和堆是表示。一个动态数组可以实现序列或栈，链表可以实现队列，平衡搜索树和哈希表都能实现映射，但它们的顺序能力与成本不同。

选择时先列出操作频率、是否需要顺序、最坏界还是期望界、内存上限和失败行为。若算法需要反复取最小值，排序一次或使用堆哪个更好取决于后续插入次数；若只需一次最小值，线性扫描可能更简单。数据结构名称不能替代工作负载分析。

常见误区

练习：不变量与操作成本

知识连接与资源

• 编程与科学计算综合项目 提供容器、函数契约和边界处理。
• 计数原理 支持层数、节点和操作次数求和。
• 哈希表、图与并查集 将使用桶序列、遍历队列和树形集合。
• 分治、贪心与排序 将使用递归树、堆和优先选择。
• 数据结构与算法综合复习 汇总不变量、正确性和复杂度选择。

MIT OpenCourseWare 6.006 覆盖序列、树、堆和渐近分析，可用于核对本章接口、不变量与复杂度。本章不把语言容器的某个内部实现写成抽象数据类型的永久语义。