队列应用—–树的层次遍历:
如下图所示为一个树:
分为四层,我们在遍历的时候是根据层次进行遍历的
遍历的过程是,从左向右遍历,将新的元素放在队尾,访问对头元素,遍历完一个节点的左右节点之后,该节点出队。
具体过程如下:
此时对头节点变成2号结点,因此将2号结点的左右节点插入队尾。
此时对头节点变成3号结点,因此将3号结点的左右节点插入队尾。
遍历完3号结点之后,3号结点出队。
下面遍历4号结点,由于4号结点没有左右节点,因此直接出队,遍历下一个节点,重复进行上述操作,直至遍历完所有的节点。
队列的应用—–图的广度优先遍历。
队列应用——图的广度优先遍历:
如下图所示为一个图:
图的遍历方式和树有些相似,只是这里并不是依次访问左右节点,而是将和它相连的节点插入队尾。
具体过程如下:
访问一号结点:
和树一样接下来访问对头元素,2号结点。
然后访问3号结点,和3号结点相连的有1,5,6,但是由于1号结点已经访问过了,因此只需要将剩下的两个节点插入队尾。
队列在操作系统中的应用:
多个进程争抢着使用有限的系统资源,FCFS(first come first service先来先服务)是一种常用策略。
举例:
打印数据缓冲区:
场景:去学校打印店打印论文,多个同学用同一台打印机打印,打印的先后顺序如何?
假设有一位同学,他需要打印论文,但是由于论文很长,需要一定时间去打印,因此在打印机为该同学工作的过程中,打印数据的缓冲区就会将其他同学要打印的内容组成一个“队列”。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/81443.html