图解 | 不就是队列吗

IT牧场

共 2620字,需浏览 6分钟

 ·

2021-03-17 21:45

点击下方“IT牧场”,选择“设为星标”



今天分享的内容是队列这种数据结构,主要内容有:

  • 队列的定义及应用

  • 顺序队列的介绍及实现

  • 循环队列的介绍及实现

  • 链式队列的介绍及实现



01

队列的定义及应用

队列(queue)是一种先进先出的线性表,只允许在一端进行插入操作,在另一端进行删除操作。允许数据插入的这一端称为队尾,允许数据删除的这一端称为队头。
队列在生活中的一个应用是客户服务的排队等待。比如去移动营业厅办理业务时,对于刚去的几个人,由于客户服务专员都是空闲的,所以可以一对一处理相关业务。在处理过程中,如果有其他客户过来,那么就需要排队等待,当某个客户服务专员处理完一个业务后,队首的客户就可以到相应窗口处理其业务了。


02

顺序队列的介绍及实现

顺序队列是指由数组实现的队列。
我们说队列有队头和队尾,对于用数组实现的队列,在这里我们规定索引为0的一端作为队头。那么,入队操作就是就是向数组中添加元素,这时不需要移动任何元素。
当队列满时,需要做的是扩容,在这里我们扩容为原来的2倍。也就是当数组满时,新建一个容量为原数组2倍的数组,然后将原数组中的元素依次拷贝到新数组中。这里入队操作只有在数组容量不足时,才会做一次数据移动,根据根据摊还分析法(满满的一篇,全是复杂度分析核心知识点),其时间复杂度为O(1)。
接着,我们看下出队操作的时间复杂是多少?
出队操作,是将索引为0的元素移除。由于,我们规定索引为0的这一端是队头,因此,每次队头元素出队后,都需要将队列中剩余的元素向前移动一位。所以出队操作的时间复杂度是O(n)。
顺序队列的代码实现如下:



03

循环队列的介绍及实现

上述顺序队列的实现中,我们把索引为0的位置当做队头,这使得每当元素出队时,都要将其后面的所有元素向前移动一个位置。
当数据量很大时,这个操作就非常耗时了。那么,可不可以减少数据移动的次数呢?
可以的。就是我们分别用head和tail指向队列的队头和队尾。这样,当有元素入队时,tail++就可以;
同样的,当有元素出队时,head++就可以了。
在这里我们分别用head和tail指向队列的队头和队尾,那么当队列为空时,head和tail指向同一个位置,也就是说head==tail表示队列为空。
那么什么时候会触发数据移动呢?就是当tail的值等于数组容量,head不等于0时。因为,如果tail的值等于数组容量且head=0,则表示队列满了。
队列不满时,数据迁移具体动画演示如下:

这样出队操作的时间复杂度就降低了。这时用数组实现队列的代码如下:


那么,能不能更进一步,就是当tail的值等于数组容量且head不等于0时(如下图所示),在这种情况下,直接将元素添加到空的位置呢?
也就是说tail的值等于数组容量时,将其指向索引为0的位置,即在从头开始添加元素。我们把这种头尾相接的顺序存储结构称为循环队列
在索引为0的位置添加元素后,tail需要加1,即向后移动一个位置。此时,head==tail,也就是说队列满了。
但是,我们在上面已经规定head==tail是表示队列为空。这时该怎么办呢?我们可以规定(tail+1)%data.length==head表示队列满了。
接着,我们对(tail+1)%data.length==head表示队列满做一个解释:
  • 如下图,tail=6时,(6+1)%7=0=head,此时队列满。
  • 下图中,tail再次指向0,此时(0+1)%7=1=head,队列满。
  • 下图中,tail=1,此时(1+1)%7=2=head,队列满。
根据上述分析,在循环队列中,head==tail表示队列为空;(tail+1)%data.length==head表示队列满,此时,数组中浪费一个存储空间。
基于数组实现的循环队列代码示例如下:


04

链式队列的介绍及实现

链式队列是指用链表实现的队列。常见的链表结构如下图:
对于这样的链表不论是在head这一端添加元素还是删除元素,都是容易的。
在链表头节点head之前添加元素的时间复杂度是O(1),动画演示如下:
删除链表头节点head时,不需要遍历链表,时间复杂度是O(1),动画演示如下:

也就是说对于链表的头节点head来说,把其当做队列的队头和队尾都是可以的。
但是,队列只允许在一端进行插入操作,在另一端进行删除操作。因此,链表的head这一端,要么做队头,要么做队尾。
接着,我们看下当有tail指向链表尾节点时,添加元素和删除元素是怎么样的。
向tail所指节点,即链表尾节点添加元素不需要进行遍历操作,时间复杂度是O(1)。
在要删除链表尾节点时,要知道tail前一个节点是哪个,就需要从链表头节点开始遍历链表才能确定。因此,如果把链表尾节点当做队列的队头,出队操作的时间复杂度就是O(n)。
根据上述分析,我们应该把head指向的头节点作为队头,tail指向的尾节点作为队尾。这样,出队和入队操作的时间复杂度就都是O(1)。
链式队列的代码实现如下:


今天的分享就到这里了

错误或不足之处
欢迎留言指出
下一篇我们将学习新的内容,敬请期待


参考资料:
  • 《大话数据结构》——程杰著
  • 《数据结构与算法之美》——极客时间

  • 《玩转数据结构》——慕课网

干货分享

最近将个人学习笔记整理成册,使用PDF分享。关注我,回复如下代码,即可获得百度盘地址,无套路领取!

001:《Java并发与高并发解决方案》学习笔记;002:《深入JVM内核——原理、诊断与优化》学习笔记;003:《Java面试宝典》004:《Docker开源书》005:《Kubernetes开源书》006:《DDD速成(领域驱动设计速成)》007:全部008:加技术群讨论

近期热文

LinkedBlockingQueue vs ConcurrentLinkedQueue解读Java 8 中为并发而生的 ConcurrentHashMapRedis性能监控指标汇总最全的DevOps工具集合,再也不怕选型了!微服务架构下,解决数据库跨库查询的一些思路聊聊大厂面试官必问的 MySQL 锁机制

关注我

喜欢就点个"在看"呗^_^

浏览 30
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报