数据结构与算法

数据结构与算法知识详解
帅旋
关注
充电
IT宅站长,技术博主,架构师,全网id:arthinking。

队列数据结构

发布于 2020-04-28 | 更新于 2024-05-16

6、队列

队列是一种线性数据结构,它通过执行两个主要操作(即入队enqueue和出队dequeue)来对现实世界中的队列进行建模。

6.1、术语

image-20200412095233658

  • Dequeue:出队,类似命名:Polling
  • Enqueue:入队,类似命名:Adding,Offering
  • Queue Front:对头
  • Queue Back:队尾

队列底层可以使用数组或者链表实现

6.2、使用场景

  • 任何排队等候的队伍都可以建模为Queue,例如在电影院里的队伍;
  • 可用于有效地跟踪最近添加的x个元素;
  • 用于Web服务器请求管理,保证服务器先接受的先处理;
  • 图的广度优先搜索(BFS)。

6.2.1、请用队列实现图的广度优先遍历

提示:

image-20200412103414505

遍历顺序:0 -> 2, 5 -> 6 -> 1 -> 9, 3, 2, 7 -> 3, 4, 8, 9

6.3、时间复杂度

操作 时间复杂度
入队 O(1)
Dequeue O(1)
Peeking O(1)
Contains O(n)
Removal O(n)
isEmpty O(1)

6.4、编程实践

本文作者: 帅旋

本文链接: https://www.itzhai.com/columns/dsa/queue.html

版权声明: 版权归作者所有,未经许可不得转载,侵权必究!联系作者请加公众号。

×
IT宅

关注公众号及时获取网站内容更新。

请帅旋喝一杯咖啡

咖啡=电量,给帅旋充杯咖啡,他会满电写代码!

IT宅

关注公众号及时获取网站内容更新。