数据结构（19）栈和队列的实际应用 目录 1、栈的应用 1.1、栈在括号匹配中的应用 1.2、栈在表达式求值中的应用 1.3、栈在递归中的应用 2、队列的应用 2.1、队列在层次遍历中的应用 2.2、队列在计算机系统中的应用 1、栈的应用 1.1、栈在括号匹配中的应用 假设表达式中允许两种括号：圆括号和方括号，其嵌套的顺序任意即([]())或[([][])]等均为正确的格式，[(])这种交叉的为不正确的格式。 考虑下面括号序列： [ ( [ ] [ ] ) ] 1 2 3 4 5 6 7 8 分析如下： 1）计算机接收第一个“[”后，期待与之匹配的第8个括号“]”出现。 2）获得了第2个括号“(”，此时第一个括号“[”暂时放在一边，而几波期待与之匹配的第7个括号“)”出现。 3）获得了第3个括号“[”，此时第2个括号“(”暂时放在一边，而迫切期待与之匹配的第4个括号“]”出现。第3个括号的期待得到满足，消解之后，第2个括号又成为当前最迫切的任务 4、依次类推。可见该处理过程与栈的思想吻合。 算法的思想如下： 1）初始设置一个空栈，顺序读入括号。 2）若是右括号，则或者使置于栈顶的最急迫期待得以消解，或者使不合法的情况（括号序列不匹配，退出程序）。 3）若是左括号，则作为一个新的更急迫的期待下入栈中，自然使得原油的在栈中的所有未消解的期待的急迫性降了一级，算法正常结束时，栈为空，否则括号序列不匹配。 实例：假设一个算术表达式中包含圆括号、方括号和花括号3种类型的括号 ，编写一个算法来别表达式中的括号是否配对，以字符“0”作为算术表达式的结束符。 1.2、栈在表达式求值中的应用 表达式求值是程序设计语言编译中一个最基本的问题，它的实现是栈应用的一个典范类型。中缀表达式不仅依赖运算符的优先级，而且还要处理括号。后缀表达式的运算符在操作数后面，在后缀表达式中已经考虑了运算符的优先级，没有括号，只有操作数和运算符。中缀表达式A+B*(C-D)-E/F所对应的后缀表达式为ABCD-*+EF/-。 中缀表达式转化为后缀表达式并求值的详细内容见博主的另一篇文章前缀表达式、中缀表达式、后缀表达式。 1.3、栈在递归中的应用 递归是一种重要的程序设计方法。简单地说，若是在一个函数、过程或数据结构的定义中又应用了它本身，则这个函数、过程或数据结构称为是递归定义的，简称递归。 可以参照博主关于斐波那契数列的一些描述和相应代码。 2、队列的应用 2.1、队列在层次遍历中的应用 在信息处理中有一大类问题需要逐层或者逐行处理。这类问题的解决方法往往是在处理当前层或者当前行时就对下一层或下一行做预处理，把处理顺序安排好，待当前层或者当前行处理完毕，就可以处理下一层或下一行。使用队列是为了保存下一步的处理顺序。下面用二叉树层次遍历的例子，说明队列的应用。 
层次遍历二叉树的过程 1）根节点入队。 2）若队空（所有结点都已经处理完毕），则结束遍历；否则重复第3步操作。 3）队列中第一个结点出队，并访问之，若有左孩子，则左孩子入队，若有右孩子，则右孩子入队，返回第2步。 2.2、队列在计算机系统中的应用 队列在计算机系统中的应用非常广泛，以下仅从两个方面来简述队列在计算机系统中的作用：第一个方面是解决主机和外部设备之间速度不匹配问题；第二个方面是解决CPU竞争问题。 对于第一个方面，以主机和打印机之间速度不匹配为例来说明。主机输出数据的速度远远大于打印机的打印速度，所以需要建立一个打印数据缓冲区，主机将数据缓冲区写满了可以去做其他的事情，而这个数据缓冲区就是一个队列。 第二个方面，CPU资源的竞争就是一个典型的例子。像进程切换、线程切换的本质原因就是为了提高CPU的有效利用率。比如有A,B,C三个任务，但是每个任务中间都有IO请求，这样三个进程（或线程）排成一个队列（当然了实际的处理机调度是很复杂的，但是我们这儿可以简化为A先执行，遇到IO换B，依次循环执行，直到所有任务结束），这个过程中，我们看到需要处理机的任务也是一个队列的概念。还有实时交互系统，就是所有任务也是可以简化看作在一个队列中，比如按照时间片去执行这个队列，在用户端呈现出一种实时的多人操作的感官。 你，总要埋头去做一些事情，不是吗
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/69623.html
