3.2 栈及其应用

栈实际上也是线性表，只不过是一种特殊的线性表。栈的运算规则较一般线性表有更多的约束和限制，因此又称为限定性数据结构。本节将讨论栈的结构特点、顺序栈的基本运算及应用。

3.2.1 栈的基本概念和结构特征

1.栈的基本概念

栈作为一种限定性线性表，是将线性表的插入和删除运算限制为仅在表的一端进行，通常将表中允许进行插入、删除操作的一端称为栈顶（Top），因此栈顶的当前位置是动态变化的，它由一个称为栈顶指针的位置指示器指示。同时，表的另一端被称为栈底（Bottom）。当栈中没有元素时称为空栈。栈的插入操作被形象地称为进栈或入栈，删除操作称为出栈或退栈。

2.栈的结构特征

通常栈可以用线性的方式存储，分配一块连续的存储区域存放栈中的元素，并用一个变量指向当前的栈顶，如图3-5所示。

每次进栈的元素都被放在原栈顶元素之上而成为新的栈顶，而每次出栈的总是当前栈中“最新”的元素，即最后进栈的元素。在图3-5所示的栈中，元素是以a1，a2，a3，…，an的顺序进栈的，而退栈的次序却是an，…，a3，a2，a1。栈的修改是按后进先出（Last In First Out，LIFO）的原则进行的。因此，栈又称为后进先出的线性表，简称为LIFO表。

3.栈的建立

在C语言中用一维数组来实现栈。假设栈的元素个数最大不超过整数Maxsize，所有的元素都具有同一个数据类型DataType，则可用下列方式来定义栈的类型Stack：

说明：

1）类型标示符DataType可以是任何的数据类型，如：int、float、char和复合类型等。在算法中，除特别说明外，规定DataType的默认类型是int。

2）Maxsize是一个表示栈中可容纳的最多元素的正整数，称为栈的最大容量。假设用宏定义设置其值为100，其C语言程序如下：

3）变量top是栈指针，指向栈顶，栈中元素和栈顶指针之间的关系如图3-6所示。

4）置空栈。初始化栈顶指针，其C语言程序如下：

3.2.2 栈的基本运算

栈的基本操作除了进栈（栈的压入）、出栈（栈的弹出）外，还有读栈顶元素、判定栈是否为空等运算。

1.栈的压入Push（S，x）

将数据元素x插入到S栈中的函数：

2.栈的弹出Pop（S，x）

从栈中弹出栈顶元素，并获取栈顶元素的值：

进栈（栈的压入）、出栈（栈的弹出）操作如图3-7所示。

3.读栈顶元素GetTop（S，x）

读栈顶元素而保持栈不变的函数：

4．判定栈是否为空isEmpty(S)

判定栈s是否为空栈的函数：

3.2.3 栈的应用

由于栈结构具有的后进先出的特性，致使栈成为程序设计中常用的工具。以下是几个栈应用的例子。

1．算术表达式的中缀表示

把运算符放在参与运算的两个操作数中间的算术表达式称为中缀表达式。例如，“2+3*4-6/9”算术表达式中包含了算术运算符和算术量（常量、变量、函数），而运算符之间又存在着优先级，不能简单地进行从左到右运算，编译程序在求值时，必须先算运算级别高的，再算运算级别低的，同一级运算才从左到右。在计算机中进行中缀表达式求值较麻烦，而后缀表达式求值较方便（无须考虑运算符的优先级及圆括号）。

2．算术表达式的后缀表示

把运算符放在参与运算的两个操作数后面的算术表达式称为后缀表达式。例如，对于下列各中缀表达式：

1)3/5+8。

2)18-9水(4+3)。

对应的后缀表达式为：

1)35/8+。

2)18943+水-。

转换规则：把每个运算符都移到它的两个操作数的后面，然后删除所有的括号即可。

3．后缀表达式的求值

将中缀表达式转换成等价的后缀表达式后，求值时，不需要再考虑运算符的优先级，只需从左到右扫描一遍后缀表达式即可。具体求值步骤为：从左到右扫描后缀表达式，遇到运算符就把表达式中该运算符前面两个操作数取出并运算，然后把结果带回后缀表达式；继续扫描直到后缀表达式最后一个表达式。

4．后缀表达式的求值的算法

设置一个栈，开始时栈为空，然后从左到右扫描后缀表达式，若遇操作数，则进栈；若遇运算符，则从栈中退出两个元素，先退出的放到运算符的右边，后退出的放到运算符左边，运算后的结果再进栈，直到后缀表达式扫描完毕。此时，栈中仅有一个元素，即为运算的结果。

例如，求后缀表达式：12+82-74-/*（中缀表达式为（1+2）+(8-2)／(7-4))的值，栈的变化情况如表3-2所示。

从以上可知，最后求得的后缀表达式之值为6，与用中缀表达式求得的结果一致，但后缀式求值要简单得多。

5.中缀表达式变成等价的后缀表达式的算法

将中缀表达式变成等价的后缀表达式，表达式中操作数次序不变，运算符次序发生变化，同时去掉了圆括号。转换规则是：设立一个栈，存放运算符，首先栈为空，编译程序从左到右扫描中缀表达式，若遇到操作数，直接输出，并输出一个空格作为两个操作数的分隔符；若遇到运算符，则必须与栈顶比较，运算符级别比栈顶级别高则进栈，否则退出栈顶元素并输出，然后输出一个空格作分隔符；若遇到左括号，进栈；若遇到右括号，则一直退栈输出，直到退到左括号止。当栈变成空时，输出的结果即为后缀表达式。将中缀表达式（1＋2）*（（8-2）／（7-4））变成等价的后缀表达式。

现在用栈来实现该运算，栈的变化及输出结果见表3-3。

6.数制转换

将一个非负的十进制整数N转换为另一个等价的基为B的B进制数的问题，很容易通过“除B取余法”来解决。

【例3-1】 将十进制数13转化为二进制数。

解答：按除2取余法，得到的余数依次是1、0、1、1，则十进制数转化为二进制数为1101。

分析：由于最先得到的余数是转化结果的最低位，最后得到的余数是转化结果的最高位，因此很容易用栈来解决。

转换算法如下：

说明：函数Initstack（）、push（）、isEmpty（）定义见3.2.2。

7.栈的应用举例之迷宫求解

求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。由于计算机求解迷宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求迷宫通路的算法中应用“栈”也就是自然而然的事了。

首先，在计算机中可以用如图3-8所示的方块图表示迷宫。图中的每个方块或为通道（以空白方块表示），或为墙（以带阴影的方块表示）。所求路径必须是简单路径，即在求得的路径上不能重复出现同一通道块。

假设“当前位置”指的是“在搜索过程中某一时刻所在图中某个方块位置”，则求迷宫中一条路径的算法的基本思想是：若当前位置“可通”，则纳入“当前路径”，并继续朝“下一位置”探索，即切换“下一位置”为“当前位置”，如此重复直至到达出口；若当前位置“不可通”，则应顺着“来向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周4个方块均“不可通”，则应从“当前路径”上删除该通道块。所谓“下一位置”指的是“当前位置”四周4个方向（东、南、西、北）上相邻的方块。假设以栈s记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。由此，“纳入路径”的操作即为“当前位置入栈”；“从当前路径上删除前一通道块”的操作即为“出栈”。

求迷宫中一条从入口到出口的路径的算法可简单描述如下：

在此，需说明的一点是，所谓当前位置可通，指的是未曾走到过的通道块，即要求该方块位置不仅是通道块，而且既不在当前路径上（否则所求路径就不是简单路径），也不是曾经纳入过路径的通道块（否则只能在死胡同内转圈）。