不完全类型和抽象数据类型的定义

码，比如，只有数组大小增加时才重新分配空间。IA_getSize()访问给定下标所指的元素，让IntArray检查下标是否在界内。

由此可见，IntArray的实现是由两部分组成的，即保存对象信息的数据和构成对象接口的函数，其使用范例程序详见程序清单 2.32。

程序清单 2.32 使用IntArray.h范例程序

>>> 2.4.2 抽象数据类型

1. 栈的实现

假设需要一个字符栈，且栈的大小是固定的，即可使用数组保存栈中的元素，然后指定一个计数器表明栈中元素的数量。其数据结构定义如下：

由于调用者并不能直接访问底层，因此在向栈中压入元素之前，必须先创建一个栈。其函数原型为：

由于刚开始时栈为空，暂时还没有元素存储到数组elements[0]中，因此只要将数组的下标置为0，即可创建一个空栈。即：

其调用形式如下：

当向栈中压入一个新的元素时，将元素存储在数组接下来的空间中，并计数递增。其函数原型为：

也就是说，当top的值加1时，则将新的元素值value入栈。即：

当弹出元素时，计数递减并返回栈顶元素。其函数原型如下：

也就是说，当top的值减1时，则删除栈顶结点，返回该结点的值。比如：

除了这些基本的操作之外，经常还需要知道栈所包含的元素数量，以及栈是空还是满，这些函数的原型为：

显然，只要返回栈顶值就知道栈中存储了多少个元素，而当stack->top为0时，说明栈为空；当stack->top大于等于MAXSIZE时，说明栈已满。

实际上，当定义了一个结构体指针变量stack后，（stack->top）就成为了一个变量，即可通过stack->top与stack->elements[stack->top++]分别实现对stack的各成员的访问。显然程序暴露了"数组和下标"这一内部结构，且无法阻止用户使用stack指针变量直接访问结构体的成员。比如：

由于对直接访问top和elements，因此用户有可能破坏栈中的数据。如果其内部实现发生变化，也必须对程序进行相应的修改。如果程序规模很大，则修改的工作量也很大，因此很多时候明明知道通过重构能够改善程序，也会因工作量太大而不愿意改变具体的实现。

由此可见，上述栈的实现方法不仅暴露了栈的数据结构，而且仅有1个栈。如果需要多个栈时，怎么办？一种方法是编写多个名字不同功能相同的函数，这样就会出现多段处理完全相同的代码。为了解决这个问题，抽象的方法是将栈中的数据结构隐藏到实现代码中。

2. 建立抽象

虽然标准C提供了类似int、char、float、double这样不可分割的原子数据类型，但如果需要表示任意大的整数，显然原子数据类型无能为力。此时，创建一种新的整数类型势在必行，而这种新的数据类型便是一种抽象数据类型ADT（Abstract Data Type）。

设计一个基于Stack的抽象数据类型，我们应该从哪里开始呢？一个不错的方法是用一句话来描述。这种描述应该尽可能地抽象，尽量不要涉及数据的内部结构，要简单到谁都能够理解它，因此可以描述"栈（Stack）是一个可以在同一个位置上插入（push）和删除（pop）数据（value）的存储器，该位置是存储器的末端，即栈顶（top）"。该定义既未说明栈中存储什么数据，也未指定是用数组、结构体还是其它数据形式存储数据，而且也没有规定用什么方式实现操作，这些细节都留给实现去完成。

关于栈的详细描述如下：

• 类型名：Stack

• 类型属性：可以存储有序的数据（value）

• 类型操作：创建栈（newStack）和销毁栈（freeStack），从栈顶添加数据（push）和从栈顶删除数据（pop），确定栈是否为空（stackIsEmpty），确定栈是否已满（stackIsFull），返回栈中元素的个数（getStackDepth），读取栈中任何位置的元素（getStackElement）。

也就是说，在向栈中添加元素之前，必须先创建一个栈。当不再使用内存时，必须销毁栈。对栈的基本操作有push（进栈）和pop（出栈），前者相当于插入，后者相当于删除最后插入的元素。对空栈进行的pop，认为是栈ADT的错误。另一方面，当运行push时空间用尽是一个实现错误，但不是ADT错误。

3. 建立接口

（1）隔离变化

为了防止用户直接访问top和elements而破坏栈中的数据，根据以往的经验，可以使用使用依赖倒置原则。将保存在结构体中栈的实现所需要的数据结构隐藏在".c"文件中，将处理数据的接口包含在".h"文件中，用户将无法看到栈的数据结构在底层是如何实现的。

虽然可以将一个数组看作是具有固定小的，但是内置数组并不会存储它的大小，而且也不会检查下标是否越界。通常将一个指向数组的指针