1.1 ADT 操作：stack、queue 与 function pointer

同一接口，不同表示

Stack 可以用数组，也可以用 linked node 保存元素。成功执行 push(10) 与 push(20) 后，调用者在两种表示下都应从 pop() 得到 20。数组索引与节点地址不同，可观察的序列却相同。如果调用者直接读取内部 count 字段或跟随 node link，即使 stack 的行为仍然正确，更换表示也可能破坏客户端。

抽象数据类型把这种可观察行为与实际存储分开。前置条件说明何时允许操作，后置条件说明返回结果和操作后的状态。失败行为同样可见：定长 stack 拒绝一次 push，而可增长 stack 接受它，除非共享契约明确处理这个差别，否则不能把两者视为相同实现。

抽象状态与失败原子性

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

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

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

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

Stack 限制下一次移除的对象必须是最近加入的元素。调用者不必知道存储布局，也能根据这个规则预测结果。

以上是概念层面的操作。下方的 C header 并未公开 top；接口也可以把这项观察操作命名为 Peek。调用者只能使用实际 header 已声明的操作。

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 handle 防止客户端依赖内部字段：

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 可以保存和传递 handle，却不能直接访问字段，因此不同存储表示可以公开相同声明。

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

Stack 的实现方式

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

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

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

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

动态数组版本加入 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 都不能提交新容量或丢失旧分配。

例如，容量按 1, 2, 4, 8, ... 增长时，复制量由之前容量的总和控制，而这个几何和小于下一个容量。因此，只含 push 的长序列总复制量是线性的；触发 resize 的某一次 push 仍可能花费当前深度的线性时间。摊还界并不表示每一次操作都同样快。

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

链式表示与不同的成本模型

增长改变存储身份，而不改变元素顺序。Linked stack 要求无环链，首节点表示顶端。它使用另一 simulation relation：从 top 沿 next link 行走，所得顺序是从底至顶抽象序列的反向。push 安装一个新 head；pop 拆下一个旧 head。如果另存 depth，每次成功 link 变更都必须在同一次 commit 更新它；如果通过遍历计算 depth，成本就是线性而不是常数。两种选择仍可以满足完全相同的 observer 后置条件。合法的定长数组 push 与 pop 都是常数时间；linked stack 同样只改变一个节点，但分配成本与 locality 有别于连续存储。

错误通道与被拒绝的更新

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

Sentinel 也可能是合法元素值。把状态与输出值分开返回可避免歧义；上面的不返回处理器则放弃恢复。不同操作若混用这些失败策略，客户端便无法统一推理失败之后的行为。

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

Stack 应用：逆波兰表示法

逆波兰表示法先出现 operand，再出现 operator。最近压入的是右 operand，因此程序先 pop 右 operand，再 pop 左 operand。计算只依赖 stack 契约，不必访问其内部字段。

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 和除以零。

FIFO 需要在两端操作

工作队列需要取出最早仍在等待的项目，即使期间不断有新项目到达。这个 FIFO 规则要求在相反的逻辑端点执行插入与移除。

用从 head 至 tail 的序列表示抽象状态。Enqueue(Q, x) 的后置条件是 Q' = Q · x。Dequeue(Q) 要求 Q != []；若 Q = x · R，则返回 x 并令 Q' = R。概念操作 front 与 top 一样，并未出现在下方较小的 C 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 都遵守相同语义。

合法更新为何保持 LIFO 与 FIFO

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

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)--];
}

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

反复移除首元素会带来 stack 没有的存储问题：空位可能不断积累在 front 之前。

• 非循环定长数组要么在删除时搬移元素，要么最终在 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 指针，只要内存分配成功就可以增长。

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

考虑容量为五、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。其他循环设计可以预留一个位置或另存 full flag。新区块和 index 只能在分配与复制成功后公开。

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

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

空 queue 的表示同时要求 head == NULL 与 tail == NULL，因此 QueueIsEmpty() 可以只检查 head == NULL。跨越空与单节点的边界时，更新必须维持两个 endpoint 的一致性。

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

链式转移顺序与 queue 长度

新节点必须先分配并初始化，才能改变 queue 的 endpoint。不同边界状态决定接下来需要更新哪些 link。

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

Function pointer 支持 callback 与真正的分派

容器可以确定要遍历哪些 entry，却不必预先决定调用者要怎样处理它们。 Callback 在运行时提供这项操作，同时保留可检查的函数签名。

最基本地说，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);

Dictionary 可以自行遍历 entry，再让 callback 处理每个关联。客户端不必知道 bucket 的具体布局，因此可以先独立规定这个 traversal 接口。

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 契约规定。

仅有相同参数个数并不足够；通过不兼容函数类型调用具有 undefined behavior。多种 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 语义。

用程序测试 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。

Model-based test 可以维护一个简单序列作为 oracle，把相同操作分别施加于模型与 ADT，并比较返回值及 observer 结果。模型只表达契约，因此不依赖具体字段。测试序列应包含空、单元素和多元素之间的转移。

失败测试需要可控制的原因，例如填满有界表示，或让分配层拒绝下一次申请。被拒操作后，除了重新检查 observer，还应继续执行合法操作，确认对象仍可使用。Callback 测试记录被访问的 entry 与 payload identity；dispatch 测试则覆盖已注册命令、未知 key 及替换策略。时间和分配次数另行测量，不能用速度代替语义正确性。

常见错误

快速检查

练习

总结

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