第03章 表、栈与队列：线性结构三件套

这一篇在干嘛？

表（list）、栈（stack）、队列（queue）是所有数据结构的”原子零件”。本章先讲清两个底层实现路线——数组与链表各自的代价，再亲手实现一遍 STL 的 vector 和 list，最后用栈解决表达式求值、用环形数组实现队列。后面章节的树、哈希、图全都建立在这一章的语汇上。

3.1 抽象数据类型（ADT）：先谈”能干什么”，再谈”怎么干”

ADT（Abstract Data Type）= 一组操作的集合 + 数据的数学定义，不涉及实现。比如”表”这个 ADT 只说：有一串元素 A₁…Aₙ，能取后继、能插入、能删除。

白话：ADT 是”接口合同”。C++ 里 list<int> 的使用者不需要知道内部是链表还是数组——这层隔离让同一份使用代码可以随时换实现。这是全书的方法论起点：先定义 ADT，再比较不同实现的代价。

3.2 表：数组实现 vs 链表实现

对”一般形式的表”，两个经典实现路线代价互补：

操作	简单数组	链表
按下标访问 findKth(k)	$O(1)$	$O(k)$，从头走
在位置 p 插入/删除	$O(N)$（后面全部平移）	$O(1)$（改两个指针）

白话：数组像一排连座电影院——找第 k 个座位瞬间到达，但中间插人要全体后移；链像寻宝游戏——每张纸条指向下一张，中间插一张新纸条只需改写两条”线索”，但想直接去第 1000 站就得走 999 步。频繁随机访问选数组，频繁中间插删选链表。

3.3 STL 的 vector 与 list：迭代器是桥

C++ 标准库给了两个现成品：vector（动态数组）和 list（双链表）。两者统一通过**迭代器（iterator）**访问——迭代器是”泛化的指针”，指向容器中一个位置，支持 *it 解引用、++it 前进：

vector<int> v{10, 20, 30};
auto itr = v.begin();        // 指向第一个元素的迭代器
cout << *itr;                // 解引用：10
v.insert(itr, 5);            // 在迭代器位置前插入
auto itr2 = v.begin();
v.erase(itr2);               // 删除迭代器指向的元素
for (auto it = v.begin(); it != v.end(); ++it)
    cout << *it << " ";

白话：不管容器内部长什么样，“begin 到 end 逐个前进”都成立——这就是迭代器模式的价值。常用操作里 insert(it, x) 和 erase(it) 都以迭代器为坐标，list 的这两个操作是 $O(1)$（拿到位置就能改指针），vector 的则是 $O(N)$（要平移元素）。

一个必须记住的坑：对 vector 做 insert/erase 后，之前拿到的迭代器全部失效；对 list，只有被删元素自己的迭代器失效。经典错误是”边遍历边删除”，正确姿势是用 erase 的返回值（指向被删元素的下一个）接续遍历。另外，用 range-for 遍历时对容器做结构性修改是未定义行为。

3.4 亲手实现 vector：扩容是灵魂

vector 的三个数据成员：theSize（元素个数）、theCapacity（底层数组容量）、objects（指向数组的指针）。所有操作里最核心的是 push_back：

void push_back(const Object &x) {
    if (theSize == theCapacity)          // 装满了
        reserve(2 * theCapacity + 1);    // 容量翻倍（+1 防初始为 0）
    objects[theSize++] = x;
}
 
void reserve(int newCapacity) {
    if (newCapacity < theSize)
        return;                          // 不允许缩到比 size 还小
    Object *newArray = new Object[newCapacity];
    for (int k = 0; k < theSize; ++k)
        newArray[k] = std::move(objects[k]);   // 搬家：移动而非拷贝
    theCapacity = newCapacity;
    std::swap(objects, newArray);
    delete[] newArray;
}

白话：满了不逐个让位，而是直接换一块双倍大的房子，把旧指针全部搬过去。搬一次家要 $O(N)$，但 N 次 push_back 只会触发 $O(\log N)$ 次搬家，摊还下来每次 push_back 平均 $O(1)$（摊还分析的系统化版本在第 11 章）。这就是”动态数组能当无限数组用”的秘密。

3.5 亲手实现 list：带头尾节点的双链表

STL list 的实现要点：表头表尾各放一个不存数据的哨兵节点（header/tail node），空表也有这两个节点：

白话：哨兵是”永远存在的边界桩”。有了它，插入/删除第一个、最后一个元素时不需要特判——任何位置的节点都有前驱和后继，代码只剩一种情形。这是用一两个多余节点换来代码正确性的经典交易。

链表版 erase 一行核心（节点已定位时）：

iterator erase(iterator itr) {
    Node *p = itr.current;
    iterator retVal(p->next);
    p->prev->next = p->next;    // 前驱跳过 p
    p->next->prev = p->prev;    // 后继回链跳过 p
    delete p;
    --theSize;
    return retVal;
}

白话：双向链表删除 = 让左右邻居”手拉手”绕过自己，然后自己退场。定位后 $O(1)$；贵在定位（$O(N)$）——所以 list 的高效用法是”拿着迭代器原地连续操作”，而不是反复 list[k]。

3.6 栈：只碰顶端的表

栈（stack）= 插入和删除只在同一端（栈顶）进行的表，操作叫 push（入栈）、pop（出栈）、top（看栈顶）。后进先出（LIFO, Last In First Out）：

白话：栈像叠盘子——放和取都只动最上面那个。实现可以是链表（顶=表头，push/pop 均 $O(1)$）或数组（顶=末尾，均 $O(1)$）。所有操作都 $O(1)$，没有权衡，选哪个纯粹看习惯。第 1 章的 printOut 递归”倒着打印数字”，本质上就是系统调用栈替你 push 了每一位。

栈的应用一：括号平衡

逐字符扫描，开括号 ( [ { 入栈；遇闭括号时栈顶必须是对应的开括号，匹配则弹栈，否则非法。扫描结束时栈必须为空。

白话：每个闭括号要找”最近的未匹配开括号”配对——“最近未匹配”正是栈顶的定义。

栈的应用二：后缀（逆波兰）表达式求值

中缀 a + b * c 有优先级和括号困扰；后缀 a b c * + 完全不需要括号。求值只需一个栈：操作数入栈；遇运算符弹两个数（先弹的是右操作数！），计算后压回。扫描结束栈里剩下的唯一元素就是答案。

例：6 5 2 3 + 8 * + 3 + * 的求值过程：读到 + 时弹 2、3 得 5；读到 * 时弹 8、5 得 40……最终栈剩 288。每个记号处理 $O(1)$，整体线性。

栈的应用三：中缀转后缀

把 a + b * c + (d * e + f) * g 转成后缀 a b c * + d e * f + g * +，规则两条：

• 操作数直接输出。
• 运算符入栈前，先弹出栈顶所有”优先级 ≥ 自己”的运算符输出（左结合）；( 压栈作为保护罩，遇到 ) 时弹到 ( 为止、双括号丢弃。

白话：栈里存的运算符都在”等一个更晚出现的右操作数”；新运算符优先级不比栈顶高，说明栈顶的”该算了”，于是依次出栈输出。

3.7 队列：两端各管一边的表

队列（queue）= 一端入队（enqueue/back）、另一端出队（dequeue/front）的表，先进先出（FIFO）。

数组实现的关键是环形（circular array）：front 和 back 两个下标一路右移会把数组左半浪费掉，所以到末尾就绕回开头（下标 +1 后对数组容量取模）。为区分”空”与”满”，通常保留一个空位或用 size 计数。入队、出队都是 $O(1)$。

白话：队列像排队买票——新来的从队尾排，服务完从队头走。环形数组把队伍”卷成圈”，出队空出来的位置能立刻被新元素复用，不用整体搬家。

典型应用：操作系统任务调度、打印队列、BFS（第 9 章图的广度优先搜索）。

常见坑

① 边遍历边删除：erase 之后继续用旧迭代器，vector 场景直接未定义行为——正确做法是 it = c.erase(it);。② 中缀转后缀时弹错顺序：求值时先弹的是右操作数，a b - 弹出来先 b 后 a，写反了减法除法全错。③ 链表插入先断后接：先改 prev->next 就丢了后继——永远先把新节点的两条链接好，再改邻居。

通关标准

学完本篇你应该能做到：① 给定操作序列，说清数组/链表各自代价并选型；② 解释 vector 扩容的摊还 $O(1)$ 原理；③ 画出带头尾节点双链表的插入删除指针变化；④ 手写括号平衡、后缀求值，并把简单中缀式转成后缀；⑤ 说清环形数组队列如何区分空与满。

为什么 list 的 insert/erase 拿到迭代器后是 O(1)，而 vector 不是？

list 节点在内存中独立，插入删除只需改常数个指针；vector 是连续内存，插入删除要平移其后所有元素，且扩容搬家会让迭代器整体失效。

vector 扩容为什么要按倍数（如 2 倍）增长，每次只加一个不行吗？

每次加 1：N 次 push_back 搬家总代价 $1+2+\cdots +N=O(N^2)$，摊还每次 $O(N)$。按倍数增长：搬家总代价是几何级数 $1+2+4+\cdots +N/2<N$，摊还每次 $O(1)$。

双链表为什么要有 header 和 tail 哨兵节点？

让任何真实节点的插入/删除都有统一的前驱后继可改，免去”是不是第一个/最后一个”的特判分支，代码更短也更不容易错。

后缀表达式为什么不需要括号？

后缀把”先算谁”编码进了记号顺序本身：运算符一出现，它的两个操作数（已算完的结果）必然已在栈顶，运算顺序是唯一确定的，不再依赖优先级和括号。

环形数组实现的队列怎么判断"空"和"满"？

front back 既可能是空也可能是满，需要打破对称：常见做法是保留一个元素位不放（满：`(back+1)%cap front`），或者额外维护一个 size 计数器（最直观）。