栈与队列的应用
栈在括号匹配中的应用
提示
观察这个序列：
[ ( [ ] [ ] ) ]
12345678
分析思路：
- 计算机接受1号
[后，期待与之匹配的]在8号位置出现 - 获得2号
(后，此时[暂时搁置，而期待与之匹配的)在7号位置出现 - 获得3号
[后，(也同样搁置，期待与之匹配的]在4号位置出现，这时3号得到满足，我们就进行一次消解，现在当前最急迫的任务回到(上。 - ……
不难看出，以上思路与栈的思想相契合，因此我们使用栈来解决括号匹配的问题。
问题：假设表达式中允许包含两种括号，为()和[]，请设计一个算法来检测字符串中的括号是否匹配。
算法思想
- 初始设置一个空栈，按照顺序读入括号。
- 若遇到右括号，则先读取栈顶元素，与该右括号进行匹配：若匹配，则进行一次出栈操作；否则返回
不匹配的结果。 - 若遇到左括号，则进行一次入栈操作。
- 若遍历完字符串后栈为空则返回
匹配结果，否则返回不匹配的结果。
算法实现
栈在表达式求值中的应用
我们平日中使用中缀表达式来表达运算，但在计算机中如果直接使用则不仅要考虑运算符优先级，而且要处理括号，这样对求值会复杂很多。因此我们使用后缀表达式或者前缀表达式来代替中缀表达式，因为它们本身已经考虑了运算的优先级顺序，且没有括号，仅有操作数和运算符。
中缀表达式转换为前/后缀表达式
算法思想：
算法实现：
算法思想：
算法实现：
后缀表达式求值
算法思想：
- 顺序扫描表达式的每一项，然后判断它的类型。
- 若判断为操作数，则将其压入栈中。
- 若判断为操作符，则从栈中弹出两个操作数形成运算指令，并将计算结果重新压入栈中。
- 当所有项都扫描并处理完成后，所得的就是表达式的计算结果。
算法实现：
前缀表达式求值
算法思想：与后缀表达式求值的思路类似，但是要按照前缀表达式的计算顺序，因此也是从右向左遍历前缀表达式来求值。
算法实现：
栈在递归中的应用
将递归算法转化为非递归算法，就需要用到栈来实现。
队列在层次遍历中的应用
在信息处理中有一大类问题需要逐层或逐行处理，这类问题的解决办法往往是在处理当前层或当前行时就对下一层或下一行进行预处理，吧处理顺序安排好，等到当前层或当前行处理完毕，就可以处理下一层或下一行。而我们使用队列是为了保存下一步的处理顺序。
以二叉树层次遍历为例，该过程的算法思路是：
- 根节点入队
- 队列中第一个结点出队并访问，若其有左孩子则左孩子入队；若其有右孩子则将右孩子入队。
- 若队空（此时所有结点都已经处理完毕），则结束遍历，否则重复步骤2。
队列在计算机系统中的应用
队列在计算机系统中应用十分广泛，以下面两个方面为例来简述队列在其中的作用：
解决主机与外部设备之间速度不匹配的问题
以主机与打印机之间速度不匹配的问题为例：主机输出的速度远比打印机打印速度快得多，如果直接将输出数据送给打印机打印就必然会造成数据部分丢失，为了避免这种问题，就需要设计一个打印数据缓冲区，主机将输出数据写入这个缓冲区，写满之后暂停输出转去做其他事情，而打印机从缓冲区中按照先进先出的原则读取数据并打印，打印完成之后再向主机发出请求，主机受到请求后再向缓冲区写入接下来的打印数据。
这样做既保证了打印数据的正确性，又提高了主机的效率。而上述过程中所使用的缓冲区实质上就是一个队列。
解决由多用户引起的资源竞争问题
以CPU资源竞争为例，在一台带有多终端的计算机系统上，有多个用户需要CPU各自运行自己的程序，他们分别通过各自的终端向操作系统提出占用CPU的请求。操作系统通常按照每个请求在时间上的先后顺序（也可以是以某种标准排列的顺序）把它们排成一个队列，每次把CPU分配给队首请求的用户使用。当相应程序运行结束或者用完规定的时间间隔后令其出队（程序未执行完的情况下会再次发送请求），再把CPU分配给新的队首请求的用户使用。
这样技能满足每个用户的请求，又使CPU能够正常运行。