数据结构笔记总结(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 LoopQueue implements 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]

本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
极客文库 » 数据结构笔记总结(2.5)循环队列

欢迎加入「极客文库」,成为原创作者从这里开始!

立即加入 了解更多