数据结构笔记总结(2.5)循环队列
上一节问题分析
上一节末尾对时间复杂度的分析中,我们可以看出数组队列是有一定程度缺陷的,关键问题就是在于出队这个操作,它的时间复杂度是O(n)级别的,这一小节我们再来看一下这个问题应该怎么解决。
假设该数组队列可容纳元素是八个,现在已经有五个元素,并且要出队了,也就是要删除队首的元素。
根据队列的定义,假设队首在左侧,a这个元素就会出队。
出队之后,所有其他元素都必须向前挪一个单位,之后size–。
这就是数组底层实现删除一个队首的过程,由于删除后,剩余元素都要向前移动一位,所以时间复杂度是O(n)。
基于以上分析,相信大家不难想象,如果我们删完了a这个元素之后,剩余元素可不可以不挪一个位置呢?
当然可以啊!基于这样的想法,我们可以在数组中先记录一下队首是谁。
比如现在这个数组中,虽然第0个元素是空的,其实队首是存放在索引为1的位置,我们叫它front。
同时,队尾和之前的size一样,指的是下一次有一个新的元素入队应该存储的位置。
因此,我们只需要修改一下front的指向就好了。
准确的说,就是只要front++就可以了,而不需要所有的元素全都向前移动一个单位。
基于上面的想法,就有了循环队列这样一种队列实现方式。
循环队列
在初始的情况下,队列中没有任何元素,front和tail都指向0。
这里要注意,front本来应该指向数组的第一个元素,而tail指向数组中最后一个元素的后一个位置。
但是当队列整体为空的时候,front只好和tail指在一起,也就是说:front和tail相等的时候,意味着队列为空。
接下来,如果有一个元素a入队了,此时我们只需要维护tail也就是队尾就好了。
tail指向下一个元素再入队的时候的位置,以此类推……
此时队列里有五个元素,如果我们要出队一个元素怎么办呢?
非常简单,front指向的是队首元素,此时front指向a,a出队,front向后挪一个位置。
这种情况下,出队操作不再需要所有的元素都挪动了,只需要front的指向改变就可以了。
所以变成了一个O(1)的操作,依次类推……
如果又要有新的元素入队了,如下图所示,这种情况下,tail就不能++了。
可是大家可以看到,由于挪出前面的数组之后,空间没有被挤掉,所以相当于对于数组来说,前面有可能还有可以利用的空间,这就是循环队列的来由。
此时可以理解成,其实可以把数组看成是一个环。
现在这个数组中,一共可以容纳八个元素,对应的索引是0~7。
7之后的索引其实是0,tail++更准确的说应该是当前的索引加1再%整个数组的长度。
换句话说,7是怎么计算到0的呢?
是7+1=8,对8求余等于0,所以在0这个位置还能放新的元素。
这里要注意,只剩下一个空间了,还能放下一个元素吗?
假如再有一个元素入队了放在1这个位置,tail++,此时tail变成了2,front也是2,这种情况下,front又等于tail了。
可此时队列不为空,所以我们应该重新定义一下什么情况下队列为满:如果(tail+1)%c==front,即为队列满。
换句话说,tail指向的位置就是下次有元素入队应该放入的位置,一旦有新元素放入后,tail就要加一,但是加一后就和front重叠了,就说明队列满了。
也就是说,我们是有意识的浪费了一个空间。
代码演示
新建一个循环队列实现代码
public class LoopQueueimplements Queue { private E[] data; private int front, tail; private int size; // 可以思考一下:LoopQueue中不声明size,如何完成所有的逻辑? public LoopQueue(int capacity){ data = (E[])new Object[capacity + 1]; front = 0; tail = 0; size = 0; } public LoopQueue(){ this(10); } public int getCapacity(){ return data.length - 1; } @Override public boolean isEmpty(){ return front == tail; } @Override public int getSize(){ return size; } // 下一小节再做具体实现 @Override public void enqueue(E e){ } // 下一小节再做具体实现 @Override public E dequeue(){ return null; } // 下一小节再做具体实现 @Override public E getFront(){ return null; } }
源码下载
[dm href=’https://www.jikewenku.com/product/1487.html’]下载地址[/dm]
导航目录
[dm href=’https://www.jikewenku.com/geeknote/2241.html’]查看导航[/dm]