2.5　栈结构

在程序设计中，读者一定接触过“堆栈”的概念。其实，“栈”和“堆”是两个不同的概念。栈是一种特殊的数据结构，在中断处理特别是重要数据的现场保护有着重要意义。

2.5.1　什么是栈结构

栈结构是从数据的运算来分类的，也就是说栈结构具有特殊的运算规则。而从数据的逻辑结构来看，栈结构其实就是一种线性结构。如果从数据的存储结构来进一步划分，栈结构包括两类。

・顺序栈结构：即使用一组地址连续的内存单元依次保存栈中的数据。在程序中，可以定义一个指定大小的结构数组来作为栈，序号为0的元素就是栈底，再定义一个变量top保存栈顶的序号即可。

・链式栈结构：即使用链表形式保存栈中各元素的值。链表首部（head引用所指向元素）为栈顶，链表尾部（指向地址为null）为栈底。

典型的栈结构，如图2-9所示。从图中可以看出，在栈结构中只能在一端进行操作，该操作端称为栈顶，另一端称为栈底。也就是说，保存和取出数据都只能从栈结构的一端进行。从数据的运算角度来分析，栈结构是按照“后进先出”（Last In Firt Out，LIFO）的原则处理结点数据的。

其实，栈结构在日常生活中有很多生动的例子。例如，当仓库中堆放货物时，先来的货物放在里面，后来的货物码放在外面；而要取出货物时，总是先取外面的，最后才能取到里面放的货物。也就是说，后放入货物先取出。

在计算机程序设计中，特别是汇编程序中，栈通常用于中断或者子程序调用过程。此时，首先将重要的寄存器或变量压入栈，然后进入中断例程或者子程序，处理完后，通过出栈操作恢复寄存器和变量的值。

在栈结构中，只有栈顶元素是可以访问的。这样，栈结构的数据运算非常简单。一般栈结构的基本操作有两个。

・入栈（Push）：将数据保存到栈顶的操作。进行入栈操作前，先修改栈顶引用，使其向上移一个元素位置，然后将数据保存到栈顶引用所指的位置。

・出栈（Pop）：将栈顶的数据弹出的操作。通过修改栈顶引用，使其指向栈中的下一个元素。

接下来，了解如何在Java语言中建立顺序栈，并完成顺序栈结构的基本运算。

2.5.2　准备数据

有了前面的理论知识后，下面就开始栈结构的程序设计。首先需要准备数据，即准备在栈操作中需要用到的变量及类等。示例代码如下：

在上述代码中，定义了栈结构的最大长度MAXLEN，栈结构数据元素的类DATA及栈结构的类StackType。在类StackType中，data为数据元素，top为栈顶的序号。当top=0时表示栈为空，当top=SIZE时表示栈满。

Java语言中数组都是从下标0开始的。在这里，为了讲述和理解的方便，从下标1开始记录数据结点，下标0的位置不使用。

2.5.3　初始化栈结构

在使用顺序栈之前，首先要创建一个空的顺序栈，即初始化顺序栈。顺序栈的初始化操作步骤如下：

（1）按符号常量SIZE指定的大小申请一片内存空间，用来保存栈中的数据。

（2）设置栈顶引用的值为0，表示一个空栈。

初始化顺序栈的代码示例如下；

在上述代码中，首先使用new关键字申请内存，申请成功后设置栈顶为0，然后返回申请内存的首地址。如果申请内存失败，将返回null。

2.5.4　判断空栈

判断空栈即判断一个栈结构是否为空。如果是空栈，则表示该栈结构中没有数据。此时可以进行入栈操作，但不可以进行出栈操作。

判断空栈的代码示例如下：

在上述代码中，输入参数s为一个指向操作的栈的引用。程序中，根据栈顶引用top是否为0，判断栈是否为空。

2.5.5　判断满栈

判断满栈即判断一个栈结构是否为满。如果是满栈，则表示该栈结构中没有多余的空间来保存额外数据。此时不可以进行入栈操作，但是可以进行出栈操作。

判断满栈的代码示例如下：

在上述代码中，输入参数s为一个指向操作的栈的引用。程序中，判断栈顶引用top是否等于符号常量MAXLEN，从而判断栈是否已满。

2.5.6　清空栈

清空栈即清除栈中的所有数据。清空栈的代码示例如下：

在上述代码中，输入参数s是一个指向操作的栈的引用。在程序中，简单地将栈顶引用top设置为0，表示执行清空栈操作。

2.5.7　释放空间

释放空间即释放栈结构所占用的内存单元。由前面知道，在初始化栈结构时，使用了malloc函数分配内存空间。虽然可以使用清空栈操作，但是清空栈操作并没有释放内存空间，这就需要使用free函数释放所分配的内存。

释放空间的代码示例如下：

在上述代码中，输入参数s是一个指向操作的栈的引用。程序中，直接赋值null操作释放所分配的内存。一般在不需要使用栈结构的时候使用，特别是程序结束时。

2.5.8　入栈

入栈（Push）是栈结构的基本操作，主要操作是将数据元素保存到栈结构。入栈操作的具体步骤如下：

（1）首先判断栈顶top，如果top大于等于SIZE，则表示溢出，进行出错处理；否则执行以下操作。

（2）设置top=top+1（栈顶引用加1，指向入栈地址）。

（3）将入栈元素保存到top指向的位置。

入栈操作的代码示例如下：

在上述代码中，输入参数s是一个指向操作的栈的引用，输入参数data是需要入栈的数据元素。程序中首先判断栈是否溢出，如果溢出则不进行入栈操作；否则修改栈顶引用的值，再将元素入栈。

2.5.9　出栈

出栈（Pop）是栈结构的基本操作，主要操作与入栈相反，其操作是从栈顶弹出一个数据元素。出栈操作的具体步骤如下：

（1）判断栈顶top，如果top等于0，则表示为空栈，进行出错处理；否则，执行下面的步骤。

（2）将栈顶引用top所指位置的元素返回。

（3）设置top=top-1，也就是使栈顶引用减1，指向栈的下一个元素，原来栈顶元素被弹出。

在上述代码中，输入参数s是一个指向操作的栈的引用。该函数返回值是一个DATA3类型的数据，返回值是栈顶的数据元素。

2.5.10　读结点数据

读结点数据即读取栈结构中结点的数据。由于栈结构只能在一端进行操作，因此这里的读操作其实就是读取栈顶的数据。

需要注意的是，读结点数据的操作和出栈操作不同。读结点数据的操作仅显示栈顶结点数据的内容，而出栈操作则将栈顶数据弹出，该数据不再存在了。

读结点数据的代码示例如下：

在上述代码中，输入参数s是一个指向操作的栈的引用。该方法返回值同样是一个DATA3类型的数据，返回值是栈顶的数据元素。

2.5.11　栈结构操作实例

学习了前面的栈结构的基本运算，便可以轻松地完成对栈结构的各种操作。下面给出一个完整的例子，来演示栈结构的创建、入栈和出栈等操作。代码示例如下：

【程序2-3】

在上述代码中，main（）主方法首先初始化栈结构，然后循环进行入栈操作，添加数据结点，当输入全部为0时则退出结点添加的进程。接下来，用户每按一次按键，就进行一次出栈操作，显示结点数据。当为空栈时，退出程序。该程序执行结果，如图2-10所示。