为什么先讲契约
在 CSCI2520 里，最常见的错误通常不是少了一个分号，而是少了一个 清楚的契约。
ADT 会先说明四件事：
- 允许做什么操作，
- 每个操作要保证什么结果，
- client 调用之后可以假设什么状态，
- 空结构和错误情况怎么处理。
这一步很重要，因为同一个 stack 或 queue 接口，可以用 fixed array、 dynamic array，或者 linked list 来实现。client 代码不应该因为内部实现 变化而一起改。
定义
ADT 契约与实现
ADT 契约描述操作和语义。 实现决定数据字段、内存布局，以及更新方式。 契约是承诺；实现是机制。
Stack 是只能从顶端操作的结构
讲到 stack，核心不是“一摞东西”这个比喻，而是 top-only 这条不变量。
定义
Stack 核心操作
对于一个 stack ：
push(x)：把x放入顶端，pop()：移除并返回顶端元素，top()：查看顶端但不移除，isEmpty()：检查是否为空，StackDepth()：返回深度。
LIFO 是 stack 的基本规则：后进先出。
例题
追踪 stack 状态
初始是空 stack。
push(10)之后是[10]push(20)之后是[10, 20]top()返回20，状态不变pop()返回20，stack 变成[10]
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，但不能直接改内部字段。
定理
表示独立性
如果 client 只能通过 ADT 已声明的操作来使用数据结构，那么内部 representation 就可以自由更改，而不影响 client 可见行为。
Stack 的实现方式
slides 里强调了三个重要概念。
第一，fixed array 版本会用一个 count 记录深度：
struct stackCDT {
stackElementT elements[100];
int count;
};
这个版本简单，但最大深度固定为 100。深度超过上限时，会出现 representation-level 的 overflow。
第二，dynamic array 版本会再加 size，并在满的时候使用 realloc()
扩容：
struct stackCDT {
stackElementT *elements;
int count;
int size;
};
第三，Pop() 还可以进一步收敛 memory usage，让实现更完整。意思是：
ADT 接口不变，但 memory policy 可以逐步改进。
例题
Push / Pop 的简化实现
void Push(stackADT stack, stackElementT element) {
if (stack->count == stack->size) {
stack->size += 10;
stack->elements = realloc(
stack->elements,
stack->size * sizeof(stackElementT)
);
}
stack->elements[stack->count] = element;
stack->count++;
}
stackElementT Pop(stackADT stack) {
stack->count--;
return stack->elements[stack->count];
}
重点是：
count表示下一个可用位置，push先存再加一，pop先减一再返回旧顶端。
Queue 虽然相似，但语义完全不同
Queue 的规则是 FIFO：先进先出。
定义
Queue 核心操作
对于一个 queue ：
enqueue(x)：从尾端加入x，dequeue()：从前端移除并返回，front()：查看前端但不移除，isEmpty()：检查是否为空，QueueLength()：返回长度。
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 的实现：array、circular array、linked list
tutorial slide 已经把几个版本讲得很清楚。
- fixed array 版本最好理解，但前端出队后容易浪费空间；
- circular array 通过
%实现 wrap around，让前后位置可以重复使用； - linked list 用
head和tail指针，插入和删除时不需要搬移旧数据。
struct cellT {
queueElementT element;
struct cellT *next;
};
struct queueCDT {
struct cellT *head;
struct cellT *tail;
};
linked list 版本的意思是：
- 新节点接到尾端后面，
head指向前端，QueueIsEmpty()只要检查 。
例题
为什么 circular array 比普通 array 更好
如果 queue 不断交替 enqueue 和 dequeue：
- 普通 array 会在前端释放出空位后，未必能有效重用；
- circular array 会把
front和rearwrap around，把前面空位重新利用起来。
所以 tutorial 才会问：如果重复做很多次 enqueue / dequeue，会发生什么？
function pointer 让 C 可以做分派和 callback
function pointer 不是额外技巧，而是 C 做 runtime dispatch 的核心工具。
int (*fp)(int);
这个声明表示 fp 是一个指向“接收一个 int，返回一个 int”函数的
指针。prototype 本身就是 type contract。
定义
Function pointer 规则
function pointer 只能指向参数列表和返回类型都匹配的函数。
课堂里用 hashtable 做了一个很实际的例子：给 ADT 加一个 callback traversal operation。
typedef void (*hashtableFnT)(char *, void *);
void ForEachEntryDo(hashtableFnT fp, hashtableADT table);
client 可以传入：
void DisplayWordCount(hashtableADT table) {
ForEachEntryDo(PrintEntry, table);
}
这个模式对 ADT 很有用，因为 traversal 交给 implementation 做，而每个 entry 要怎么处理，则由 client 提供。
同样，dispatch table 也可以靠 function pointer 来做，避免一大串 if
判断。
void ApplyOperator(char c, stackADT stack) {
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;
}
}
在这个例子里，stack 用来存 operand，而 operation table 决定怎么把它们 组合起来。function pointer 让 C 具备了一种手工控制的 polymorphism。
边读边试
追踪 ADT 操作语义
这个工具现在把 C 风格程序示例和可编辑指令串列放在一起，让读者可以直接测试 stack 与 queue 的 ADT 语义。
程序示例
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)--];
}自己试一试
行变换: push(10)
stack: [10]
queue: []
栈顶现为 10。
自己试一试
push 10
当前状态: [10]
返回值: 没有返回值
push 20
当前状态: [10, 20]
返回值: 没有返回值
top
当前状态: [10, 20]
返回值: 20
pop
当前状态: [10]
返回值: 20
push 7
当前状态: [10, 7]
返回值: 没有返回值
最终状态: [10, 7]
用程序测试 ADT 契约
当接口固定之后，下一个问题不应该只是“能不能 compile”，而是 “每一步可观察到的状态转移，是否仍然符合契约”。
一个实用做法是写小型 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，就应该证明第一个入队的元素仍然是第一个出队。
常见错误
常见错误
把 stack 和 queue 语义混淆
push / pop 是 stack；enqueue / dequeue 是 queue。改名不改行为，
就是破坏 ADT 契约。
常见错误
忽略空结构错误策略
空 stack 做 pop、空 queue 做 dequeue，都必须预先定义清楚错误处理方式。
常见错误
把接口稳定和实现稳定混为一谈
应该保持稳定的是接口；应该允许演进的是内部 representation。
快速检查
快速检查
做完 push(1), push(2), pop() 之后，stack 还剩什么？
按 LIFO 来判断。
解答
答案
快速检查
做完 enqueue(4), enqueue(7), dequeue() 之后，返回什么元素？
按 FIFO 来判断。
解答
答案
快速检查
为什么 ForEachEntryDo(PrintEntry, table) 需要 callback type，而不是普通 generic pointer？
重点是 type checking 和参数列表匹配。
解答
引导答案
练习
快速检查
写出 Pop(stack) 对非空 stack 的前置条件和后置条件。
尽量精确。
解答
引导答案
快速检查
解释为什么 linked list queue 可以 enqueue 而不需要搬移旧元素。
用 head 和 tail 来讲。
解答
引导答案
快速检查
用一小段文字解释 function pointer 怎样帮助 ADT 测试。
要讲到接口和实现分离。
解答
引导答案
重点总结
真正重要的不是“stack 和 queue 是两种数据结构”这么简单，而是：
- ADT 契约定义行为，
- 实现负责存储和内存，
- function pointer 让 C 可以维持 type-safe 的分派和 callback。