第3章 Lists, Stacks, and Queues：线性结构的接口与表示

从“List 不是 linked list”开始

abstract data types（）先回答“调用者能做什么”。representation 才回答“怎样存”。把 List ADT 直接等同 linked list，会把一种实现误当接口本身；连续 vector 同样可以实现 sequence。

先预测一个日志 buffer：需要按下标读取、主要尾部追加、很少在中间插入。linked list 的中间 insert 若已有 iterator 是 O(1)，却要为每个节点分配内存，随机下标是 O(N)，遍历还伴随 pointer chasing；vector 偶尔扩容 O(N)，但顺序读和尾插通常更快。选择数据结构必须看完整 operation mix。

官方目录的七节是 Abstract Data Types (ADTs)、The List ADT、vector and list in the STL、Implementation of vector、Implementation of list、The Stack ADT、The Queue ADT。本章沿这个顺序，从语义走到两种表示，再由受限 ADT 检查是否真正理解了接口。

3.1 Abstract Data Types (ADTs)

一个 ADT 由 objects 与 operations 定义。List 的 objects 是有序元素序列，常见 operations 包括 size、find、insert、erase；Stack 只暴露一端；Queue 从一端进入、另一端离开。ADT 的正确性不依赖 C++ class，但 class 可以把 contract 与 private state 绑定。

每个 operation 还要写：

• precondition，例如 pop 需要非空；
• postcondition，例如 insert 后 size 增1且原相对次序保持；
• failure policy，例如抛 UnderflowException；
• complexity promise，例如 iterator 已知时 list erase 是 constant。

同一个 big-O 可能隐藏不同条件。“list insert O(1)”假设已经持有 insertion iterator；若先按下标走到第 i 个节点，定位仍是 O(i)。

3.2 The List ADT

List ADT（）的核心不变量是 logical order。array representation 用 index 表位置；linked representation 用 node/iterator 表位置。

对 sequence [a,b,c]，在 b 前 insert x 后必须得到 [a,x,b,c]；erase b 后其他元素顺序不变。随机 access、iterator stability、insert cost 和 memory overhead 由 representation 决定，不属于抽象序列本身。

iterator 把 traversal position 封装成可复制对象。begin() 指向首元素，end() 是 one-past-the-end marker，不能 dereference；half-open range [begin,end) 允许空序列自然满足 begin==end。

3.3 vector and list in the STL

STL中的vector与list（）有共同接口，却有不同 guarantee。

STL algorithm 通过 iterator category 工作。vector iterator 支持 random access，list iterator 只 bidirectional；对 list 调 std::advance 前进 k 步仍要 O(k)。泛型接口相同不代表 capability 与 cost 相同。

3.4 Implementation of vector

vector实现（）维护三个核心字段：theSize、theCapacity、objects。始终满足：

1. 0 ≤ theSize ≤ theCapacity；
2. [0,theSize) 是已使用元素；
3. [theSize,theCapacity) 是 spare storage；
4. objects 拥有一段 capacity 大小的数组。

官方第3版 push_back 在满容量时调用 reserve(2 * theCapacity + 1)，随后写入新元素：

void push_back(const Object& x) {
    if (theSize == theCapacity)
        reserve(2 * theCapacity + 1);
    objects[theSize++] = x;
}

一次 reallocation 要分配新数组、复制 size 个元素、释放旧数组，因此 worst case O(N)。但 capacity 倍增后，在下一次扩容前可完成约 N 次 constant pushes。N 次 push 的总复制量是几何级数，小于2N，所以 amortized O(1)。

reserve 改 capacity 而不凭空增加 logical elements；resize 改 size，必要时先扩 capacity。把两者混用会让未构造/无效元素进入可见范围。

void reserve(int newCapacity) {
    if (newCapacity <= theCapacity) return;
    Object* old = objects;
    objects = new Object[newCapacity];
    for (int i = 0; i < theSize; ++i)
        objects[i] = old[i];
    theCapacity = newCapacity;
    delete[] old;
}

第3版教学代码手写 Big Three；现代 std::vector 还处理 allocator、move、exception guarantee 和 element destruction。教学实现的价值是暴露 size/capacity 与 invalidation 的因果关系，不应当直接替代标准库。

3.5 Implementation of list

list实现（）为每个 node 保存 data、prev、next。head/tail 不保存业务元素，空表也始终有：

head.next == tail
tail.prev == head
size == 0

在 iterator itr 指向的节点 p 前插入 x，只需创建一个 node 并改四条 links：

iterator insert(iterator itr, const Object& x) {
    Node* p = itr.current;
    ++theSize;
    return iterator(
        p->prev = p->prev->next = new Node(x, p->prev, p)
    );
}
 
iterator erase(iterator itr) {
    Node* p = itr.current;
    iterator next(p->next);
    p->prev->next = p->next;
    p->next->prev = p->prev;
    delete p;
    --theSize;
    return next;
}

返回 successor iterator 让 range erase 能写成 itr = erase(itr)，避免递增已经失效的 iterator。clear 反复 pop_front，destructor 再 delete 两个 sentinels；copy assignment 先 clear，再逐个 push_back，保证目标与源节点独立。

3.6 The Stack ADT

Stack ADT（）暴露 push、pop、top、empty。限制接口是优势：调用者不能随意访问中间元素，representation 可由 vector back 或 list end 实现。

典型应用包括 function call stack、balanced delimiters、infix-to-postfix conversion、postfix evaluation 和 undo history。对 postfix 3 4 + 2 *：

1. 数字压栈；
2. 运算符弹出右、左 operands；
3. 计算后结果压回；
4. 最终栈恰有一个值14。

operand 顺序不能反。对 subtraction/division，第一次 pop 是 rhs，第二次是 lhs。underflow 和最终剩余多个值都表示 expression malformed。

3.7 The Queue ADT

Queue ADT（）用于 event loop、BFS、producer/consumer buffer 和 scheduling。linked list 可在 tail insert、head erase；array 版本不能每次 dequeue 都左移全部元素，应使用 circular indices。

capacity 为 C 时，第 i 个逻辑元素位于 (front+i) mod C。保存 size 可区分 empty 与 full；另一种方案牺牲一个 slot，用 front==back 表 empty。两种都行，但 invariants 与 tests 必须一致。

void enqueue(const Object& x) {
    if (size == capacity) grow();
    data[(front + size) % capacity] = x;
    ++size;
}
 
void dequeue() {
    if (size == 0) throw UnderflowException{};
    front = (front + 1) % capacity;
    --size;
}

从操作组合选择表示

本章回顾

1. ADT 规定对象与操作语义，representation 决定布局和成本。
2. List 是有序 sequence 抽象，不等于 linked list。
3. vector 连续且支持 O(1) indexing，list 用节点换取已知位置 O(1) relink。
4. vector 以 size/capacity 分离和倍增扩容实现 amortized O(1) push_back。
5. list 的 head/tail sentinels 消除首尾特判，erase 返回 successor iterator。
6. iterator stability 是容器契约的一部分，不能把 iterator 当永久 pointer。
7. Stack 限制为 LIFO，Queue 限制为 FIFO；限制接口让不变量更强。
8. ring buffer 用 modulo 复用数组空间，避免 dequeue 搬移所有元素。

名词解释