数据结构笔记总结（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;
    }
}