计算机导论：堆栈介绍及应用

2023-11-18 理论教育版权反馈

【摘要】：对于由n个数据元素构成的线性序列，如果只允许在其头部位置插入数据元素和删除数据元素，则这种逻辑结构的数据结构称为堆栈。很多应用问题的软件设计需要使用堆栈这种数据结构。所以，系统要保证递归结构程序执行过程的正确进行，就必须在调用下一级子程序前，把当前子程序中要保存的数据保存到堆栈中。

对于由n个数据元素构成的线性序列，如果只允许在其头部位置插入数据元素和删除数据元素，则这种逻辑结构的数据结构称为堆栈。

很多应用问题的软件设计需要使用堆栈这种数据结构。例如，在7.4.2节讨论过递归结构，递归结构程序的执行过程如图8-3所示。当主程序调用一个递归结构的子程序时，程序的执行过程是主程序调用该子程序，若子程序不满足递归出口的条件，则该子程序继续调用子子程序，若子子程序不满足递归出口的条件，则该子子程序继续调用子子子程序，直到某次调用的子程序满足递归出口的条件，递归调用过程结束，开始逐级返回；返回的次序是最后被调用的子程序要最先返回，最先被调用的子程序要最后返回。

要实现图8-3所示的递归结构程序的执行过程，就需要有一种数据结构来保存当前子程序的参数和临时变量等数据，以便于在程序返回时能继续执行尚未执行完的部分。例如，对于7.4.2节讨论的计算阶乘的递归算法如下：

PROCEDURE Fact（n）

{

IF（n＝＝1）THEN y＝1；

ELSE y＝n*Fact（n-1）；(www.chuimin.cn)

}

图8-3 递归结构程序的执行过程

假设主程序是Fact（3），则程序的执行过程如图8-4所示。

图8-4 Fact（3）的执行过程

在执行子程序Fact（3）时，由于Fact（2）还未计算出，所以需要保存当前的参数n（此时n＝3）的数值，再继续调用Fact（2）；在执行子程序Fact（2）时，由于Fact（1）还未计算出，所以需要保存当前的参数n（此时n＝2）的数值，再继续调用Fact（1）；在执行子程序Fact（1）时，由于此时满足递归出口的条件，所以结束递归调用过程，得到计算结果y＝1并把该计算结果返回到上一级子程序Fact（2）；在返回到子程序Fact（2）后，继续未完成的计算，得到计算结果y＝2，并把该计算结果返回Fact（3）；在返回到子程序Fact（3）后，继续未完成的计算，得到计算结果y＝6，并把该计算结果返回主程序。由于递归程序的执行过程是最后被调用的子程序要最先被返回，最先被调用的子程序要最后被返回（即后进先出），这正好和堆栈的后进先出特性吻合。所以，系统要保证递归结构程序执行过程的正确进行，就必须在调用下一级子程序前，把当前子程序中要保存的数据保存到堆栈中。

归纳而言，堆栈是由n个数据元素构成的有限的线性序列，并且要求对这个数据元素序列上的插入和删除操作只允许在头部位置进行。换句话说，堆栈是一种保存数据元素并完成数据元素序列先进后出转换的数据结构。

计算机导论：堆栈介绍及应用

相关推荐