栈的应用

栈和队列

栈：限定在表尾进行插入和删除的线性表

队列：只允许在一端进行插入操作，而在另一端进行删除操作的线性表

链栈与顺序栈相比，一个明显的优点是通常不会出现栈满的情况

循环队列满的条件是：（rear +1) % QueueSize == front

循环队列长度计算公式：（rear - front + QueueSize) % QueueSize

栈满的时候要考虑上溢的情况，栈空的时候要考虑下溢的情况。

表达式

主要总结考试常见的表达式求值的形式

一、中缀表达式快速转前缀和后缀

一般是给你一个中缀表达式，要求你快速写出它的后缀或者前缀形式。具体步骤如下：

1、加括号

原则：每个操作符连接的两个表达式两边加上括号，加上括号后看做一个新的表达式参与后面的运算。应保证加上括号后不改变原先的计算顺序

2、转前缀

操作数不变，将操作符移到包含这个操作符连接的两个表达式的最近的括号的前边。

3、转后缀

操作数不变，将操作符移到包含这个操作符连接的两个表达式的最近的括号的后边。

操作	形式
中缀表达式	a / b + ( c * d - e * f ) / g
加括号	( ( a / b ) + ( ( ( c * d ) - ( e * f ) ) / g ) )
前缀表达式	+ / a b / - * c d * e f g
后缀表达式	a b / c d * e f * - g / +

二、中缀转后缀——使用一个操作符栈

我们假设最后的结果直接打印输出到屏幕中，如果想要保存后缀表达式只需要创建一个数组或者其他数据结构接收结果即可。下面规则只考虑到了左右小括号( 和 )

规则：从左到右遍历中缀表达式的每个数字和符号，

1. 若是数字就输出，即成为后缀表达式的一部分；
2. 如果操作符栈为空，或者栈顶是左括号，或者当前扫描到的元素是左括号。直接将当前符号进栈。
3. 如果是右括号，则依次弹出栈顶元素，弹出的元素成为后缀表达式的一部分，直到遇到左括号。最后将左括号弹出栈。
4. 如果是中缀表达式的结束符（比如：\0，也可以自定义结束符），或者优先级小于或等于栈顶元素，则依次弹出栈顶元素，弹出的元素成为后缀表达式的一部分。直到操作符栈为空，或者遇到左括号。最后将当前符号进栈。
5. 其他情况是当前符号优先级高于栈顶元素，直接将符号进栈。

Notes：

上面是按照实际编程写的步骤，所以一些细节也都考虑进去了，显得有点多。再简单描述一下思路：

先考虑数字 => 考虑左括号 => 考虑右括号 => 考虑优先级小于等于栈顶元素 => 考虑优先级大于栈顶元素 => 最后中缀表达式结束合并到第四步，因为二者操作相同。

实战演练

中缀表达式：3 - 2 + ( 5 * 5 - 4 * 4 ) / 3

三、后缀表达式求值——使用一个操作数栈

首先创建一个操作数栈

规则：从左到右扫描所给的后缀表达式的每个数字和操作符

• 遇到数字就进栈；
• 遇到操作符就将处于栈顶的两个数字出栈进行运算，先弹出来的数字放在操作符后面，后弹出来的放在前面，运算结果再次进栈。
• 一直到扫描完毕，栈中最后的数字就是运算结果。

实战演练

**后缀表达式： 3 2 - 5 5 * 4 4 * - 3 / + **

四、中缀表达式求值——使用两个栈：操作数栈和操作符栈

中缀表达式求值可以转化为先转成后缀表达式，然后再对后缀表达式求值。所以这部分可以说是前面的综合应用。所以规则也是两者的结合

首先创建操作符栈和操作数栈。

规则：从左到右扫描所给的后缀表达式的每个数字和操作符

• 遇到数字就进操作数栈。
• 遇到操作符，进操作符栈的规则和中缀转后缀一样。唯一不同的是，只要从操作符栈弹出操作符，就必须从操作数栈弹出两个元素参与运算，运算结果再次进操作数栈。注意，先弹出来的操作数放在后面。
• 最后，操作数栈就是一个元素，就是计算结果。

实战演练

中缀表达式：3 - 2 + ( 5 * 5 - 4 * 4 ) / 3

五、了解前缀和后缀如何转中缀

都是利用一个栈来实现，这里设定栈是string类型的，可以存放表达式

后缀转中缀

实战演练

后缀表达式：a b / c d * e f * - g / +

前缀转中缀

实战演练

前缀表达式：+ / a b / - * c d * e f g

六、参考

• 数据结构精讲与习题详解--殷人昆
• 大话数据结构--程杰
• 408历年真题