形式陈述

抽象数据类型由一组抽象值、操作签名及操作应满足的语义规律组成，而不规定内存布局。可写成多排序代数规格：每个操作

$$op:A_1\times \cdots \times A_k\to B$$

具有输入类型、结果与行为契约；具体数据结构通过表示函数和表示不变式实现该规格。

直觉

ADT 回答“对象能做什么”，实现回答“对象如何存”。同一个栈接口可由数组或链表实现，只要外部可观察行为相同。

例子与边界

栈 ADT 提供 push、pop、top 与空栈查询，并满足后进先出规律。数组容量、扩容策略或节点指针不是栈 ADT 本身。若复杂度写入接口契约，它才成为规格的一部分。

推论与应用

ADT 支持模块化验证、表示独立性和实现替换。算法通常只依赖接口性质；复杂度分析再结合具体表示的操作代价。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022, Parts I–II。
• Robert Sedgewick and Kevin Wayne, Algorithms, 4th ed., Addison-Wesley, 2011, §1.3。