本节将介绍栈这种操作受限的线性表的抽象定义、存储方式以及相应基本操作的实现；用栈完成对导学问题1的实现；对栈的其他应用进行拓展讨论。

3.1.1 知识学习

1. 栈的基本概念

栈是只能在一端进行插入和删除的线性表。允许插入、删除的一端称为栈顶，另一端称为栈底。当栈中没有元素时称为空栈。

栈有两个主要的操作：插入和删除。栈的插入操作常称为入栈（压栈），栈的删除操作常称为出栈（弹栈）。栈的主要特点是“后进先出（Last In First Out，LIFO）”，即出栈元素只能是位于栈顶的元素，而入栈元素也只能放在栈顶位置。因此，栈是一种操作受限的线性表。

图3-1所示的栈中有3个元素，进栈的顺序是 a 、 b 、 c ，出栈时其顺序为 c 、 b 、 a 。

在日常生活中，有很多后进先出的例子，如图3-2所示的硬币收纳筒，要放入一枚硬币或是从中取出一枚硬币只有从顶部操作。在程序设计中，也常常需要栈这样的数据结构，如编译程序中判断表达式括号匹配、算术表达式求值等问题。

【 例3-1 】假定有4个元素 A 、 B 、 C 、 D ，按所列次序进栈，试写出所有可能的出栈序列。注意，每一个元素进栈后都允许出栈，如 ACDB 就是一种出栈序列。

解 ：可能的出栈序列有： ABCD 、 ABDC 、 ACBD 、 ACDB 、 ADCB 、 BACD 、 BADC 、 BCAD 、 BCDA 、 BDCA 、 CBAD 、 CBDA 、 CDBA 、 DCBA 。

当有 n 个元素按照某种顺序压入栈中，且可在任意时刻弹出时，所获得可能的出栈序列个数可用Catalan列计算，即 。

由于栈是操作受限的线性表，因此线性表的存储结构对栈也是适用的，只是操作不同而已。下面分别给出栈的顺序存储及基本操作和链式存储及基本操作。

2. 栈的顺序存储及基本操作

（1）栈的顺序存储结构

利用顺序存储方式实现的栈又称为顺序栈。类似于顺序表的定义，栈中的数据元素用一个预设足够长度的一维数组来存储；栈底位置可以设置在数组的任一个端点，本书将栈底位置设在低下标0处。由于栈顶位置会随着入栈和出栈而变化，因此可用一个整型变量来表示当前栈顶的位置，通常称该整型变量为栈顶指针。

顺序栈的类型定义如下：

栈空时，栈顶指针top= -1；栈满时，栈顶指针top=MaxSize-1。入栈前，栈顶指针加1；出栈后，栈顶指针减1。顺序栈的栈操作示意图如图3-3所示。

（2）顺序栈的操作

由于栈是操作受限的线性表，因此顺序栈的基本操作是顺序表的简化。顺序栈的基本操作算法介绍如下。

1）初始化。初始化栈就是要构造一个空栈，如算法3-1所示。

算法3-1 顺序栈的初始化

2）入栈操作。顺序栈的入栈操作类似于顺序表的插入操作。在栈顶插入一个新元素 x ，使 x 成为新的栈顶元素，同时栈顶指针需要发生变化，如算法3-2所示。

算法3-2 顺序栈的入栈操作

3）出栈操作。出栈操作类似于顺序表的删除操作。将栈顶元素从栈中删除，同时栈顶指针需要发生变化，如算法3-3所示。

算法3-3 顺序栈的出栈操作

4）取栈顶元素。将栈顶元素作为结果返回，栈顶指针不变化，如算法3-4所示。

算法3-4 顺序栈的取栈顶元素操作

5）判断栈是否为空，具体实现如算法3-5所示。

算法3-5 判断顺序栈是否为空

6）判断栈是否为满，具体实现如算法3-6所示。

算法3-6 判断顺序栈是否为满

3. 栈的链式存储及基本操作

（1）栈的链式存储结构

利用链式存储方式实现的栈又称为链栈。链栈中的结点仍可采用在第2章中已经定义的Node结点类型。由于栈是操作受限的线性表，对栈中元素的插入和删除只能在栈顶进行，因此实现链栈的单链表不需要带头结点。链栈通常可表示为如图3-4的形式，栈顶指针top就是单链表的头指针。

链栈的类型定义如下：

可以用LinkStack定义指针，该指针就代表了一个链栈，如：

（2）链栈的操作

链栈的基本操作是单链表基本操作的简化。

1）初始化。初始化函数用于建立一个无头结点的单链表，如算法3-7所示。

算法3-7 链栈初始化

2）入栈操作。入栈类似于在无头结点的单链表中进行表头插入，如算法3-8所示。

算法3-8 链栈入栈操作

3）出栈操作。出栈类似于在单链表中进行表头结点的删除，如算法3-9所示。

算法3-9 链栈出栈操作

4）取栈顶元素。返回栈顶指针所指向结点的数据域即可，如算法3-10所示。

算法3-10 链栈中取栈顶元素操作

5）判断栈是否为空，具体实现如算法3-11所示。

算法3-11 判断链栈是否为空

6）链栈的销毁。类似于单链表的销毁函数，需要释放链栈所占用的空间，如算法3-12所示。

算法3-12 链栈的销毁

请读者自行比较该算法与算法2-15，哪个算法的描述更为简洁？

3.1.2 知识应用：导学问题1的实现

利用栈结构实现数制转换时，主要涉及栈的两个主要操作：入栈和出栈。辗转相除时，将每次所得余数入栈；输出结果时，依次出栈即可。转换函数的代码如下：

如果需要增强以上函数的通用性，使其可以将十进制数 n 转换成 r 进制数（ r 为二进制至十六进制间任意值）。上述函数该如何修改？请读者在上面conversion函数右边的空白框中尝试写出改进后的函数，如有困难，请用手机扫描右侧的二维码查看参考代码。

3.1.3 知识拓展：栈的其他应用

栈的应用非常广泛，只要问题满足“后进先出”原则，均可使用栈作为其数据结构。计算机中表达式的求值问题、递归程序等均与栈相关。本节将介绍这些实际问题如何使用栈来解决。

1. 算术表达式求值

算术表达式求值问题：输入包含+、-、*、/、圆括号和正整数组成的中缀算术表达式，以′@′作为表达式结束符，计算该表达式的运算结果。

（1）利用中缀表达式直接求值

在程序设计语言中，操作符（运算符）位于两个操作数中间的表达式称为中缀表达式。

中缀表达式的计算比较复杂，在计算过程中，既要考虑括号的作用，又要考虑操作符的优先级，还要考虑操作符出现的先后次序。由于各操作符实际的运算次序往往与它们在表达式中出现的先后次序是不一致的。因此在求值时不能简单地进行从左到右运算，必须先算运算级别高的，再算运算级别低的，同一级别的运算才从左到右，这种方法称为“算符优先法”。算符间的优先关系见表3-1。

要实现中缀表达式直接求值，必须设置两个栈：一个栈存放操作符，记做OPTR；另一个栈存放操作数，记做OPND。

中缀表达式求值算法的步骤如下。

1）初始时，操作数栈为空，操作符栈中放置一个元素′@′。

2）依次读入表达式中的每个字符，直至表达式结束。

①若读到的是操作数，则进入操作数栈，并读入下一个字符。

②若读到的是操作符c，则将操作符栈的栈顶元素pre_op与之进行比较，会出现以下3种情况：

● 若pre_op＜c，则将c入栈，并读入下一个字符。

● 若pre_op=c，则pre_op出栈，并读入下一个字符。

● 若pre_op＞c，则pre_op出栈，并在操作数栈中退栈两次，依次得到操作数b和a，然后进行a pre_op b运算，并将运算的结果压入操作数栈中。

3）扫描完毕时操作数栈中只有一个元素，即为运算的结果。

【 例3-2 】利用算符优先法，对输入的算术表达式“8/（5-3）@”求值。

解 ：操作过程见表3-2。

算法3-13 算符优先法求算术表达式的值

注意：算法3-13只能对10以内的算术表达式求值，其中完成计算的函数Operate（），以及进行算符优先级比较的函数Precede（）等请读者自行完成。还需要注意的是，算法中用到了两个数据元素类型不同的栈，需要分别进行定义。参考程序可登录www.cmpedu.com进行下载。

由于C语言功能的限制，本程序中对于操作符栈和操作数栈需要分别定义一套处理代码，而这两段代码中的处理功能是一致的，只是处理的数据类型不同。C++语言提供的类模板可以很好地解决这个问题，用类模板实现算法3-13的代码请参考 《数据结构（C++语言描述）》（吉根林、陈波编著，高等教育出版社，2014）一书。

（2）利用后缀表达式求值

波兰科学家卢卡谢维奇很早就提出了算术表达式的另一种表示，即后缀表示，又称逆波兰式。后缀是指把操作符放在两个操作数的后面。采用后缀表示的算术表达式被称为后缀算术表达式或后缀表达式。在后缀表达式中，不存在括号，也不存在优先级的差别，计算过程完全按照运算符出现的先后次序进行。

【 例3-3 】将下列各中缀表达式转换为后缀表达式。

（1）3/5+6

（2）16-9*（4+3）

（3）2*（x+y）/（1-x）

（4）（25+x）*（a*（a+b）+b）

解 ：相应的后缀表达式如下：

（1）3 5/ 6 +

（2）16 9 4 3 + * -

（3）2 x y + *1 x - /

（4）25 x + a a b + * b + *

将中缀表达式变成等价的后缀表达式时，表达式中操作数的次序不变，而操作符的次序会发生变化，同时需要去掉圆括号。因此设置一个栈OPTR用以存放操作符。

把中缀表达式转换为后缀表达式算法的基本思路如下。

1）初始时，操作符栈中放置一个元素′@′。

2）依次读入中缀表达式中的每个字符，对于不同类型的字符按不同情况进行处理。

①若读到的是操作数，则输出该操作数，并读入下一个字符。

②若读到的是左括号，则把它压入到OPTR栈中，并读入下一个字符。

③若读到的是右括号，则表明括号内的中缀表达式已经扫描完毕，将OPTR栈从栈顶直到左括号之前的操作符依次出栈并输出，然后将左括号也出栈，并读入下一个字符。

④若读到的是操作符c，则将操作符栈的栈顶元素pre_op与之进行比较：

● 若pre_op ＜c，则将c入栈，并读入下一个字符。

● 若pre_op＞=c，则将pre_op出栈并输出。

⑤若读到的是结束符@，则将栈中剩余的操作符依次出栈并输出，即可得到转换成的后缀表达式。

请读者根据以上算法步骤完成程序。

【 例3-4 】用一个操作符栈来模拟将输入的中缀算术表达式“8/（5-3）@”转换成后缀表达式的过程。

解 ：操作过程见表3-3。

将中缀表达式转换成等价的后缀表达式求值时，不需要再考虑操作符的优先级，只需从左到右扫描一遍后缀表达式即可。可设置一个栈OPND用以存放操作数。

后缀表达式求值算法的基本思路如下：

1）依次读入后缀表达式中的每个字符，直至表达式结束。

● 若读到的是操作数，则入栈OPND。

● 若读到的是操作符，则在OPND栈中退出两个元素（先退出的在操作符右，后退出的在操作符左），然后用该操作符进行运算，并将运算的结果压入OPND栈中。

2）后缀表达式扫描完毕时，若OPND栈中仅有一个元素，即为运算的结果。

请读者根据以上算法步骤完成应用实战第1题。

【 例3-5 】用一个操作数栈来模拟【例3-4】所得的后缀算术表达式“853 - / @”的求值过程。

解 ：操作过程见表3-4。

2. 栈与递归

（1）递归的含义

递归是指函数直接调用自己或通过一系列调用语句间接调用自己，该函数称为递归函数。递归是程序设计的有效方法之一，可用递归方法求解的问题必须同时具备以下两个条件：

1）一个问题可以化解为若干个性质相同、解法相同的小问题，而小问题还可分解为更小的问题……上述转化具有相同的规律，并使问题逐步简化。

2）存在明确的递归出口（终止条件），即当问题规模降低到一定程度时可以直接求解。

实际上以上两点也是递归算法设计的基本框架。

根据上述条件，适合用递归方法求解的问题有以下3种情况：

1）数学上定义为递归的函数。例如，求整型数 n 的阶乘的定义为

还有很多递归性质的函数，如Fibonacci级数、Ackerman函数等。

2）数据的结构是递归的。例如，本书第5章介绍的广义表，其元素也可以是一个子表，而子表也是表；第6章介绍的树形结构，每个结点可以有0至多个子树，而子树又是一棵树。

3）解题的方式用递归解法比用递推解法更为简单。例如，汉诺塔问题、八皇后问题等。

（2）栈和递归

在用高级语言编写的程序中，对于函数的调用，系统是通过栈来实现的。一个递归函数的执行过程类似于多个函数的嵌套调用，因此在执行递归函数的过程中也需要一个“递归工作栈”。它的作用如下：

1）将递归调用时的实际参数和函数返回地址传递给下一层的递归函数。

2）保存本层的参数和局部变量，以便从下一层返回时重新使用它们。

算法3-14给出了求整型数 n 的阶乘的递归设计。

算法3-14 求阶乘的递归算法

图3-5给出了 n =3时求阶乘递归算法的运行轨迹。

图3-6给出了 n =3时求阶乘递归算法运行时的工作栈中的状况。