1.1 ADT 操作：stack、queue 与 function pointer

动机

在 CSCI2520 中，最常见的问题往往不是少写一个分号，而是缺少清楚的 操作契约。

ADT 必须先说明四件事：

• 允许执行哪些操作，
• 每个操作保证什么结果，
• 客户端调用后可以依赖什么状态，
• 空结构和错误情况如何处理。

最后一项也是正确性的一部分。前置条件描述操作前必须成立的事实； 后置条件描述操作的返回值和完成后的抽象状态。如果前置条件可能不成立， 接口还必须规定可观察的失败策略。

这项分隔十分重要，因为同一个 stack 或 queue 接口可以由定长数组、 动态数组或链表实现。内部表示变化时，客户端代码不应随之改写。

抽象状态与失败原子性

抽象状态是客户端看到的数学值，例如由已存储元素组成的有限序列；数组 索引、容量和节点地址都不属于该值。mutator 应先检查前置条件并取得所需 资源，然后才一次提交表示变更。如果操作报告 overflow、underflow 或分配 失败，失败原子性要求旧抽象状态仍然可以完整观察。这条规则防止失败的插入 改变深度或长度，也防止删除操作在报告错误前丢失元素。

把程序与抽象状态精确连接的一种方法，是定义 abstraction function。它把 每个有效的具体表示映射到唯一抽象序列。representation invariant 说明哪些 具体状态有效；操作契约则说明映射后的序列可以如何改变。两者必须分开： 客户端有权依赖操作契约，却不会看到或修复内部 invariant。另一方面，实现 可以在操作期间重新组织存储，只要中间形式不会泄漏，而且最终具体状态会 映射到承诺的抽象结果。

失败原子性可以设计成一项短 transaction。首先在不改变状态的情况下检查 所有逻辑前置条件；然后计算新容量或 link 值，并拒绝算术 overflow；接着在 旧表示仍然完整时取得内存或其他资源；最后才把新 pointer、index、count 或 link 作为一次已提交转移公开。最后阶段前的失败应通过已声明 error channel 返回，让每个 observer 都得到旧答案。即使程序遇错就终止，这项规律仍使 局部推理更清楚，也支持以后改成可恢复接口。

Stack 是只能从顶端操作的结构

stack 的核心不是“一摞物体”这个比喻，而是只能从顶端访问的不变量。

以上是概念层面的操作。下方的课堂 header 并未公开 top；Tutorial 2 则把相应观察操作称为 Peek。采用哪一种均可，但公开接口必须前后一致。

LIFO 是 stack 的基本规则：后进先出。若用从底至顶的序列表示抽象状态 S，Push(S, x) 的后置条件是 S' = S · x。Pop(S) 的前置条件是 S != []；若 S = T · x，则操作返回 x，并令 S' = T。

完整的 stack 操作契约

构造操作返回已经初始化、深度为零的空状态。深度和空状态测试都是 observer： 它们要求有效的 stack handle，返回当前序列的信息，并保持序列不变。 顶端 observer 同样不改变状态，但要求序列非空。push 成功后只增加一个 最新元素；pop 只删除该元素。如果接口提供 clear，后置条件是序列为空， 并按照 ownership policy 释放表示所拥有的资源。这些语义后置条件都不指定 存储方式必须是数组还是节点链。

observer 必须幂等且不改变次序；top 不转移值或 pointee 的 ownership， 相关规则须另写入契约。push 与 pop 保持其余元素的次序和值。clear 释放 表示所拥有的资源后仍留下可复用的空 stack；destructor 才释放 stack 对象， 并使后续使用无效。

Stack 接口会隐藏内部表示

课堂里的 opaque type 形式是：

typedef struct stackCDT *stackADT;
typedef int stackElementT;

stackADT EmptyStack(void);
void Push(stackADT stack, stackElementT element);
stackElementT Pop(stackADT stack);
int StackDepth(stackADT stack);
int StackIsEmpty(stackADT stack);

这个设计不是装饰，而是保护契约。stackADT 只是指向不完整 struct 的指针，client 可以传递 stack，但不能直接访问其内部字段。

表示独立性只保证可观察行为一致，并不表示成本相同。定长数组、动态数组 和链表表示可以具有不同的隐藏容量、分配方式和运行时间；但如果一项实现 拒绝某次 push，另一项却接受，该成功或失败差异便是可观察的。只有当每次 调用结果一致，或共享抽象明确把容量及其失败策略参数化或排除在外时，它们 才满足这里的强表示独立性。复杂度界限只有写入契约后才能被客户端依赖。

表示不变量与成本模型

定长数组把具体的有效 prefix 对应到抽象序列，并保持 count 不超过容量。 动态数组还必须保证分配足以容纳容量以下的每个位置。linked stack 则要求 一条无环链，首节点表示抽象顶端；如果另存 count，它必须等于可达节点数。 定长数组的 push 和 pop 是常数时间，但受容量限制。动态增长偶尔需要复制 整个当前序列。链式操作不做整批复制，却需要分配或释放节点，而且 locality 不同。这些成本差异不会改变 LIFO 行为。

对定长数组而言，有效区域恰好是长度等于 count 的 prefix。prefix 以外的 位置可能仍有旧 bits，但它们不是抽象元素，observer 绝不能把它们返回。 push 在旧 prefix 后第一个位置写入，并且只在写入合法后增加 count。pop 减少逻辑长度并返回原来最后一个 prefix 值；是否清除该位置不影响语义， 因为缩短后的 count 已把它隐藏。可是在容量已满时，连第一次写入都必须 等待 overflow policy 选出安全结果后才能发生。

动态数组在相同 prefix relation 之外再加入容量关系。空 dynamic stack 可以 拥有小型分配，也可以采用 null pointer 配合零容量，但选定 convention 后 必须一致表示。增长改变存储身份，而不改变元素顺序。linked stack 使用 另一 simulation relation：从 top 沿 next link 行走，所得顺序是从底至顶 抽象序列的反向。push 安装一个新 head；pop 拆下一个旧 head。如果另存 depth，每次成功 link 变更都必须在同一次 commit 更新它；如果通过遍历计算 depth，成本就是线性而不是常数。两种选择仍可以满足完全相同的 observer 后置条件。

Stack 的实现方式

课堂幻灯片强调三个重要概念。

第一，定长数组版本用 count 记录深度：

struct stackCDT {
   stackElementT elements[100];
   int count;
};

它的表示不变量是 0 <= count <= 100。只有在 count < 100 时，Push 才能写入数组；否则必须先按契约处理 overflow，不能越界写入。

第二，动态数组版本加入 size，并在满载时用 realloc() 扩容：

struct stackCDT {
   stackElementT *elements;
   int count;
   int size;
};

该表示必须保持 0 <= count <= size。若 size == 0，还必须有 count == 0，此时允许 elements == NULL；若 size > 0，elements 必须指向至少能够容纳 size 个元素的有效存储空间。Pop() 还可以配合 谨慎的缩容策略改善内存用量，而不改变 ADT 接口。

#include <limits.h>
#include <stdint.h>
#include <stdlib.h>

/* StackError 会报告错误，并且不会返回。 */
void Push(stackADT stack, stackElementT element) {
   if (stack->count == stack->size) {
      if (stack->size > INT_MAX - 10) {
         StackError("capacity overflow");
      }
      int newSize = stack->size + 10;
      stackElementT *grown;
      if ((size_t)newSize > SIZE_MAX / sizeof *grown) {
         StackError("allocation-size overflow");
      }
      size_t newBytes = (size_t)newSize * sizeof *grown;
      grown = realloc(stack->elements, newBytes);
      if (grown == NULL) {
         StackError("allocation failure");
      }
      stack->elements = grown;
      stack->size = newSize;
   }
   stack->elements[stack->count] = element;
   stack->count++;
}

stackElementT Pop(stackADT stack) {
   if (StackIsEmpty(stack)) {
      StackError("stack underflow");
   }
   return stack->elements[--stack->count];
}

几何增长如何改变摊销成本

含有大量元素的 stack 一次 resize 可能很昂贵，因为所有现有值都可能需要 复制。amortized analysis 把偶发成本分摊到此前成本很低的 push。如果容量按 几何比例增长，各次复制大小形成几何级数，其总和不超过最终深度的常数倍， 所以长操作序列中的平均 push 成本是常数。固定增加容量会触发更多 resize， 总复制量可达平方量级。这项成本分析与失败原子性相互独立：无论采用哪种 增长规则，失败的 resize 都不能提交新容量或丢失旧分配。

缩容需要另一套 policy。每次 pop 后立即收缩，会让交替 push 和 pop 反复 复制相同的值。较低的 shrink threshold 形成 hysteresis：容量在满载边界 增长，但只在使用率显著降低时收缩。如果 shrink allocation 失败，实现可以 安全保留较大区块，因为它仍表示所承诺序列。因此，失败的 growth 会阻止 插入；失败的可选 shrink 却不必让本来成功的 pop 失败。

Stack 应用：逆波兰表示法

以下来源示例是 stack 应用，不是 function pointer dispatch table。逆波兰 表示法先出现 operand，然后才出现 operator，因此程序先 pop 右 operand， 再 pop 左 operand。

void ApplyOperator(char c, stackADT stack) {
   /* 必须在两次 Pop 前检查：depth >= 2；c 合法；所选结果可由 int
      表示；若为除法，y != 0，且 operand pair 不是 INT_MIN, -1。 */
   int y = Pop(stack);
   int x = Pop(stack);

   switch (c) {
   case '+': Push(stack, x + y); break;
   case '-': Push(stack, x - y); break;
   case '*': Push(stack, x * y); break;
   case '/': Push(stack, x / y); break;
   }
}

对格式正确的输入，后置条件是用运算结果替换顶端两个 operand，而较低位置 的 operand 顺序不变。在两次 pop 之前，调用方必须确认所选 +、- 或 * 结果可由 int 表示；除法还要求除数非零，并拒绝 INT_MIN / -1。 这些检查同时避免有符号整数 overflow 的 undefined behavior 和除以零。

Queue 虽然相似，但语义完全不同

Queue 的规则是 FIFO：先进先出。

用从 head 至 tail 的序列表示抽象状态。Enqueue(Q, x) 的后置条件是 Q' = Q · x。Dequeue(Q) 要求 Q != []；若 Q = x · R，则返回 x 并令 Q' = R。概念操作 front 与 top 一样，并未出现在下方较小的 课堂 header 中。

Queue 的 header 也采用 opaque 形式：

typedef struct queueCDT *queueADT;
typedef int queueElementT;

queueADT EmptyQueue(void);
void Enqueue(queueADT queue, queueElementT element);
queueElementT Dequeue(queueADT queue);
int QueueLength(queueADT queue);
int QueueIsEmpty(queueADT queue);

完整的 queue 操作契约

构造操作返回空的 head-to-tail 序列。长度和空状态测试是不改变状态的 observer，而 front observer 还要求 queue 非空。enqueue 成功后恰好把一个 元素附加到 tail；dequeue 成功后返回并删除 head。clear 的后置条件是空 序列。overflow、underflow 和分配失败都必须按照已声明策略处理，不能暴露 部分更新的序列。线性数组、循环数组、动态数组和 linked queue 都遵守 相同语义。

定理 / 命题

证明思路

对操作数目作归纳。零次操作时，两个状态均为空，命题立即成立。假设命题 在 k 次操作后成立。stack 的 push 把值加入从底至顶序列的右端；合法 pop 只删除该最右端值。queue 的 enqueue 把值加入从 head 至 tail 序列的右端； 合法 dequeue 只删除最左端值。top、front 和 isEmpty 等观察操作不会 改变序列。因此每一种下一步操作都保持返回规则和剩余元素的相对次序， 归纳完成。

Queue 的实现：array、circular array、linked list

tutorial 幻灯片列出以下版本。

• 非循环定长数组要么在删除时搬移元素，要么最终在 front 之前留下无法 直接复用的位置；
• 循环数组把第 i 个逻辑元素存于 (front + i) % capacity。若另存 count，空状态是 count == 0，满载是 count == capacity；enqueue 写入 (front + count) % capacity，dequeue 则用模运算推进 front， 所有保留元素都不需要搬移。执行任何模运算之前，表示不变量必须保证 capacity > 0、0 <= front < capacity 和 0 <= count <= capacity；零容量 dynamic queue 必须先增长；
• 动态循环数组保持相同的逻辑不变量，只在满载时增长；
• 链表使用 head 和 tail 指针，只要内存分配成功就可以增长。

循环存储为何不需要搬移元素

当容量为正时，循环表示把每个逻辑 rank 加到 front index，再对容量取模， 从而得到存储位置。enqueue 只改变下一个空位和 count；dequeue 只改变 front index 和 count。每个保留元素的逻辑 rank 因而仍然对应到同一个 已存储值，不需要移动该值。在这里的表示中，另存 count 是 index 重合时 区分空与满的选定方法；其他有效设计也可以预留一个位置或另存 full flag。 动态循环 queue 增长时可以把逻辑序列一次复制到较大区块，但必须在复制 成功后才公开新区块和新 index。

考虑容量为五、front 位于物理位置三、count 为四的 queue。其逻辑元素依次 占据位置三、四、零和一，下一个空位是二。删除 front 后，front 推进到位置 四，count 减至三；位置四、零和一的值完全不移动。后续一次插入会写入位置 二。这段 trace 说明物理 index 顺序与逻辑 FIFO 顺序并不相同，也说明直接 打印 raw array 不是有效的 queue observer。

no-shift 性质对每个容量为正的有效状态都成立，而不只限于上述示例。删除 前，旧逻辑 rank r + 1 存储在 (front + (r + 1)) % capacity。front 推进后，该 survivor 的新 rank 为 r，而位置表示式给出相同存储位置。 因此每个 survivor 已在正确的新逻辑位置。在这里选用的 count-based 设计中， count 限定所有逻辑 rank、指出下一个插入位置，并区分空与满；其他有效的 循环表示可以用不同方式承担这些作用。dynamic growth 时，按 rank 顺序把 元素复制到新 prefix，再把新 front 设为零，就会在较大区块建立相同 invariant。

struct cellT {
   queueElementT element;
   struct cellT *next;
};

struct queueCDT {
   struct cellT *head;
   struct cellT *tail;
};

它的边界状态转移也是表示不变量的一部分：

• 空 queue 同时满足 head == NULL 和 tail == NULL，
• 对空 queue enqueue 时，两个指针都指向新节点，
• 对非空 queue enqueue 时，先连接旧 tail，再推进 tail，
• 多节点 queue dequeue 后只推进 head，
• 唯一节点被 dequeue 并释放后，head 和 tail 都必须重置为 NULL，
• QueueIsEmpty() 只要检查 head == NULL。

在保存 head 和 tail 的前提下，链式 enqueue 和 dequeue 都是常数时间。 课堂实现通过遍历计算 QueueLength，成本为线性；另存并正确维护 count 可以把长度查询改为常数时间，但也增加一项表示不变量。

链式转移顺序与 queue 长度

链式更新必须有适当顺序，使每个中间状态都始终由 queue 持有且保持可达。enqueue 先分配并初始化节点，然后才改变任何 queue pointer。dequeue 先保存旧 head 及其值，再推进 head；如果 queue 变空就重置 tail，最后才释放旧节点。同一 顺序可以一致处理空、单节点和多节点情况，不会留下 dangling public state。 遍历计算长度不需要额外字段，但时间与可达节点数成正比。另存 count 可以让 observer 成为常数时间，前提是每次成功的 enqueue、dequeue 和 clear 都在 同一次提交转移中更新它。

empty-to-one 转移没有旧 tail，因此分配成功后须同时公开两个 endpoint； 非空插入则先连接旧 tail，再推进 tail。删除时须在节点仍存活时复制 value， 再推进 head；若 successor 为 null，释放旧节点前还须把 tail 设为 null。 allocation failure 发生在任何 endpoint 改变前，故 enqueue 保持失败原子性。 若另存 count，enqueue、dequeue 和 clear 都必须同步更新它。

Function pointer 支持 callback 与真正的分派

function pointer 让 C 在运行时选择行为，同时保留可检查的函数签名。

最基本地说，function pointer 存储代码地址：

int (*fp)(int);

括号把“指向函数的指针”和“返回指针的函数”区分开来。typedef 可以使 契约更容易阅读：

typedef int (*intToIntFnT)(int);
int square(int x) { return x * x; } /* 此处要求 x * x 可由 int 表示。 */
intToIntFnT fp = square;
int value = fp(3);

课堂用 hashtable 演示 callback traversal operation。

typedef void (*hashtableFnT)(char *, void *);

/* 前置条件：fp != NULL；key 是借用且只读的。 */
void ForEachEntryDo(hashtableFnT fp, hashtableADT table);

void PrintEntry(char *key, void *value) {
   printf("%s\t%d\n", key, *((int *)value));
}

客户端可以传入：

void DisplayWordCount(hashtableADT table) {
   ForEachEntryDo(PrintEntry, table);
}

这个模式由实现负责 traversal，由客户端负责每个 entry 的特定行为。 prototype 会检查调用形状，但 void * 仍会抹去 payload 类型；PrintEntry 必须恢复并正确使用实际的 pointee 类型。

来源的 command dispatch 应用把指向 cmdEntryT wrapper 的对象指针存为 command 名称所对应的值；function pointer 位于 wrapper 内，而不是由 hashtable 的对象指针直接充当：

typedef void (*cmdFnT)(void);
typedef struct { cmdFnT fp; } cmdEntryT;

void ExecuteCommand(char *cmd, hashtableADT commands) {
   cmdEntryT *entry = (cmdEntryT *)Lookup(commands, cmd);
   if (entry == NULL || entry->fp == NULL) {
      printf("Undefined command: %s\n", cmd);
      return;
   }
   entry->fp();
}

这才是真正的 function-pointer dispatch：lookup 选出签名兼容的函数， 再通过存储的 pointer 调用。前述 RPN switch 并不是 dispatch table。

签名边界与 dispatch table 的生命周期

兼容性涵盖完整函数类型：parameter type、return type 和调用点使用的 prototype 都必须一致；cast 不能让不兼容调用变得安全。这里的 ForEachEntryDo 要求 callback 非空，以明确未指定的次序恰好访问每个 entry 一次，并禁止在 traversal 期间改变 table 结构或 key。每个 key 与 payload pointer 都是借用值，除非另有更长生命周期说明，否则只在该次 callback 期间有效。旧式签名虽然暴露 char *，callback 仍须把 key bytes 当作只读， 不得保留、释放或改写。void * 不提供 run-time type proof，因此 payload 的实际 object type 和 ownership 必须由周围的 ADT 契约规定。

函数签名兼容涵盖每个 parameter 和 return type；cast 不能修复不兼容调用。 多种 command shape 必须采用真正共同的 wrapper signature 或分开的 typed table；(void) 表示不接收参数，不同于旧式的未指定 parameter list。

dispatch table 起始于有效的空 registration state。registration 把 command key 与 table 拥有的 cmdEntryT wrapper 关联；wrapper 内含非空且签名兼容的 function pointer，并按文档规定的 replace-or-reject policy 解决 duplicate key。 wrapper 在 entry 被删除或 table 被销毁前保持有效，函数地址本身不由 table 拥有。当前 wrapper 没有 context；若日后加入 context，registration 还必须 规定 table 是否拥有它，以及删除时使用哪个 destructor。execution 对 absent wrapper 或空 entry->fp 都不得间接调用，然后只调用所选 entry。正是这个 lifecycle 让 table 成为可扩展的 conditional chain 替代方案；单纯写出 switch 并不会产生 registration 与 lookup 语义。

typedef struct {
  int data[100];
  int top;
} Stack;

void push(Stack *s, int x) {
  s->data[++(s->top)] = x;
}

int pop(Stack *s) {
  return s->data[(s->top)--];
}

用程序测试 ADT 契约

接口固定后，问题不应只是“能否编译”，而是“每一步可观察的状态转移 是否仍然符合契约”。

一个实用方法是编写小型 trace test：

stackADT s = EmptyStack();
Push(s, 10);
Push(s, 20);
assert(StackDepth(s) == 2);
assert(Pop(s) == 20);
assert(Pop(s) == 10);
assert(StackIsEmpty(s));

这类测试检查的是 ADT 层次的承诺，而不是底层内存布局。即使以后把 array-based stack 换成 linked representation，只要契约不变，同一组测试 仍应原封不动地通过。

queue 也是一样：一段短短的 enqueue、enqueue、dequeue、dequeue trace 应确认第一个入队的元素仍然最先出队。测试可以要求相同的可观察 行为，却不应假设两种表示具有相同成本。

表示独立的契约测试矩阵

通用 black-box 测试应检查空构造、重复 observer、单元素删除、多元素顺序， 以及共享的成功与失败策略。每个被拒操作后，测试再次观察深度、长度， 并在接口已公开且满足非空前置条件时观察 top 或 front，以便在不读取 字段的情况下验证失败原子性。表示特有测试应另行配置：填满固定容量实现 来触发 overflow，用 instrumented allocator 让动态增长失败，使循环实现跨越 wrap boundary，并让 linked backend 执行单节点 pointer 转移。这些案例不能 原样强加给每一种 backend。复杂度测量也应另置，因为相同结果不代表相同 分配、遍历或 resize 成本。只有测试框架刻意使用 operations table 在运行时 选择实现时，才需要 function pointer。

常见错误

underflow 和 overflow 策略必须在整个接口中一致。终止策略应报告原因， 并在 mutation 前停止；可恢复策略应把状态与元素值分开返回，使每个可能 元素仍可表示。exception 不是 C 的内建机制，静默返回任意值也不是契约。 对 bounded queue 而言，满载是预期状态；对动态结构而言，分配失败是资源 事件。两者可以共用报告机制，但都不能让 counter、index 或 link 只更新 一半。

capacity overflow 与 arithmetic overflow 也必须区分。前者表示 representation 没有获准使用的空位；后者表示建议的新容量或 byte size 即使还未请求内存， 也已经无法安全表示。allocation failure 则表示可表示的 request 未能满足。 三者都应在抽象 append 发生前拒绝 insertion，但 diagnostic 和 recovery choice 可以不同。明确命名这些情况，就可以把模糊 error handling 变成 可测试的 ADT 契约部分。

快速检查

练习

总结

ADT 契约规定合法状态转移和失败行为。stack 与 queue 的实现即使采用不同 存储方式和成本，也必须保持各自的 LIFO 与 FIFO 序列不变量。function pointer 提供受签名约束的 callback 与 dispatch，但不能取代带来表示独立性的 ADT 接口。