下载掌阅APP，畅读海量书库
立即打开
栈是作为一种限定性线性表，只允许在表的一端进行插入和删除操作。
栈 （Stack），也称为堆栈，它是一种特殊的线性表，只允许在表的一端进行插入和删除操作。允许在表中地行插入删除操作的一端称为栈顶（Top），另一端称为栈底（Bottom）。栈顶是动态变化的，它由一个称为栈顶指针（top）的变量指示。当表中没有元素时，称为空栈。
栈的插入操作称为入栈或进栈，删除操作称为出栈或退栈。
在栈S=（a 1 ,a 2 ,…,a n ）中，a 1 称为栈底元素，a n 称为栈顶元素。栈中的元素按照a 1 ，a 2 ，…，a n 的顺序依次进栈，当前的栈顶元素为a n 。最先进栈的元素一定在栈底，最后进栈的元素一定在栈顶。每次删除的元素是栈顶元素，也就是最后进栈的元素。因此，栈是一种后进先出的线性表。如图3.1所示。
在图3.1中，a 1 是栈底元素，a n 是栈顶元素，由栈顶指针top指示。最先出栈的元素是a n ，最后出栈的元素是a 1 。
可以把栈想象成一个木桶，先放进去的东西在下面，后放进去的东西在上面，最先取出来的是最后放进去的，最后取出来的是最先放进去的。
图3.1 栈的示意图
图3.2演示了元素A、B、C、D和E依次进栈和出栈的过程。
图3.2 元素A、B、C、D、E进栈和出栈的过程
如果一个进栈的序列由A、B、C组成，它的出栈序列由ABC、ACB、BAC、BCA和CBA五种可能，只有CAB是不可能的输出序列。因为A、B、C进栈后，C出栈，接着就是B要出栈，A不可能在B之前出栈，所以CAB是不可能出现的序列。
栈的抽象数据类型定义了栈中的数据对象、数据关系及基本操作。栈的抽象数据类型定义如下：
ADT Stack{数据对象：D={a i |a i ∈ElemSet，i=1，2，…，n，n≥0}数据关系：R={<a i-1 ,a i >|a i-1 ，a i ∈D，i=2，3，…，n}约定a 1 端为栈底，a n 端为栈顶。
基本操作：
（1）InitStack（&S）
初始条件：栈S不存在。
操作结果：建立一个空栈S。
这就像盖房子前，先打了地基，建好框架结构，再准备垒墙。
（2）StackEmpty（S）
初始条件：栈S已存在。
操作结果：若栈S为空，返回1，否则返回0。
栈为空就类似于打好了地基，还没有开始垒墙。栈不为空就类似于开始垒墙。
（3）GetTop（S,&e）
初始条件：栈S存在且非空。
操作结果：返回栈S的栈顶元素给e。
栈顶就像刚垒好的墙的最上面一层砖。
（4）PushStack（&S,x）
初始条件：栈S已存在。
操作结果：将元素x插入到栈S中，使其成为新的栈顶元素。
这就像在墙上放置了一层砖，成为墙的最上面一层。
（5）PopStack（&S,&e）
初始条件：栈S存在且非空。
操作结果：删除栈S的栈顶元素，并用e返回其值。
这就像拆墙，需要把墙的最上面一层从墙上取下来。
（6）StackLength（S）
初始条件：栈S已存在。
操作结果：返回栈S的元素个数。
这就像整个墙有多少层组成。
（7）ClearStack（S）
初始条件：栈S已存在。
操作结果：将栈S清为空栈。
这就像把墙全部拆除。
}ADT Stack
与线性表一样，栈也有两种存储表示：顺序存储和链式存储。
采用顺序存储结构的栈称为顺序栈。顺序栈利用一组连续的存储单元存放栈中的元素，存放顺序依次从栈底到栈顶。由于栈中元素之间的存放地址的连续性，在C语言中，同样采用数组实现栈的顺序存储。另外，增加一个栈顶指针top，用于指向顺序栈的栈顶元素。
栈的顺序存储结构类型描述如下：
用数组表示的顺序栈如图3.3所示。将元素A、B、C、D、E、F、G、H依次进栈，栈底元素为A，栈顶元素为H。在本书中，约定栈顶指针top指向栈顶元素的下一个位置（而不是栈顶元素）。
图3.3 顺序栈结构
说明：
（1）初始时，栈为空，栈顶指针为0，即S.top=0。
（2）栈空条件为S.top==0，栈满条件为S.top==StackSize-1。
（3）进栈操作时，先将元素压入栈中，即S.stack[S.top]=e，然后使栈顶指针加1，即S.top++。出栈操作时，先使栈顶指针减1，即S.top--，然后元素出栈，即e=S.stack[S.top]。
（4）栈的长度即栈中元素的个数为S.top。
注意： 当栈中元素个数为StackSize时，称为栈满。当栈满时进行入栈操作，将产生上溢错误。如果对空栈进行删除操作，将产生下溢错误。因此，在对栈进行进栈或出栈操作前，要判断栈是否已满或已空。
顺序栈的基本运算如下（以下算法的实现保存在文件“SeqStack.h”中）。
（1）栈的初始化。
（2）判断栈是否为空。
（3）取栈顶元素。
注意： 取栈顶元素并不是将元素出栈，这里的操作是S.stack[S.top-1]，并没有修改栈顶指针top的值，即不能写作S.stack[-S.top]或S.stack[S.top-1]。
（4）进栈操作。
（5）出栈操作。
（6）返回栈的长度。
（7）清空栈。
栈的应用非常广泛，经常会出现一个程序需要同时使用多个栈的情况。使用顺序栈会因为栈空间的大小难以准确估计，从而造成有的栈溢出，有的栈还有空闲。为了解决这个问题，可以让多个栈共享一个足够大的连续存储空间，利用栈的动态特性使栈空间能够互相补充，存储空间从而得到有效利用，这就是栈的共享，这些栈被称为共享栈。
在栈的共享问题中，最常用的是两个栈的共享。共享栈主要通过栈底固定、栈顶迎面增长的方式实现。让两个栈共享一个一维数组stack[StackSize]，两个栈底设置在数组的两端，当有元素进栈时，栈顶位置从栈的两端向中间迎面增长；当两个栈顶相遇时，栈满。
共享栈（两个栈共享一个连续的存储空间）的数据结构类型描述如下。
其中，top[0]和top[1]分别是两个栈的栈顶指针。
例如，共享栈的存储表示如图3.4所示。
图3.4 共享栈示意图
共享栈的算法操作（以下算法保存在文件“SSeqStack.h”中）如下。
（1）初始化。
（2）进栈操作。
（3）出栈操作。
采用链式存储方式的栈称为链栈或链式栈。由于栈的插入与删除操作仅限在表头的位置进行，因此链表的表头指针就作为栈顶指针。通常，链栈采用带头结点的单链表实现。如图3.5所示。
图3.5 链栈示意图
在图3.5中，top为栈顶指针，始终指向栈顶元素前面的头结点。链栈的基本操作与链表的类似，在使用完链栈时，应释放其空间。
链栈结点的类型描述如下：
链栈的进栈操作与链表的插入操作类似，出栈操作与链表的删除操作类似。关于链栈的操作说明如下：
（1）链栈通过链表实现，链表的第一个结点位于栈顶，最后一个结点位于栈底。
（2）设栈顶指针为top，初始化时，对于不带头结点的链栈，top=NULL；对于带头结点的链栈，top->next=NULL。
（3）不带头结点的栈空条件为top==NULL，带头结点的栈空条件为top->next==NULL。
链栈的基本运算具体实现如下（以下算法的实现保存在文件“LinkStack.h”中）。
（1）链栈的初始化。
（2）判断链栈是否为空。
（3）进栈操作。进栈操作就是要将新元素结点插入到链表的第一个结点之前，分为两个步骤：①p->next=top->next；②top->next=p。进栈操作如图3.6所示。
图3.6 进栈操作
（4）出栈操作。出栈操作就是将单链表中的第一个结点删除，并将结点的元素赋值给e，并释放结点空间。在元素出栈前，要判断栈是否为空。出栈操作如图3.7所示。
图3.7 出栈操作
（5）取栈顶元素。
（6）求表长操作。
在链表中为了求表中元素个数，必须从栈顶指针出发，依次访问每个结点，并利用计数器计数，直到栈底为止。求表长的时间复杂度为O（n）。
（7）销毁链栈。
