点击下方“IT牧场”,选择“设为星标”
今天分享的内容是队列这种数据结构,主要内容有:
队列的定义及应用
顺序队列的介绍及实现
循环队列的介绍及实现
链式队列的介绍及实现
01
队列的定义及应用
队列(queue)是一种先进先出的线性表,只允许在一端进行插入操作,在另一端进行删除操作。允许数据插入的这一端称为队尾,允许数据删除的这一端称为队头。队列在生活中的一个应用是客户服务的排队等待。比如去移动营业厅办理业务时,对于刚去的几个人,由于客户服务专员都是空闲的,所以可以一对一处理相关业务。在处理过程中,如果有其他客户过来,那么就需要排队等待,当某个客户服务专员处理完一个业务后,队首的客户就可以到相应窗口处理其业务了。
02
顺序队列的介绍及实现
我们说队列有队头和队尾,对于用数组实现的队列,在这里我们规定索引为0的一端作为队头。那么,入队操作就是就是向数组中添加元素,这时不需要移动任何元素。当队列满时,需要做的是扩容,在这里我们扩容为原来的2倍。也就是当数组满时,新建一个容量为原数组2倍的数组,然后将原数组中的元素依次拷贝到新数组中。这里入队操作只有在数组容量不足时,才会做一次数据移动,根据根据摊还分析法(满满的一篇,全是复杂度分析核心知识点),其时间复杂度为O(1)。出队操作,是将索引为0的元素移除。由于,我们规定索引为0的这一端是队头,因此,每次队头元素出队后,都需要将队列中剩余的元素向前移动一位。所以出队操作的时间复杂度是O(n)。03
循环队列的介绍及实现
上述顺序队列的实现中,我们把索引为0的位置当做队头,这使得每当元素出队时,都要将其后面的所有元素向前移动一个位置。当数据量很大时,这个操作就非常耗时了。那么,可不可以减少数据移动的次数呢?可以的。就是我们分别用head和tail指向队列的队头和队尾。这样,当有元素入队时,tail++就可以;在这里我们分别用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 中为并发而生的 ConcurrentHashMap•Redis性能监控指标汇总•最全的DevOps工具集合,再也不怕选型了!•微服务架构下,解决数据库跨库查询的一些思路•聊聊大厂面试官必问的 MySQL 锁机制
关注我
喜欢就点个"在看"呗^_^