抽象数据类型：先规定能做什么，再决定怎样实现

同学，你已经区分逻辑结构和存储结构。今天的新困难是把一个数据结构写成不依赖具体代码的“使用契约”：有哪些数据、关系和操作，每个操作需要什么条件、完成后保证什么。

抽象数据类型可以用三部分描述：数据对象 $D$、数据关系 $S$、基本操作集合 $P$。它关心外部可观察行为，不提前绑定数组、指针或某种语言。这样调用者依赖稳定接口，实现者可以在不破坏契约的前提下更换存储方案。

陪做栈的规格。数据对象是一组同类型元素；关系是从栈底到栈顶的线性次序；操作可包含 Init、Push(x)、Pop()、Top()、IsEmpty()。Pop 的前置条件是栈非空，后置条件是原栈顶被返回并删除，其余元素次序不变。这里“后进先出”是行为约束，而“数组末端作栈顶”只是某一种实现。

若用顺序栈，需要处理容量和扩容；若用链栈，需要管理结点与指针。两种实现都应满足同一 Push/Pop 契约。判断它们是不是同一个 ADT 的依据是外部行为是否一致，不是内存布局是否相同。

再看封装的意义：调用者若绕过操作直接修改内部指针，可能破坏“栈顶可达、链不断裂”等不变量。ADT 把允许的状态变化集中在操作中，使正确性更容易证明和测试。

针对性错解：把 ADT 写成某个 C 结构体，只描述了表示而没有操作语义；只列函数名不写空栈、越界等前置条件，契约不完整；认为抽象意味着不讨论效率也不对，同一契约仍可比较不同实现的复杂度。

迁移题：为队列写出 Enqueue 与 Dequeue 的前后置条件。参考答案：入队要求容量允许，完成后新元素成为队尾、原元素相对顺序不变；出队要求非空，返回并删除原队头。顺序循环队列与链队列都可实现该契约。独立验收是能为一个自选 ADT 写出 $D,S,P$，并给两个操作各写前置条件、状态变化与复杂度目标。完成本章后，你应能从现实建模一路走到抽象接口和复杂度证明。