队列是一种高效的结构,它的起源已无法追溯,被广泛运用于生活与数学应用中。就比如上面的翠园食堂排队(高一同学可以不要跑步去食堂吗:joy:
那么,这种结构在数字计算机中存在吗?
答案是:存在!
队列(queue)是一种特殊的线性结构,它只允许在队列的首部(head)进行删除操作,这称为“出队”,而在队列的尾部(tail)进行插入操作,这称为“入队”。当队列中没有元素时,称为空队列(empty queue)。在我们的日常生活中有很多情况都符合队列的特性。比如我们之前提到过的食堂干饭,每个打饭的窗口就是一个队列。在这个队列当中,新来的人总是站在队列的最后面,来得越早的人越靠前,也就越早能吃到饭,就是先来的人先服务,我们称为“先进先出”(First In First Out,FIFO)原则。
队列操作
队列是广度优先搜索中的重要数据结构。除了本文介绍的这种队列之外,还有一种队列,叫环形队列。这种队列首尾相接,如下图所示。

(关于环形队列,可参阅[1]环形队列

头图来自翠园中学学长团;
队列操作流程图来自https://zhuanlan.zhihu.com/p/138523723;
部分文字摘编自《啊哈!算法》。

最后修改日期: 2022年6月24日

作者

0 0 投票数
文章评分
订阅评论
提醒
0 评论
内联反馈
查看所有评论