队列：彻底理解队列

什么是队列

先进者先出，就是"队列" 我们可以想象成，排队买票，先来的先买，后来的只能在末尾，不允许插队。

队列的两个基本操作：入队 将一个数据放到队列尾部；出队 从队列的头部取出一个元素。队列也是一种操作受限的线性表数据结构 它具有先进先出的特性，支持队尾插入元素，在队头删除元素。

队列的概念很好理解，队列的应用也非常广泛如：循环队列、阻塞队列、并发队列、优先级队列等。

顺序队列

顺序队列都是基于数组的方式实现的，是连续的一块内存空间。如下图

顺序队列.png

我们看下代码实现，非常简单

public class ArrayQueue<T> {
    private Object queue[];
    private int head = 0;//队头
    private int tail = 0;//队尾
    private int n;//数组的容量

    public ArrayQueue(int count) {
        this.n = count;
        queue = new Object[count];
    }

    public ArrayQueue() {
        this(10);
    }

    /**
     * 加入队列
     *
     * @param t
     * @return
     */
    public boolean enqueue(T t) {
        //表示队列队容量已满
        if (tail == n) {
            //表示整个队列已经存满了
            if (head == 0) {
                System.out.println("队列已存满，没有队列移出");
                return false;
            } else {
                System.out.println("队列已满，有队列移出，进行数据搬移，然后插入队列");
                //表示还剩  （tail - head）的数据 进行数据搬移 将队头的下标改为从0开始 入队时保证了数组的连续性
                for (int i = head; i < tail; i++) {
                    queue[i - head] = queue[i];
                }
                //重置队尾的大小等于head
                tail -= head;
                //重置队头head = 0
                head = 0;
            }
        }
        System.out.println("插入队列:" + t);
        //加入队列 队尾+1
        queue[tail++] = t;
        return true;
    }

    /**
     * 移除队列
     * 如果每次出队操作 都从下标为0队位置开始，那么每次都要进行数据搬移
     * 时间复杂度O(1) 就变成了 O(n),
     * 优化：再出队时不进行数据搬移，虽然会导致数组的不连续，
     * 当没有空闲当空间时入队时在进行数据搬移，这样也就保持了数组的连续性
     *
     * @return
     */
    public T dequeue() {
        //表示队列为空
        if (head == tail) return null;
        //tail 队尾 从0开始 移除队列 已知
        T t = (T) queue[head++];
        System.out.println("移除队列:" + t);
        return t;
    }


}

需要注意的是，正常的思路，当我们每次移出队列的时候，都要进行一次数据搬移，时间复杂度O(1) 变成了 O(n),

for (int i = head; i < tail; i++) {
                    queue[i - head] = queue[i];
                }

如何进行优化呢？在上述的代码中已经给出了答案，出队时不进行数据搬移，虽然会导致数组的不连续，入队时当没有空闲当空间时也就是tail == n 入队时在进行数据搬移，这样也就保持了数组的连续性,同时也解决了频繁的入队、出队操作，导致的频繁的数据搬移。

如下图所示：

image

核心代码如下：

if (tail == n) {
            //表示整个队列已经存满了
            if (head == 0) {
                System.out.println("队列已存满，没有队列移出");
                return false;
            } else {
                System.out.println("队列已满，有队列移出，进行数据搬移，然后插入队列");
                //表示还剩  （tail - head）的数据 进行数据搬移 将队头的下标改为从0开始 入队时保证了数组的连续性
                for (int i = head; i < tail; i++) {
                    queue[i - head] = queue[i];
                }
                //重置队尾的大小等于head
                tail -= head;
                //重置队头head = 0
                head = 0;
            }
        }

从上述代码和图片中，当队列的tail队尾标志位，移动到数组的最右边后，如果有新的数据入队，将head - tail 之间的数据，整体搬移到数组中的 0 - （tail-head）的位置。

循环队列

上述通过数组来实现的队列，我们虽然进行了优化，但是当tail == n时，还是会进行一次数据搬移，性能也会收到影响，能否避免数据呢？答案是肯定的，看一下循环队列的解决思路。

循环队列就相当于一个圆环，数组可以想象成一条直线，我们吧这条直线掰成一个圆环，就是循环队列，为了更形象的表示，可以看下图所示：

循环队列.png

如上图所示，队列的大小为size = 11，队列head指向 5 ，队尾fail指向10，当向队尾添加一个元素F，这时fail = 0，这时再向队尾添加一个元素G，这时fail = 1.队列就变为下图所示

94F3B052-DCD7-4E6E-8567-0B91621E0F19.png

循环队列很显然的避免了数组的搬移操作。

循环队列的难点在于如何确定队空和队满的判定条件以及head和fail的变化.

总结一下规律，fail的变化，当fail=10，如何让fail = 0呢？很显然 fail = (fail+1)%size; 那么head同理也遵循这样的变化head=(head+1)%size.

如何判定队满呢？从上面的规律来看，我们可以发现(fail+1)%size == head的时候，队列就满了，但是fail指向的位置实际上是没有数据的，这就意味这循环队列浪费了一个存储空间，以空间换取时间。

下面就是，show time代码时间，理解了上面的思路，代码就很好实现了。

public class CycleQueue<E> {

    private Object cQ[];

    private int head = 0;
    private int tail = 0;

    private int size;

    public CycleQueue(int size) {
        this.size = size;
        cQ = new Object[size];
    }

    public CycleQueue() {
        this(10);
    }

    public boolean enqueue(E e) {
        //表示队列满了
        if ((tail+1) % size == head) return false;
        cQ[tail] = e;
        tail = (tail + 1) % size;
        return true;
    }

    public E dequeue() {
        if (head == tail) return null;
        E o = (E) cQ[head];
        head = (head + 1) % size;
        return o;
    }
}

链式队列

基于链表的实现队列，同理也需要两个指针标志这队头和队尾，如下图所示：

449ED9D2-1994-45E0-A852-5BD3CFF86FD4.png

代码很简单，如下：

public class LinkedQueue<E> {

    private int size;

    //队头
    private Node<E> head;

    //队尾
    private Node<E> tail;

    public LinkedQueue() {
    }

    public boolean enqueue(E value) {
        if (tail == null) {//表示队列是空队列 插入第一个
            Node<E> eNode = new Node<>(null, value);
            head = eNode;
            tail = eNode;
        } else {
            Node temp = tail;
            tail = new Node<>(null, value);
            temp.next = tail;
        }
        size++;
        return true;
    }

    public E dequeue() {
        if (head == null) return null;
        E value = null;
        if (head.next != null) {
            value = head.value;
            head = head.next;
        } else {//临界点 队列只剩下一个了
            value = head.value;
            head = null;
        }
        size--;
        return value;
    }

    public void traversing() {
        Node<E> temp = head;
        for (int i = 0; i < size; i++) {
            System.out.println("value:" + temp.value);
            temp = temp.next;
        }
    }

    public static class Node<E> {
        public Node<E> next;
        public E value;

        public Node(Node<E> next, E value) {
            this.next = next;
            this.value = value;
        }
    }
}

基于链表实现的队列，支持无限排队的无界队列。

另外还有几种高级的队列结构，阻塞队列、并发队列，阻塞队列就是入队、出队操作可以阻塞，并发队列就是队列的操作多线程安全。