栈和队列的应用

栈的应用

逆序输出

栈的逆序输出应该是栈最简单的应用了，由于栈的先进后出的特点，我们很自然地想到将输入序列按顺序压入栈中，在将所有元素压入栈中以后，再从栈顶依次弹出所有元素，这样就得到了一个被逆置的序列。下面我们进行一个约定：

用<表示栈顶，用]表示栈底，如\(<1, 2, 3, 4]\)就表示一个\(1\)为栈顶，\(4\)为栈底的栈。

进制转换

进制转换的过程中，我们就自然地用到了逆序输出，比如对于十进制数\(56\)，我们要将其转换为\(2\)进制数，过程如下：

\[\begin{equation} \begin{aligned} 2&|\underline{\phantom{0}56\phantom{0}}\\ 2&|\underline{\phantom{0}28\phantom{0}}\cdots\cdots 0\\ 2&|\underline{\phantom{0}14\phantom{0}}\cdots\cdots 0\\ 2&|\underline{\phantom{0}7\phantom{0}}\cdots\cdots 0\\ 2&|\underline{\phantom{0}3\phantom{0}}\cdots\cdots 1\\ &\phantom{0}1\phantom{0} \end{aligned} \end{equation} \]

我们计算余数的顺序是，先获得最低有效位，再依次获得高位，因此最终的答案是\(11000_2\)。在计算机上，我们需要对产生的余数序列进行逆置，才能得到转换后的数，我们可以使每次得到余数后就将余数压入栈中，最后将栈中的元素依次取出，这样就得到了被逆置的数。

表达式求值

表达式求值应当是栈最有意思的应用之一了，在介绍利用栈进行表达式求值之前，我们介绍一下什么是中缀表达式。

中缀表达式

一个表达式由三类元素组成：

操作数：被用于计算的数字
运算符：各类运算符号，如加法，减法等
限定符：各类括号，用于提升表达式某一部分的优先级

例如\(2 + 3\)就是一个表达式，其中的\(2,3\)就是操作数，\(+\)就是运算符。而中缀表达式指的就是运算符在两个操作数之间的表达式。

对于一个复杂的中缀表达式，可以这样手算：

找到优先级最高的运算符
计算该运算符
重新回到(1)，直到表达式中没有运算符

对于人眼，很容易分辨一个表达式中优先级最高的运算符，因此中缀表达式很适合手算，但是对于计算机来说，找到优先级最高的运算符并没有这么容易，并且由于限定符的存在，运算符优先级的判断将更加困难。于是，我们就需要一个没有限定符，并且很容易发现运算符优先级的表达式，由于计算机求解。一个波兰数学家为我们做好了这件事。

后缀表达式（逆波兰表达式）

后缀表达式，顾名思义，就是运算符在操作数之后的表达式，例如\(23+\)，就表示\(2\)和\(3\)相加。再看一个复杂的情况：

例

计算后缀表达式\(6\phantom{0} 5\phantom{0} 4\phantom{0} 3-*+2\phantom{0} 1/-\)。

下面我们给出一个后缀表达式的一般计算方法：

按顺序遍历所有的运算符
对于某个运算符，其前面的前两个数就是其运算数，计算该运算符
重复(1-2)直到表达式中无运算符

下面我们来看看例子的计算过程：

\[\begin{equation} \begin{aligned} 6\phantom{0}5\phantom{0}\underline{4\phantom{0}3-}*+2\phantom{0}1/-\\ 6\phantom{0}\underline{5\phantom{0}1*}+2\phantom{0}1/-\\ \underline{6\phantom{0}5+}2\phantom{0}1/-\\ 11\phantom{0}\underline{2\phantom{0}1/}-\\ \underline{11\phantom{0}2-}\\ 9 \end{aligned} \end{equation} \]

这里我们就得到了最终的结果\(9\)，从上述过程可以看出，我们只需要按顺序遍历所有的运算符，然后分别计算就可以了，这非常适合计算机求解。

具体的，在计算机中应该怎么求解逆波兰表达式呢？首先我们需要一个栈，并进行以下操作：

按顺序遍历表达式
如果遍历到操作数，压入栈中
如果遍历到运算符，弹出栈顶的两个元素，计算该运算符，结果压入栈中
重复(1-3)直到遍历完整个表达式

只要表达式是合法的，最后栈中有且仅有一个元素，即该表达式的解。

中缀表达式转后缀表达式

既然知道了后缀表达式适合计算机求解，那么剩下的问题就是如何将中缀表达式转成后缀表达式了。暂时抛开计算机，我们怎么样手动将中缀表达式转换成后缀表达式呢？下面看一个例子：

例

将表达式\(6+5*(4-3)-2/1\)转换成后缀表达式

关键点在于按优先级顺序找到运算符，我们来看一下这个例子的过程：

当前优先级最高的是括号中的-，将其和操作数加入后缀表达式得到\(4\phantom{0}3-\)
接下来优先级最高的有两个，一个是*，一个是/，我们约定，在优先级一样的时候，先计算靠左边的运算符，因此是*，4-3作为一个整体，充当乘法的操作数，因此将\(5\)和*加入后缀表达式得到\(5\phantom{0}4\phantom{0}3\phantom{0}-*\)
下面优先级最高的是/，由于在后缀表达式中，运算符是按计算顺序排列的，因此/要放在*的后面，于是有\(5\phantom{0}4\phantom{0}3-*2\phantom{0}1/\)
接着又有两个优先级一致的运算符，选择最左边的，于是有\(6\phantom{0}5\phantom{0}4\phantom{0}3-*+2\phantom{0}1/\)，这里5*(4-3)整体作为加法的一个操作数
最后将减法加入，有\(6\phantom{0} 5\phantom{0} 4\phantom{0} 3-*+2\phantom{0} 1/-\)

可以验证，这两者是等价的。

其实不难看出，一个运算符如果能运算，其两个操作数中的运算符一定要先计算，如上例中，-和*排在+之前，实际上转换后缀表达式就是模拟操作数产生的过程，我们从头遍历一个中缀表达式的时候，遇到运算符并不能马上得知其是否可以运算，因为其两个操作数可能并没有产生，例如上例中遍历到第一个加法，它的左操作数有了，但是右操作数还不能确定，就需要存在某个辅助内存中，等待该操作符被确认可以计算后再从辅助内存中取出来，加入表达式，而这个辅助内存就是栈。

基于下面的规则，我们可以用计算机进行中缀表达式到后缀表达式的转换：

从头遍历中缀表达式
遇到操作数直接加入后缀表达式
遇到运算符，从栈中依次弹出比它优先级高或者同级的运算符，直到遇到"("或者栈为空，加入后缀表达式
遇到"("，直接压入栈中，遇到")"，弹出所有的操作符直到遇到"("，这里我们假设表达式合法，因此一定会有一个"("与其匹配
重复(1-4)直到遍历完整个表达式

这样，我们就得到了一个与原来中缀表达式等价的后缀表达式。至于为什么这个方案是可行的，我们可以定性地分析一下：

对于一个运算符，其可以运算，当且仅当在其左边的所有高优先级或同级运算符被计算，且直到下一个同级运算符，两者之间的所有高级运算符被计算，这个也是出于该运算符的两个操作数都被生成这个保证，其比下一个同级运算符先计算，而又需要左右两边的操作数中的运算符被计算。
括号里的表达式整体应当作为一个操作数，因此括号里的运算符在遍历到")"的时候应当被全部安排妥当，它们的优先级一定是高于后面的运算符的。
对于暂时还不能确定是否可以被计算的运算符，放入栈中等待必要的信息齐全并且能判断优先级了以后，再取出

其实，对于已经确定运算顺序的运算符，我们可以直接对其进行运算，我们用两个栈，一个存放操作数，一个存放运算符，一旦有有个运算符出栈，也就是确定运算顺序了，就可以从操作数栈中取出两个数进行运算，将结果再压入操作数栈中。这样，整个表达式只需要遍历一遍就可以计算出结果。

递归求解

表达式求值除了上述实现，还有一种更为直观的实现，也就是递归求解，详见南京大学PA，总的来说就是根据表达式的递归定义进行求解，这也是一个很好的实现。

括号匹配

括号匹配也是个很简单的应用，什么叫括号匹配呢？对于每一个左括号，都有一个相应的右括号与其匹配，且这一对括号之间的所有括号都是匹配的。例如：

((((((()))))))是匹配的
((())是不匹配的，因为有左括号没有相应的右括号匹配
(()()())()()是匹配的
([(]))是不匹配的，因为最内层的一对()中仅有一个]，不匹配

我们把这个定义拆开来看看：

每一个左括号对应一个右括号
一个括号序列是匹配的，当且仅当去掉内层的括号也是匹配的，比如([][])是匹配的，那么()也是匹配的

于是我们可以用下面的方法来检验括号序列是否匹配：

按顺序从头遍历括号序列
遇到左括号直接压入栈中
遇到右括号，如果栈顶括号不与其匹配，返回不匹配；如果匹配，将栈顶括号弹出
重复(1-3)直到遍历完所有的括号，若栈中为空，返回匹配；否则返回不匹配

其实这就是模拟一个删除内层括号的过程，对于当前的栈顶元素，要么其是内层括号，我们找到其匹配的右括号，删除之；要么不是内层括号，我们会找到新的左括号。

下面看一个例子：

例

用上述算法判断((())((()))[])是否匹配

首先遍历到第一个"("，压入栈中
接着我们又找到了一个左括号，说明原来栈顶不是内层括号，将第二个左括号压入栈中
重复上面的过程直到发现了第一个右括号，其与栈顶括号匹配，删除之
接着又找到了一个右括号，此时的栈顶元素与之匹配，并且在(3)删除了原来的内层括号后，该对括号变成了内层括号，删除之
重复上面的过程，可以得到该序列匹配

递归调用

函数的递归调用过程天然和栈想契合，在某个函数没有完成其任务时，碰巧碰到了对其他函数的调用，那么我们就有必要保存当前函数的局部变量，直到被调用的函数返回后，再取出来完成剩下的工作。这就相当于一个栈所做的工作，先被调用的函数后返回，也就是先进后出。事实上，在计算机语言中，函数调用就是通过栈来实现的。

例

说明如下代码的调用过程：

void func(int n) {
    return n > 0 ? func(n - 1) * n : 1
}
int main(){
    func(3);
    return 0;
}

事实上我们可以得到：

\[\begin{align} &|\overline{\underline{func(0)}}|\phantom{0}\phantom{0} \uparrow\\ &|\underline{func(1)}|\phantom{0}\phantom{0}\ \ |\\ &|\underline{func(2)}|\phantom{0}\phantom{0}\ \ |调用顺序\\ &|\underline{func(3)}|\phantom{0}\phantom{0}\ \ |\\ &|\underline{main(\ )}|\phantom{0}\phantom{0}\ \ |\\ \end{align} \]

调用顺序时自底向上，而返回顺序时自顶向下，这就是一个函数调用栈。

剪枝

这里引用邓俊辉老师在其《数据结构》中提到的故事：

古希腊神话中半人半牛的怪物米诺陶诺斯，藏身于一个精心设计的、结构极其复杂的迷宫之中\(\dots\dots\)他（忒修斯）将线绳的一端系在迷宫路口处，而后在此不断检查各个角落的过程中，线团始终我在他的手中。

迷宫问题是剪枝的一个经典应用，假设迷宫是四方形的，被切分成了若干列和若干行，人物只能向上下左右走。我们要找到从起点到终点的路，实际上就是要找到从起点到终点的一个合法格子序列，这个格子序列是由起点\(s\)开头，以终点\(t\)为结尾的，并且序列中相邻的两个格子在迷宫中也是相邻并且联通的。

栈可以帮助我们保存当前的路径，起点压入栈中，然后每遍历到一个格子就将格子压入栈中。对于某一个格子，如果其不能到达终点，那么我们就无需遍历这个格子的下一个格子了，而这个前缀开头的所有序列都无需再检查，因此被“剪枝”了。这时候，我们可以弹出栈顶元素，回溯到上一个更短的前缀，就像忒修斯的线绳，忒修斯如果走到一个死胡同，就沿着线绳走到上一个位置，然后向着另一个方向继续前进，而栈就相当于这个线绳，记录了来到此处的路径。

每一次前进都算作一次试探，不断试探，回溯，就可以走出迷宫而不至于迷失。

具体的实现看本文的非递归实现。

当然，剪枝是一大类方法，还有\(N\)皇后问题等可以运用剪枝。