1. 概念

        队列:其实就是排队。像我们在银行窗口取钱、车站买车票等都可以叫队列。
        特点:队列只允许在后端(rear)进行插入操作,在前端(front)进行删除操作(即先进先出,FIFO, First-In-First-Out, 跟stack正好相反。简单来说就是谁先来先给谁办理业务,后来的人在队伍后面排队,不允许插队。
在这里插入图片描述
(上图来源:wiki)
在这里插入图片描述

2. 实现方式

1> 单链表
① 优点:链表有头指针和尾指针,这正好满足了队列的条件(只需要处理头(前端)和尾(后端),一个删除,一个插入)
② 缺点:没有index这个概念,查询中间任意一个节点的数值,都需要遍历链表,时间复杂度是O(n)
③ 使用链表实现队列的条件:只顾头尾,甚至只顾头(例如:银行办理业务时谁先来先办理谁的,不会说先挨个问一下每个人办理什么业务,突然让某个人插个队或者说因为队伍最后一个人前面的人太多,就先给最后那个人办理)
2> 动态数组
① 优点:有index这个概念,查询数组中间任意一个下标的元素,时间复杂度是O(1)。(例如:现在办理业务时,有位老人已经等很久了,考虑到老人的身体状况,可能会叫一下那个老人手中的号,先给老人办理)
② 缺点:每删除一个array[0]的元素都是o(n)的时间复杂度(因为数组中有补位这个概念的存在),不适合庞大的队伍。除此之外,如果扩容,还需要考虑复杂度震荡的问题。

3. 复杂度

在这里插入图片描述
                                        (图片来源:wiki)
① search(搜索某个元素):无论链表还是数组都需要遍历,因此平均和最差时间复杂度都是O(n)
注:搜索:给定元素判断有无或者找下标;查询:给定下标找元素
② insert:都是从后端直接插入,因此平均和最差时间复杂度都是o(1)
③ delete:都是从前端直接删除(数组先不考虑后续的补位,只说删除这个操作),因此平均和最差时间复杂度都是o(1)

其他

search:好像指的是搜索
query:指的查询
peek:常用于stack或者queue查看最顶端(或最前面)的元素

4. 实际应用

① 操作系统中的进程管理:可以控制进程执行的优先级(例如(大概过程,实际情况比这个复杂):后台同时挂着游戏和工作软件,现在想打游戏,就把游戏放在首位,CPU、显卡等硬件都先给它用;过了一会发现工作快到上交的截止日期了,马上把工作再放到首位,CPU、显卡等硬件都先给工作用。由此可见打游戏、工作这些事情可以被看作一个队伍。在计算机中,这些任务都是随机的,需要把它们存储到一个队列当中来表示它们的优先级顺序)
② 搜索算法中的广度优先算法
③ 网络编程中的缓存网络数据包:可以控制队列数据的传输速度
④ 计算机图形学中三维场景的遮挡剔除:可以提高图形的渲染效率
        由此可见,队列在计算机系统中非常重要(着重强调系统级),尤其是任务调度、进程管理方面,目的就是为了把它们排队,维护任务的执行顺序。

5. 内容出处

直面数据结构

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部