2.3 循环队列

       队列的特征是先进先出，有个缩写FIFO，是first input first output的缩写。在实际开发过程中，有许多队列的例子。因为先进先出，就像现实中的排队，所以广泛用于多线程中，用于保证多线程中各个线程的公平性。

       队列的实现有多种形式，比如可以直接使用链表实现队列。其实数组也可以实现，但是数组列表不合适。因为前文介绍过，数组列表从头部移除，性能十分低下。Java在1.2就提供了数组列表的实现ArrayList，但直到JDK 1.6才提供了ArrayDeque以解决头部插入和移除性能低下的问题。所以这里简单介绍下数组队列的实现，让童鞋们明白为什么ArrayDeque是怎么高效地从头部插入和移除数据的。

       前面讲过数组列表使用一个尾部索引来表示尾部位置。那么我们加上一个头部位置呢？那样就可以不频繁挪动数组元素啦，性能将极大地提高。不过这样对数组的利用就不够充分。为什么这样说呢？

       假设这种场景，头部插入异常多，而尾部插入非常少，那么就会导致首尾的不平衡，往头部插入新元素还是会频繁移动数组元素，如以下场景：

       那么怎么办呢？

       我们可以可以把数组的首尾连接起来，形成一个环，如下图所示：

       这就形成了循环队列了。需要注意的是循环队列不仅可以当作队列使用，因为两端都可以增加删除，所以还可以当作栈、环形缓冲（RingBuffer）使用。

       下面简单分析下

       从头部插入的时候，不断减少head，到了0时，就移动到最后一个。比如上图到了0，再往头部插入数据，head就移动到索引11。直到head到了tail+1的位置。

       从尾部插入的时候，不断增加tail，同理，如果tail增加到了11的话，在增加就到了索引0。直到到了head-1的位置。

       因为是个循环，所以要使用模加法/模减法。这里有个细节哈哈，JDK8的循环队列，使用的是位运算，而JDK11使用的是模加法/模减法。

       这里就需要注意边界值的问题。如果head和tail都指向空闲位置。在初始化时，head和tail都指向0。那么插入一个元素之后，需要移动两个指针，程序的判断就复杂了。所以最好的方案是对头尾进行不同的处理，tail指向空闲位置，而head指向已经有元素的位置。

       而删除方法就比较容易了，和数组列表的处理方式一样。下面是我用java写的比较简单的循环队列实现：

package com.youngthing.list.cycle;import java.util.Arrays;/** * 循环队列 * created at 11/01/2022 * * @author 俞建波 * yujianbo@chtwm.com * @since 1.0.0 */public class CycleList {    private Object[] data;    private int head;    private int tail;    public CycleList() {        data = new Object[4];    }    public static int decrease(final int i, int modules) {        int j = i - 1;        if (j = modules) {            return j - modules;        }        return j;    }    public int size() {        int l = tail - head;        if (l < 0) {            l += data.length;        }        return l;    }    public void addFirst(T e) {        head = decrease(head, data.length);        data[head] = e;        if (head == tail) {            ensureCapacity();        }    }    public void addLast(T e) {        data[tail] = e;        tail = increase(tail, data.length);        if (head == tail) {            ensureCapacity();        }    }    public T removeFirst() {        if (head == tail) {            throw new IllegalArgumentException("队列为空");        }        T e = (T) data[head];        head = increase(head, data.length);        return e;    }    public T removeLast() {        if (head == tail) {            throw new IllegalArgumentException("队列为空");        }        T e = (T) data[tail - 1];        tail = decrease(tail, data.length);        return e;    }    private void ensureCapacity() {        Object[] array = new Object[(data.length + 1) << 1];        System.arraycopy(data, 0, array, 0, head);        int lengthDiff = array.length - data.length;        System.arraycopy(data, head, array, head + lengthDiff, data.length - head);        head = head + lengthDiff;        data = array;    }}

       对于循环队列，不建议重复造轮子，以java为例子，Java自带的ArrayDeque代码就相当完善。面试时会问到JDK8与JDK11ArrayDeque的区别，本文不讨论具体语言的细节。