抽象数据类型

抽象数据类型（ADT）描述一个集合承诺能做什么，而不说它是怎么做到的。想想自动取款机。从外面看，你知道它的契约：插卡、输密码、取现金、查余额。你并不知道——也不需要知道——现金是装在转鼓里、托盘里，还是墙后一只机械臂里。接口是承诺；机械是藏起来的。抽象数据类型对一组数据来说，正是这样一种承诺：它支持哪些操作，以及每个操作意味着什么。

举个例子，栈这个抽象数据类型只承诺压入、弹出、以及「看一眼顶上是什么」，规则是后进先出。队列这个抽象数据类型承诺相反的次序，先进先出。映射（或字典）这个抽象数据类型承诺存放「键到值」的配对，并能凭键查到值。要紧的是，这些都没说「怎么做」。栈可以由数组实现，也可以由链表实现；映射可以是哈希表，也可以是平衡树。抽象数据类型是行为；数据结构则是兑现这一行为的某一台机器。

为什么要把两者分开？因为这样你就能只凭那份承诺来推理正确性，然后把底下的机器换成更快的一台，而不必动用到它的那些代码——只要新机器守住同样的承诺。这正是良好软件设计的核心：面向接口编程，而非面向实现。当你读到「队列的入队是 O(1)」时，那是在说队列这个抽象数据类型的某一种具体实现，而不是在说抽象数据类型本身。