下载掌阅APP，畅读海量书库
立即打开
栈（stack）又称堆栈，是限制在表的一端进行插入和删除的线性表。其限制是仅允许在表的一端进行插入和删除操作，不允许在其他任何位置进行插入、查找、删除等操作。表中进行插入、删除操作的一端称为栈顶（Top），栈顶保存的元素称为栈顶元素。相对的，表的另一端称为栈底（Bottom）。当栈中没有数据元素时称为空栈；向一个栈插入元素又称为进栈或入栈；从一个栈中删除元素又称为出栈或退栈。
由于栈的插入和删除操作仅在栈顶进行，后进栈的元素必定先出栈，所以又把堆栈称为后进先出表（Last In First Out，LIFO）。图3.1 显示了一个堆栈及数据元素插入和删除的过程。
图3.1 堆栈及入栈和出栈
在图3.1中，当ABCD均已入栈之后，出栈时得到的序列为DCBA，这就是“后进先出”。在解决实际问题时，如果碰到了数据的使用具有“后进先出”的特性，就预示着可以使用堆栈来存储和使用这些数据。堆栈的基本操作除了进栈、出栈操作外，还有判空、取栈顶元素等操作。
由于栈是运算受限的线性表，除了操作不同外，线性表的存储结构对栈也是适用的。利用顺序存储方式实现的栈称为顺序栈。为了便于理解，后面示例中顺序栈操作，均以学号和姓名为数据元素。
根据顺序栈的存储特点，要将某一元素压入栈内，则要进行如下操作：
（1）先判断栈是否已经装满元素，如果未装满才能进行入栈操作，否则不操作。
（2）栈顶指针先自增，给需要进栈的元素腾出内存空间。
（3）再将要入栈的元素放入腾出的内存空间里，就是把入栈的元素赋值给对应的数组元素。
【例3.1】1200101班已有2名同学王丽、张阳的报到信息存放在栈内，现有（120010131，郑克龙）同学来报到，请将其信息压入栈中。
首先要定义学生信息结构体来存放学生记录，具体参见上一章的struct Student定义。
接下来压入对应结点的过程如下：
入栈前如图3.2所示。
图3.2 入栈前学生报到信息表
图3.3 入栈后学生报到信息表
栈顶指针先自增，给需要进栈的元素腾出内存空间，再往空间里压入元素（120010131，郑克龙），如图3.3所示。
顺序栈的学生元素存放在data数组中，length为栈的总长度，top为栈顶指针，则学生元素入栈程序流程图如图3.4所示。
图3.4 学生元素入栈流程图
根据顺序栈的存储特点，要取出栈内某一元素，则要进行如下操作：
（1）先判断栈是否有元素，如果有元素时才能进行出栈操作，否则不操作。
（2）再将要出栈的元素取出放在内存空间里。
（3）栈顶指针自减。
【例3.2】1200101 班已有3 名同学王丽、张阳、郑克龙的报到信息存放在栈内，现需要从栈中取出一位同学的信息进行审查，并显示取出的信息。
首先要定义学生信息结构体来存放学生记录，具体参见上一章的struct Student定义。
接下来取出对应结点的过程如下：
出栈前如图3.5所示。
先把需要出栈的元素（120010131，郑克龙）取出放在内存空间里，再把栈顶指针自减，如图3.6所示。
图3.5 入栈后学生报到信息表
图3.6 入栈前学生报到信息表
顺序栈的学生元素存放在data数组中，length为栈的总长度，top为栈顶指针，则学生元素出栈程序流程图如图3.7所示。
图3.7 学生元素出栈流程图
在入栈程序的基础上，添加出栈代码，实现如图3.7所示的流程功能，具体代码实现如下：
用链式存储结构实现的栈称为链栈。其结点结构与单链表的结构相同，链式堆栈也是由一个个结点组成的，每个结点由两个域组成：一个是存放数据元素的数据元素域element；另一个是存放指向下一个结点的对象引用（即指针）域next。
图3.8 链栈示意图
因为栈中的主要运算是在栈顶插入、删除，显然在链表的头部做栈顶是最方便的，而且没有必要像单链表那样为了运算方便附加一个头结点，所以链式堆栈通常不带头结点。
通常将链栈表示成图3.8 的形式。
在学生信息结构体的基础上，链栈的结点定义如下：
链栈的基本操作也是进栈和出栈操作。
根据链栈的存储特点，要将某一个新结点s压入栈内，则要进行如下操作：
（1）处理新结点s的后继，这个后继就是原本的栈顶结点。
（2）将栈顶指针top重新指向新结点s即可。
【例3.3】1200101 班已有两名同学王丽、张阳的报到信息存放在链栈内，现有（120010131，郑克龙）同学来报到，请将其信息压入链栈中。
首先要定义学生信息结构体和结点结构体，具体参见上一章struct Student和struct Node的定义。
接下来将对应结点压入链栈内的过程如下：
入栈前如图3.9所示。
图3.9 入栈前学生报到信息表
生成新结点（120010131，郑克龙），处理新结点的后继，使其后继指向原本的栈顶结点，如图3.10所示。
图3.10 新结点链入栈
将栈顶指针 top 重新指向新结点（120010131，郑克龙）即可，如图3.11所示。
图3.11 重置top指针
链栈中插入的学生元素存放在node中，top为栈顶指针，curlen为栈的长度，则学生元素入栈程序流程图如图3.12所示。
图3.12 链栈入栈流程图
根据链栈的存储特点，要弹出某一个结点，则要进行如下操作：
（1）在栈顶指针top非空的情况下，保存弹出结点。
（2）将栈顶指针top下移一个元素，即top=top.next。
【例3.4】1200101 班已有3 名同学王丽、张阳、郑克龙的报到信息存放在链栈内，现需要从链栈中取出一位同学的信息进行审查，并显示取出的信息。
首先要定义学生信息结构体和结点结构体，具体参见上一章struct Student和struct Node的定义。
接下来弹出对应结点的过程如图3.13所示。
图3.13 新结点出栈
链栈中弹出学生元素存放在ni中，top为栈顶指针，curlen为栈的长度，则学生元素出栈程序流程图如图3.14所示。
图3.14 链栈出栈流程图
在链栈入栈程序的基础上，添加出栈代码，实现如图3.14所示的流程功能，具体代码实现如下：
递归（Recursion）是指在定义自身的同时又出现了对自身的引用。如果一个算法直接或间接地调用自己，则称这个算法是一个递归算法。
任何一个有意义的递归算法总是由两部分组成：递归调用与递归终止条件。下面是一个递归的例子。
【例3.5】非负整数的阶乘Fac(N)被定义为所有小于或等于N的正整数的积。若用N!表示该值，则：
下面以Fac(4)=4!=4*3*2*1=24 为例来说明递归使用，如图3.15所示。
首先，执行主程序的语句Fac(4)，触发第1 次方法调用，进入函数后，值参数N=4，应执行计算4*Fac(3)。
图3.15 递归调用说明
为了计算Fac(3)，将触发对方法Fac的第2 次调用，重新进入方法，值参数N=3，应执行计算3*Fac(2)。
为了计算Fac(2)，将触发对方法Fac的第3 次调用，重新进入方法，值参数N=2，应执行计算2*Fac(1)。
为了计算Fac(1)，将触发对方法Fac的第4 次调用，重新进入方法，值参数N=1，应执行计算1*Fac(0)。
为了计算Fac(0)，将触发对方法Fac的第5 次调用，重新进入方法，值参数N=0，应执行计算Fac(0)=1。回送结果Fac(0)=1，返回到调用处，完成第5 次调用。返回第4 次调用。
计算1*Fac(0)=1*1=1，完成第4 次调用，回送结果Fac(1)=1，返回到第3 次调用。
计算2*Fac(1)=2*1=2，完成第3 次调用，回送结果Fac(2)=2，返回到第2 次调用。
计算3*Fac(2)=3*2=6，完成第2 次调用，回送结果Fac(3)=6，返回到第1 次调用。
计算4*Fac(3)=4*2=24，完成第1 次调用，回送结果Fac(4)=24，返回到主程序。
这个递归算法的逻辑很简单，即N大于0 时递归调用到N-1，N等于0 时返回1，具体代码如下：
此算法先判断是否满足递归终止条件，如果满足则执行返回，否则进行递归调用执行计算。在这里可以看到递归调用与递归终止条件在递归算法中缺一不可，如果没有递归终止条件，那么递归将会无休止的进行下去；而没有递归调用，则递归算法就不成其为递归算法。因此在编写递归算法时一定要注意这两个方面的内容。
我们知道在递归算法中会递归调用自身，因此在递归算法的执行过程中会多次进行自我调用。
为了说明自身的递归调用，先看任意两个函数之间进行调用的情况。
通常在一个函数执行过程中需要调用另一个函数时，在运行被调用函数之前系统通常需要完成3 件工作：①对调用函数的运行现场进行保护，主要是参数与返回地址等信息的保存；②创建被调用函数的运行环境；③将程序控制转移到被调用函数的入口。
在被调用函数执行结束之后，返回调用函数之前，系统同样需要完成3 件工作：①保存被调函数的返回结果；②释放被调用函数的数据区；③依照保存的调用函数的返回地址将程序控制转移到调用函数。
如果上述函数调用的过程中发生了新的调用，即被调函数在执行完成之前又调用了其他函数，此时构成了多个函数的嵌套调用。当发生嵌套调用时按照后调用先返回的原则处理，如此则形成了一个保存函数运行时环境变量的“后进先出”的使用过程，因此整个函数调用期间的相关信息的保存需要使用一个堆栈来实现。系统将整个程序运行时需要的数据空间安排在一个堆栈中，每当调用一个函数时就为它在栈顶分配一个存储区，每当从一个函数返回时就释放它的存储区。
一个递归算法的实现实际上就是多个相同函数的嵌套调用。
下面用例3.5中的Fac来说明递归的实现过程。假设n=3，那么递归调用的过程如图3.16所示。
图3.16 递归调用栈状态