
栈是“后进先出”(LIFO,Last InFirst Out)的数据结构,与之相反,队列是“先进先出”(FIFO,First InFirst Out)的数据结构。
队列的作用就像售票口前的人们站成的一排一样:第一个进入队列的人将最先买到票,最后排队的人最后才能买到票。
在计算机操作系统或网路中,有各种队列在安静地工作着。打印作业在打印队列中等待打印。当敲击键盘时,也有一个存储键盘键入内容的队列,如果我们敲 击了一个键,而计算机又暂时在做其他事情,敲击的内容不会丢失,它会排在队列中等待,直到计算机有时间来读取它,利用队列保证了键入内容在处理时其顺序不 会改变。
栈的插入和删除数据项的命名方法很标准,成为push和pop,队列的方法至今也没有一个标准化的方法,插入可以称作put、add或enque等,删除可以叫作delete、get、remove或deque等。
下面我们依然使用数组作为底层容器来实现一个队列的操作封装,与栈不同的是,队列的数据项并不都是从数组的第一个下标开始,因为数据项在数组的下标越小代表其在队列中的排列越靠前,移除数据项只能从队头移除,然后队头指针后移,这样数组的前几个位置就会空出来如下图所示:
这与我们的直观感觉相反,因为我们排队买票时,队列总是向前移动,当前面的人买完票离开后,其他人都向前移动,而在我们的设计中,队列并没有向前移动,因为那样做会使效率大打折扣,我们只需要使用指针来标记队头和队尾,队列发生变化时,移动指针就可以,而数据项的位置不变。
但是,这样的设计还存在着一个问题,随着队头元素不断地移除,数组前面空出的位置会越来越多,当队尾指针移到最后的位置时,即使队列没有满,我们也不能再插入新的数据项了。
解决这种缺点的方法是环绕式处理,即让队尾指针回到数组的第一个位置:
这就是循环队列(也成为缓冲环)。虽然在存储上是线形的,但是在逻辑上它是一个首尾衔接的环形。
还有一种称为双端队列的数据结构,队列的每一端都可以进行插入和移除操作。
其实双端队列是队列和栈的综合体。如果限制双端队列的一段只能插入,而另一端只能移除,就变成了平常意义上的队列;如果限制双端队列只能在一端进行插入和移除,就变成了栈。
像普通队列一样,优先级队列有一个队头和一个队尾,并且也是从队头移除数据,从队尾插入数据,不同的是,在优先级队列中,数据项按关键字的值排序,数据项插入的时候会按照顺序插入到合适的位置。
除了可以快速访问优先级最高的数据项,优先级队列还应该可以实现相当快的插入,因此,优先级队列通常使用一种称为堆的数据结构来实现。在下例中,简便起见,我们仍然使用数组来实现
在数据项个数比较少,或不太关心速度的情况下,用数组实现优先级队列还可以满足要求,如果数据项很多,或对速度要求很高,采用堆是更好的选择
优先级队列的实现跟上面普通队列的实现有很大的区别。
优先级队列的插入本来就需要移动元素来找到应该插入的位置,所以循环队列那种不需要移动元素的优势就不太明显了。在下例中,没有设置队头和队尾指 针,而是使数组的第一个元素永远是队尾,数组的最后一个元素永远是队头,为什么不是相反的呢?因为队头有移除操作,所以将队头放在数组的末端,便于移除, 如果放在首段,每次移除队头都需要将队列向前移动。
插入元素示意图
移除元素示意图
在下例中,我们设置了一个基准点,认为元素到里基准点的距离越近则优先级越高,如设置的基准点为2,3到2的距离就是|3-2|=1,而-1到2的距离是|-1-2|=3,所以2的优先级就比-1要高。
数据分析咨询请扫描二维码
若不方便扫码,搜微信号:CDAshujufenxi
CDA 数据分析师报考条件详解与准备指南 在数据驱动决策的时代浪潮下,CDA 数据分析师认证愈发受到瞩目,成为众多有志投身数 ...
2025-07-18刚入职场或是在职场正面临岗位替代、技能更新、人机协作等焦虑的打工人,想要找到一条破解职场焦虑和升职瓶颈的系统化学习提升 ...
2025-07-182025被称为“AI元年”,而AI,与数据密不可分。网易公司创始人丁磊在《AI思维:从数据中创造价值的炼金术 ...
2025-07-18CDA 数据分析师:数据时代的价值挖掘者 在大数据席卷全球的今天,数据已成为企业核心竞争力的重要组成部分。从海量数据中提取有 ...
2025-07-18SPSS 赋值后数据不显示?原因排查与解决指南 在 SPSS( Statistical Package for the Social Sciences)数据分析过程中,变量 ...
2025-07-18在 DBeaver 中利用 MySQL 实现表数据同步操作指南 在数据库管理工作中,将一张表的数据同步到另一张表是常见需求,这有助于 ...
2025-07-18数据分析师的技能图谱:从数据到价值的桥梁 在数据驱动决策的时代,数据分析师如同 “数据翻译官”,将冰冷的数字转化为清晰的 ...
2025-07-17Pandas 写入指定行数据:数据精细化管理的核心技能 在数据处理的日常工作中,我们常常需要面对这样的场景:在庞大的数据集里精 ...
2025-07-17解码 CDA:数据时代的通行证 在数字化浪潮席卷全球的今天,当企业决策者盯着屏幕上跳动的数据曲线寻找增长密码,当科研人员在 ...
2025-07-17CDA 精益业务数据分析:数据驱动业务增长的实战方法论 在企业数字化转型的浪潮中,“数据分析” 已从 “加分项” 成为 “必修课 ...
2025-07-16MySQL 中 ADD KEY 与 ADD INDEX 详解:用法、差异与优化实践 在 MySQL 数据库表结构设计中,索引是提升查询性能的核心手段。无论 ...
2025-07-16解析 MySQL Update 语句中 “query end” 状态:含义、成因与优化指南 在 MySQL 数据库的日常运维与开发中,开发者和 DBA 常会 ...
2025-07-16如何考取数据分析师证书:以 CDA 为例 在数字化浪潮席卷各行各业的当下,数据分析师已然成为企业挖掘数据价值、驱动决策的 ...
2025-07-15CDA 精益业务数据分析:驱动企业高效决策的核心引擎 在数字经济时代,企业面临着前所未有的数据洪流,如何从海量数据中提取有 ...
2025-07-15MySQL 无外键关联表的 JOIN 实战:数据整合的灵活之道 在 MySQL 数据库的日常操作中,我们经常会遇到需要整合多张表数据的场景 ...
2025-07-15Python Pandas:数据科学的瑞士军刀 在数据驱动的时代,面对海量、复杂的数据,如何高效地进行处理、分析和挖掘成为关键。 ...
2025-07-15用 SQL 生成逆向回滚 SQL:数据操作的 “后悔药” 指南 在数据库操作中,误删数据、错改字段或误执行批量更新等问题时有发生。 ...
2025-07-14t检验与Wilcoxon检验的选择:何时用t.test,何时用wilcox.test? t 检验与 Wilcoxon 检验的选择:何时用 t.test,何时用 wilcox. ...
2025-07-14AI 浪潮下的生存与进阶: CDA数据分析师—开启新时代职业生涯的钥匙(深度研究报告、发展指导白皮书) 发布机构:CDA数据科 ...
2025-07-13LSTM 模型输入长度选择技巧:提升序列建模效能的关键 在循环神经网络(RNN)家族中,长短期记忆网络(LSTM)凭借其解决长序列 ...
2025-07-11