2.3 抽象数据类型
一个抽象数据类型是一个接口，它定义了一个数据类型和对该类型的值所进行的操作。一个数据类型是一个值的集合。在C语言中，内建的数据类型包括字符、整数、浮点数等。而结构本身也能定义新的类型，因而可用于建立更高级类型，如列表、树、查找表等。
高级类型是抽象的，因为其接口隐藏了相关的表示细节，并只规定了对该类型值的合法操作。理想情况下，这些操作不会暴露类型的表示细节，因为那样可能使客户程序隐含地依赖于具体的表示。抽象数据类型或ADT的标准范例是栈。其接口定义了栈类型及其5个操作：
〈initial version of stack.h〉≡
#ifndef STACK_INCLUDED
#define STACK_INCLUDED
typedef struct Stack_T *Stack_T;
extern Stack_T Stack_new (void);
extern int Stack_empty(Stack_T stk);
extern void Stack_push (Stack_T stk, void *x);
extern void *Stack_pop (Stack_T stk);
extern void Stack_free (Stack_T *stk);
#endif
上述的typedef定义了Stack_T类型，这是一个指针，指向一个同名结构。该定义是合法的，因为结构、联合和枚举的名称（标记）占用了一个命名空间，该命名空间不同于变量、函数和类型名所用的命名空间。这种惯用法的使用遍及本书各处。类型名Stack_T，是这个接口中我们关注的名称，只有对实现来说，结构名才比较重要。使用相同的名称，可以避免用太多罕见的名称污染代码。
宏STACK_INCLUDED也会污染命名空间，但_INCLUDED后缀有助于避免冲突。另一个常见的约定是为此类名称加一个下划线前缀，如_STACK或_STACK_INCLUDED。但标准C将下划线前缀保留给实现者和未来的扩展使用，因此避免使用下划线前缀看起来是谨慎的做法。
该接口透露了栈是通过指向结构的指针表示的，但并没有给出结构的任何信息。因而Stack_T是一个不透明指针类型，客户程序可以自由地操纵这种指针，但无法反引用不透明指针，即无法查看指针所指向结构的内部信息。只有接口的实现才有这种特权。
不透明指针隐藏了表示细节，有助于捕获错误。只有Stack_T类型值可以传递给上述的函数，试图传递另一种指针，如指向其他结构的指针，将产生编译错误。唯一的例外是参数中的一个void指针，该该参数可以传递任何类型的指针。
条件编译指令#ifdef和#endif以及定义STACK_INCLUDED的#define，使得stack.h可以被包含多次，在接口又导入了其他接口时可能出现这种情况。如果没有这种保护，第二次和后续的包含操作，将因为typedef中的Stack_T重定义而导致编译错误。
在少数可用的备选方案中，这种约定似乎是最温和的。禁止接口包含其他接口，可以完全避免重复包含，但这又强制接口用某种其他方法指定必须导入的其他接口，如注释，也强迫程序员来提供包含指令。将条件编译指令放在客户程序而不是接口中，可以避免编译时不必要地读取接口文件，但代价是需要在许多地方衍生出很多乱七八糟的条件编译指令，不像只放在接口中那样清洁。上文说明的约定，需要编译器来完成所谓的“脏活”。
按约定，定义ADT的接口X可以将ADT类型命名为X_T。本书中的接口在这个约定基础上更进一步，在接口内部使用宏将X_T缩写为T。使用该约定时，stack.h如下：
〈stack.h〉≡
#ifndef STACK_INCLUDED
#define STACK_INCLUDED
#define T Stack_T
typedef struct T *T;
extern T Stack_new (void);
extern int Stack_empty(T stk);
extern void Stack_push (T stk, void *x);
extern void *Stack_pop (T stk);
extern void Stack_free (T *stk);
#undef T
#endif
该接口在语义上与前一个是等效的。缩写只是语法糖（syntactic sugar），使得接口稍微容易阅读一些。T指的总是接口中的主要类型。但客户程序必须使用Stack_T，因为stack.h末尾的#undef指令删除了上述的缩写。
该接口提供了可用于任意指针的容量无限制的栈。Stack_new创建新的栈，它返回一个类型为T的值，可以作为参数传递给其他四个函数。Stack_push将一个指针推入栈顶，Stack_pop在栈顶删除一个指针并返回该指针，如果栈为空，Stack_empty返回1，否则返回0。Stack_free以一个指向T的指针为参数，释放该指针所指向的栈，并将类型为T的变量设置为NULL指针。这种设计有助于避免悬挂指针（dangling pointer），即指针指向已经被释放的内存。例如，如果names通过下述代码定义并初始化：
include "stack.h"
Stack_T names = Stack_new();
下述语句
Stack_free(&names);
将释放names指向的栈，并将names设置为NULL指针。
当ADT通过不透明指针表示时，导出的类型是一个指针类型，这也是Stack_T通过typedef定义为指向struct Stack_T的指针的原因。本书中大部分ADT都使用了类似的typedef。当ADT披露了其表示细节，并导出可接受并返回相应结构值的函数时，接口会将该结构类型定义为导出类型。第16章中的Text接口说明了这种约定，该接口将Text_T声明为struct Text_T的一个typedef。无论如何，接口中的主要类型总是缩写为T。