数据结构—–队列应用

导读:本篇文章讲解 数据结构—–队列应用,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com

队列应用—–树的层次遍历:

如下图所示为一个树:

分为四层,我们在遍历的时候是根据层次进行遍历的
在这里插入图片描述遍历的过程是,从左向右遍历,将新的元素放在队尾,访问对头元素,遍历完一个节点的左右节点之后,该节点出队。

具体过程如下:

对一号结点进行遍历:
在这里插入图片描述遍历完1号结点之后,1号结点出队。

此时对头节点变成2号结点,因此将2号结点的左右节点插入队尾。

在这里插入图片描述
2号结点遍历完成后,出队。

此时对头节点变成3号结点,因此将3号结点的左右节点插入队尾。
在这里插入图片描述遍历完3号结点之后,3号结点出队。

下面遍历4号结点,由于4号结点没有左右节点,因此直接出队,遍历下一个节点,重复进行上述操作,直至遍历完所有的节点。
队列的应用—–图的广度优先遍历。

队列应用——图的广度优先遍历:

如下图所示为一个图:

图的遍历方式和树有些相似,只是这里并不是依次访问左右节点,而是将和它相连的节点插入队尾。
在这里插入图片描述具体过程如下:

访问一号结点:

与它相联着的有2号和3号结点。
在这里插入图片描述然后1号结点出队。

和树一样接下来访问对头元素,2号结点。

在这里插入图片描述然后2号结点出队。

然后访问3号结点,和3号结点相连的有1,5,6,但是由于1号结点已经访问过了,因此只需要将剩下的两个节点插入队尾。

在这里插入图片描述
依次类推,直至访问完所有的节点。

队列在操作系统中的应用:

多个进程争抢着使用有限的系统资源,FCFS(first come first service先来先服务)是一种常用策略。

举例:

CPU资源的分配:
在这里插入图片描述在举一个生活中常见的例子:

打印数据缓冲区:

场景:去学校打印店打印论文,多个同学用同一台打印机打印,打印的先后顺序如何?

假设有一位同学,他需要打印论文,但是由于论文很长,需要一定时间去打印,因此在打印机为该同学工作的过程中,打印数据的缓冲区就会将其他同学要打印的内容组成一个“队列”。

因为打印机打印的速度远低于主机的速度,因为这样一来,也可缓解主机与打印机速度不匹配的问题。
在这里插入图片描述

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/81443.html

(0)
小半的头像小半

相关推荐

极客之音——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!