2.8 栈和队列的应用

2.8.1 栈的应用

栈在括号匹配中的应用

1. 初始设置一个空栈，顺序读入括号
2. 若是右括号，则或者置于栈顶的最急迫期待得以消解，或者是不合法的情况
3. 若是左括号，则作为一个新的更急迫的期待压入栈中
4. 算法结束时，栈为空，否则括号序列不匹配

表达式求值(中缀表达式求值)

三种表达式：中缀表达式、后缀表达式、前缀表达式

中缀表达式：有界限符

后缀和前缀表达式：无界限符

注：方法一和方法二都是分开的，分为两步

方法一：中缀表达式转后缀表达式，再用后缀表达式求值

1. 中缀表达式转后缀表达式（用栈保存运算符）

中缀表达式从左往右扫描：

①遇到操作数，直接压入栈。

②遇到界限符，遇到“（”，直接压入栈；遇到“）”，依次弹出栈内运算符从左往右加入表达式，直到弹出“（”结束。

③遇到运算符，依次弹出比这个运算符优先级高的所有运算符，将此运算符压入栈。

2. 后缀表达式求值（用栈存运算结果）

后缀表达式从左往右扫描：

①遇到操作数，直接压入栈。

②遇到运算符，弹出两个元素，执行相应运算，将运算结果压回栈顶

方法二：中缀表达式转前缀表达式，再用前缀表达式求值

1. 中缀表达式转前缀表达式（用栈保存运算符）

中缀表达式从右往左扫描：

①遇到操作数，直接压入栈。

②遇到界限符，遇到“（”，直接压入栈；遇到“）”，依次弹出栈内运算符从右往左加入表达式，直到弹出“（”结束。

③遇到运算符，依次弹出比这个运算符优先级高的所有运算符，将此运算符压入栈。

2. 前缀表达式求值（用栈存运算结果）

前缀表达式从右往左扫描：

①遇到操作数，直接压入栈。

②遇到运算符，弹出两个元素，执行相应运算，将运算结果压回栈顶

递归

可以将递归算法转换为非递归算法。通常需要借助栈来实现这种转换

2.8.2 队列的应用

1. 树的层次遍历

2. 图的广度优先遍历

3. 操作系统中的应用

多个进程争抢有限的系统资源时，采用先来先服务算法(FCFS)

例子：CPU资源分配；打印数据缓冲区