栈的经典应用例子

1、括号匹配

http://www.noobdream.com/Major/article/124/

2、表达式求值

前缀、中缀、后缀表达式

前缀、中缀、后缀表达式是对表达式的不同记法，其区别在于运算符相对于操作数的位置不同，前缀表达式的运算符位于操作数之前，中缀和后缀同理

举例：
中缀表达式：1 + (2 + 3) × 4 - 5
前缀表达式：- + 1 × + 2 3 4 5
后缀表达式：1 2 3 + 4 × + 5 -

中缀表达式
中缀表达式是一种通用的算术或逻辑公式表示方法，操作符以中缀形式处于操作数的中间。中缀表达式是人们常用的算术表示方法。 虽然人的大脑很容易理解与分析中缀表达式，但对计算机来说中缀表达式却是很复杂的，因此计算表达式的值时，通常需要先将中缀表达式转换为前缀或后缀表达式，然后再进行求值。对计算机来说，计算前缀或后缀表达式的值非常简单。

前缀表达式

前缀表达式的运算符位于两个相应操作数之前，前缀表达式又被称为前缀记法或波兰式

前缀表达式的计算机求值

1. 从右至左扫描表达式
2. 遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 op 次顶元素），并将结果入栈
3. 重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果

示例：
计算前缀表达式的值：- + 1 × + 2 3 4 5

1. 从右至左扫描，将5，4，3，2压入堆栈；
   2）遇到+运算符，弹出2和3（2为栈顶元素，3为次顶元素），计算2+3的值，得到5，将5压入栈；
   3）遇到×运算符，弹出5和4，计算5×4的值，得到20，将20压入栈；
   4）遇到1，将1压入栈；
   5）遇到+运算符，弹出1和20，计算1+20的值，得到21，将21压入栈；
   6）遇到-运算符，弹出21和5，计算21-5的值，得到16为最终结果

可以看到，用计算机计算前缀表达式是非常容易的，不像计算后缀表达式需要使用正则匹配

后缀表达式

后缀表达式与前缀表达式类似，只是运算符位于两个相应操作数之后，后缀表达式也被称为后缀记法或逆波兰式

后缀表达式的计算机求值

与前缀表达式类似，只是顺序是从左至右：

1. 从左至右扫描表达式
2. 遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素op 栈顶元素 ），并将结果入栈
3. 重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果

示例：
计算
计算后缀表达式的值：1 2 3 + 4 × + 5 -

1）从左至右扫描，将1，2，3压入栈；
2）遇到+运算符，3和2弹出，计算2+3的值，得到5，将5压入栈；
3）遇到4，将4压入栈
4）遇到×运算符，弹出4和5，计算5×4的值，得到20，将20压入栈；
5）遇到+运算符，弹出20和1，计算1+20的值，得到21，将21压入栈；
6）遇到5，将5压入栈；
7）遇到-运算符，弹出5和21，计算21-5的值，得到16为最终结果

中缀表达式转化为前缀和后缀表达式

转化步骤：

1. 按照运算符的优先级对所有的运算单位加括号
2. 将运算符移动到对应括号...

课后习题

【2016年真题】设有如下图所示的火车车轨，入口到出口之间有n条轨道，列车的行进方向均为从左至右，列车可驶入任意一条轨道。现有编号为1~9的9列列车，驶入的次序依次是8,4,2,5,3,9,1,6,7。若期望驶出的次序依次为1~9，则n至少是

A.2            B.3            C.4            D.5

参考答案：C

【2011年真题】已知循环队列存储在一维数组A[0...n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是（）
A．0,0
B．0，n-1 
C．n-1,0
D．n-1，n-1 

参考答案：B
答案解析：插入元素时，front不变，rear+1.而插入第一个元素之后，队尾要指向尾元素，显然，rear初始应该为n-1,front为0。

【2014年真题】假设栈初始为空，将中缀表达式 a/b+(c*d-e*f)/g 转换为等价的后缀表达式的过程中，当扫描到 f 时，栈中的元素依次是（）
A．+ ( * -         B．+ ( - *         C．/ + ( * - *         D．/ + - * 

参考答案：B
答案解析：将中缀表达式转换为后缀表达式的算法思想如下： 
从左向右开始扫描中缀表达式； 
遇到数字时，加入后缀表达式； 
遇到运算符时： 
a. 若为 '('，入栈； 
b. 若为 ')'，则依次把栈中的的运算符加入后缀表达式中，直到出现'('，从栈中删除'(' ； 
c. 若为除括号外的其他运算符， 当其优先级高于除'('以外的栈顶运算符时，直接入栈。 
否则从栈顶开始，依次弹出比当前处理的运算符优先级高和优先级相等的运算符，直到一个 
比它优先级低的或者遇到了一个左括号为止。 
当扫描的中缀表达式结束时，栈中的所有运算符依次出栈加入后缀表达式。 

由此可知，当扫描到 f 的时候，栈中的元素依次是+(-*，选 B。 
在此，再给出中缀表达式转换为前缀或后缀表达式的一种手工做法，以上面给出的中缀 
表达式为例： 
第一步：按照运算符的优先级对所有的运算单位加括号。 
式子变成了：((a/b)+(((c*d)-(e*f))/g)) 
第二步：转换为前缀或后缀表达式。 
前缀：把运算符号移动到对应的括号前面，则变成了：+(/(ab)/(-(*(cd)*(ef))g)) 
把括号去掉：+/ab/-*cd*efg 前缀式子出现。 
后缀：把运算符号移动到对应的括号后面，则变成了：((ab)/(((cd)*(ef)*)-g)/)+ 
把括号去掉：ab/cd*ef*-g/+ 后缀式子出现。 
当题目要求直接求前缀或后缀表达式时，这种方法会比上一种快捷得多。

【2012年真题】已知操作符包括"+"、"-"、"*"、"/"、"("和")"。将中缀表达式 a+b-a*((c+d)/e-f)+g 转换为等价的后缀表达式 ab+acd+e/f-*-g+时，用栈来存放暂时还不能确定运算次序的操作符，若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是（）
A．5 
B．7 
C．8 
D．11

参考答案：A
答案解析：考查栈的应用、表达式求值。 
表达式求值是栈的典型应用。通常涉及中缀表达式和后缀表达式。中缀表达式不仅依赖运算符的优先级，还要处理括号。后缀表达式的运算符在表达式的后面且没有括号，其形式已经包含了运算符的优先级。所以从中缀表达式转换到后缀表达式需要用运算符栈对中缀表达式进行处理，使其包含运算法优先级的信息，从而转换为后缀表达式的形式。转换过程如下表：

【2019年真题】请设计一个队列，要求满足：①初始时队列为空；②入队时，允许增加队列占用空间；③出队后，出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减；④人队操作和出队操作的时间复杂度始终保持为O(1)。请回答下列问题：
(1) 该队列应该选择链式存储结构，还是顺序存储结构？
(2) 画出队列的初始状态，并给出判断队空和队满的条件
(3) 画出第一个元素入队后的队列状态。
(4) 给出入队操作和出队操作的基本过程。

参考答案
(1)采用链式存储结构(两段式单向循环链表)，队头指针为front，队尾指针为rear。
(2)初始时，创建只有一个空闲结点的两段式单向循环链表，头指针front与尾指针rear均指向空闲结点。如下图所示。

队空的判定条件：front==rear。
队满的判定条件：front==rear->next。
(3)插入第一个元素后的队列状态：

(4)操作的基本过程：

【2018年真题】现有队列    Q 与栈 S，初始时Q 中的元素依次是1, 2, 3, 4, 5, 6（ 1 在队头），S 为空。若仅允许下列 3 种操作：①出队并输出出队元素；②出队并将出队元素人栈；③出栈并输出出栈元素，则不能得到的输出序列是（）。    
A . 1, 2, 5, 6, 4, 3            B. 2, 3, 4, 5, 6, 1
C.3, 4, 5, 6, 1, 2            D. 6, 5, 4, 3, 2, 1

参考答案：C