循环队列真的没那么难，就那么几个注意点，附Java代码及运行效果

1. 队列

队列是一种常见的线性数据结构，满足先进先出(First In First Out)，简称为FIFO，第一次看到FIFO还以为是单片机的输出输出什么的，见笑了。数据结构不太了解的话可以看看我总结粗略的博客大凌的数据结构。

 

2. 循环队列

2.1 为什么需要循环队列

在 大凌的数据结构 中，大凌简述了队列可通过数组和链表实现，且数组和链表各有各的优点。如果我们看中了数组，使用数组实现队列，那么随之而来的就需要我们“买单”。我们都知道在Java中，数组是静态分配的，如果一个数组初始化时大小确定，那么后期是更改不了数组容量的，直至没有引用指向该内存地址，这个数组地址才会被Java虚拟机回收。但我们为了使队列满足先入先出这个规则，那么每一次取出一个元素，只能让队列头指针后移，而不是真正地删除该内存地址，打字太啰嗦了，直接上图，如下图。

通过上图我们可以了解，使用数组实现队列时，最终会出现明明队列的内存空间地址是空的，但是数据无法加入，也就是所谓的“假满队列”现象。

因此，为了高效地利用内存资源，“诞生”了循环队列。

 

2.2 循环队列的实现

由于循环队列的特殊，rear和front的更新、队列是否为空以及队列是否已满的判断条件变得不一样，接下来就详细地分析一下循环队列的实现。

循环队列的几点说明：

① 循环队列使用数组实现；

② 在初始化队列容量时，多分配一个，后面有用；

② 队列头指针 front 指向第一个元素的前一个元素，指针顺时针移动；

③ 队列尾指针 rear 指向最后一个元素，指针顺时针移动。

 

实现流程：

1. 一定要看上面的4点说明再来看实现流程啊啊啊！！！假设构造一个容量为5的队列，那么多分配一个，

    也就是实际生成一个容量为6的数组，初始化 front = 0， rear = 0；此时是队列为空情况，front = rear；

    此时实际的数组和循环队列对应图如下。

2. 添加两个元素4和1，front指向第一个元素的前一个元素，rear指向最后一个元素，此时实际的数组和循环队列对应图如下。

 

3. 删除一个元素，也就是取出先进入队列的元素 4，front还是指向第一个元素的前一个元素，rear还是指向最后一个元素。

    要说明的是，4其实还是在数组的第二个元素那里，只是访问不到了，则此时实际的数组和循环队列对应图如下。

4. 添加四个元素8、3、7、2，front指向第一个元素前一个元素，rear指向最后一个元素，注意：因为有一个空间是我们预留的，

    此时已是队列满情况，即 (rear + 1) = front；程序中真实判断队满的条件是 (rear + 1) % arr.length == front，后面再讲。

    有没有同学好奇rear怎么从数组的后面指向到前面来的呢？添加8 3 7后，rear指向最后一个元素7，rear = 5；

    添加元素2时，程序让rear继续自增加1，rear = 6，超出数组的最大索引？其实程序中是 rear = (++rear) % arr.length，

    那么在添加元素2后，rear = 0；此时实际的数组和循环队列对应图如下。

5. 最后我们再取出元素 1、8、3、7、2，队空，rear = front；此时实际的数组和循环队列对应图如下。

 

 

2.3 循环队列的实现代码及运行效果

2.3.1 循环队列实现类的代码

class CircleQueue{
    private int front = 0;
    private int rear = 0;
    private int capcity;
    private int defaultCapcity = 30;

    String[] arr;
    CircleQueue(){
        // 预留了一个位置，所以多分配一个内存空间
        arr = new String[defaultCapcity + 1];
        capcity = defaultCapcity + 1;
    }

    CircleQueue(int s){
        // 预留了一个位置，所以多分配一个内存空间
        arr = new String[s + 1];
        capcity = s + 1;
    }

    void addData(String s){
        // 队满条件
        if(((rear + 1) % capcity) == front){
            System.out.println("Queue is full, can't add data");
            return;
        }
        // rear指向的就是最后一个元素，再添加元素需要先后移然后取模
        rear = (++rear) % capcity;
        arr[rear] = s;
    }

    String getData(){
        // 队空条件
        if(rear == front){
            System.out.println("Queue is empty, can't get data");
            return null;
        }
        // front指向的是第一个元素的前一个，所以取元素要先后移然后取模
        front = (++front) % capcity;
        return arr[front];
    }
}

 

2.3.2 队列容量为3的运行效果图