文章目录

1. 栈的应用
2. 队列的应用

1. 栈的应用

1.1 括号匹配的问题

1.1.1 匹配的过程分析

从头遍历括号序列，如果是左括号，则不管，如果是右括号，则与最近的一个左括号看是否匹配。而这整个过程是出现一个右括号，该右括号与最近的一个左括号匹配，也就是LIFO，和栈的特点一样。所以，很自然的，我们可以使用栈来实现括号匹配的问题。

其过程如下：

其流程图如下：

1.1.2 算法的实现

1.1.2.1 顺序队列实现

1.1.2.2 链式队列实现

https://blog.csdn.net/qq_43546676/article/details/106003373

1.2 表达式求值问题

1.2.1 表达式求值问题的分析

* 在介绍表达式求值问题之前，我们先介绍几个要用到的名词：
	1. 中缀表达式
	2. 前缀表达式
	3. 后缀表达式
	4. 中缀表达式与后缀表达式的相互转换
	5. 中缀表达式与前缀表达式的相互转换

1.2.1.1 中缀表达式

我们平时计算的式子，实际上使用的就是中缀表达式，比如：

我们计算这个式子的时候，上述的序号就是计算的步骤。

中缀表达式有三部分组成：操作数、运算符、界限符
中缀表达式规则：运算符在两个操作数之间，比如1+2
中缀表达式计算步骤：和我们平时计算一样。

1.2.1.2 后缀表达式(逆波兰表达式)

我们平时在计算几个表达式时使用的是中缀表达式，由操作数、运算符、界限符三部分组成。那么，可不可以不用界限符也能无歧义地表达运算顺序？从而计算表达式？由此，诞生了后缀表达式和前缀表达式，他们都只由操作数、运算符两部分组成。

后缀表达式有两部分组成：操作数、运算符
后缀表达式规则：运算符在两个操作数之后，比如中缀表达式1+2，等价于后缀表达式12+.
后缀表达式的计算：

注意：其实上述后缀表达式的计算过程，就是将后缀表达式转为中缀表达式的过程。

1.2.1.3 前缀表达式(波兰表达式)

前缀表达式有两部分组成：操作数、运算符
前缀表达式规则：运算符在两个操作数之前，比如中缀表达式1+2，等价于后缀表达式+12.
前缀表达式的计算：

注意：其实上述前缀表达式的计算过程，就是将前缀表达式转为中缀表达式的过程。

1.2.1.4 中缀表达式转后缀表达式

首先，需要明确的是客观上一个中缀表达式可以对应多个后缀表达式，比如：

产生这个的主要原因是两个相同运算级，先计算谁。比如A+B+C，先计算A+B还是先计算B+C，导致了生成的后缀表达式不一样，前者是AB+C+，后者是ABC++。

但是，我们需要设计一个求中缀表达式转后缀表达式的算法。而算法必须具有确定性，不能存在歧义。所以，我们必须再规定同级运算的先后计算规则，使得中缀表达式转后缀表达式只有一个对应结果。

上图是前面得到的后缀表达式的一种，可以看到上面的序号是顺序的，比较有规律，运算符生效的次序刚好是顺序的。所以设计算法时，按照这个来：即同级运算时，优先计算左边的，再计算右边的。

这样就解决了算法的确定性问题。

接下来就可以给出中缀表达式转后缀表达式算法的步骤：

注意：

客观上，一个中缀表达式可以对应多个后缀表达式。但是，由于我们需要设计算法，所以，一个中缀表达式只能对应一个后缀表达式。在做题的过程中，默认是一对一的关系，也就是必须是左优先(这一点很关键，一些题目专门利用这一点设计坑)。

中缀表达式转后缀表达式的核心问题就是确定运算符的前后位置/顺序。因为数的顺序是确定的。

要检查中缀表达式转后缀表达式是否正确，可以看转换后的后缀表达式从左到右运算符是不是依次生效。

1.2.1.5 中缀表达式转前缀表达式

这个也会遇到与中缀表达式转后缀表达式相同的问题，解决方法相同。

所以，得到中缀表达式转前缀表达式算法的步骤：

注意：

中缀表达式转前缀表达式的核心问题也是确定运算符的前后位置/顺序。因为数的顺序是确定的。

要检查中缀表达式转前缀表达式是否正确，可以看转换后的前缀表达式从右到左运算符是不是依次生效。

1.2.1.6 表达式求值问题的分析

通过上述知识点阐述，表达式求值问题的问题就很容易解决了。很容易想到，先将中缀表达式转为后缀/前缀表达式，再对后缀/前缀表达式求解，就可以得到表达式的值。

那么，现在我们面临着两个问题：

使用什么数据结构实现中缀表达式转为后缀/前缀表达式。
使用什么数据结构实现后缀/前缀表达式求解。

1.2.1.6.1 使用什么数据结构实现中缀表达式转为后缀/前缀表达式

我们来看先来解决第一个问题。

我们可以想想，在之前描述手写中缀表达式转为后缀/前缀表达式的过程中有什么特点？我们可以通过下面一张图回忆一下：

我们可以发现，这个过程就是在从左往右的扫描中缀表达式，根据当前的运算符优先级确定其前面最近的一个运算符是否可以被优先计算，如果是就将其添在后缀表达式的尾部，不是则继续扫描。

整个过程就是根据当前的运算符，判断前面最近的运算符。这个特点就是后进先出，由此，我们可以使用栈来实现中缀表达式转后缀/前缀表达式。

中缀表达式转后缀表达式的具体步骤如下图所示：

中缀表达式转前缀表达式的具体步骤如下图所示：

1.2.1.6.2 使用什么数据结构实现后缀/前缀表达式求解

接着，我们来看第二个问题：使用什么数据结构实现后缀/前缀表达式求解。

通过上图可以看出，每个操作符取前面最近的两个操作数进行运算，很明显特点是后进先出。因此，后缀表达式的求值算法，可以利用栈来实现。同理，前缀表达式也可以用栈来求值，求值步骤如下：

这样，我们就在理论上解决了表达式求值问题。