什么是队列

队列是数据结构中⽐᫾重要的⼀种类型，它⽀持 FIFO，尾部添加、头部删除（先进队列的元素先出队列），跟我们⽣活中的排队类似。 因为队列是线性表，所以队列也有类似线性表的各种操作，不同的就是插入数据只能在队尾进行，删除数据只能在队头进行。

队列的种类

单队列

单队列就是常⻅的队列, 每次添加元素时，都是添加到队尾，存在“假溢出”的问题也就是明明有位置却不能添加的情况

假溢出

1. 假设是长度为5的数组，初始状态，空队列如所示，front与 rear指针均指向下标为0的位置。然后入队a1、a2、a3、a4, front指针依然指向下标为0位置，而rear指针指向下标为4的位置。

2. 出队a1、a2，则front指针指向下标为2的位置，rear不变，如下图所示，再入队a5，此时front指针不变，rear指针移动到数组之外。嗯？数组之外，那将是哪里？

问题还不止于此。假设这个队列的总个数不超过5个，但目前如果接着入队的话，因数组末尾元素已经占用，再向后加，就会产生数组越界的错误，可实际上，我们的队列在下标为0和1的地方还是空闲的。我们把这种现象叫做“假溢出”。

循环队列

解决假溢出的办法就是后面满了，就再从头开始，也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。

解决

1. rear可以改为指向下标为0的位置，这样就不会造成指针指向不明的问题了。

2. 但是这个时候，如果继续插入a6、a7的话，指针rear就会与front重合了。

3. 这个时候新的问题来了，就是rear=front的时候，队列是空了还是满了？有两种解决方案

   • 设置一个标志变量flag，当front == rear,且flag = 0时为队列空，当front == rear,且flag= 1时为队列满。
   • 当队列空时，条件就是from = rear，当队列满时，我们修改其条件，保留一个元素空间。也就是说，队列满时，数组中还有一个空闲单元。 如下图所示，我们就认为此队列已经满了，也就是说，我们不允许上图情况出现。

4. 说说第二种方法，由于rear可能比front大，也可能比front小，所以尽管它们只相差一个位置时就是满的情况，但也可能是相差整整一圈。所以若队列的最大尺寸为QueueSize，那么队列满的条件是(rear+1) %QueueSize == front (取模“%的目的就是为了整合rear与front大小为一个问题)。 QueueSize = 5，当 front=0，而 rear=4, (4+1) %5 = 0，所以此时队列满。再比如，front = 2而rear =1。(1 + 1) %5 = 2，所以此时 队列也是满的。而对于下图, front = 2而rear= 0, (0+1) %5 = 1，1!=2,所以此时队列并没有满。

5. 队列长度计算 当rear > front时，此时队列的长度为rear-front。但当rear < front时，队列长度分为两段，一段是QueueSize-front，另一段是0 + rear，加在一起，队列长度为rear-front + QueueSize，因此通用的计算队列长度公式为： (rear—front + QueueSize) % QueueSize

6. Java实现

/**
 * 循环队列
 *
 * @author blog.unclezs.com
 * @date 2020/7/26 9:37
 */
public class CycleQueue<E> {
    private int rear = 0;
    private int front = 0;
    private final Object[] elementData;

    public CycleQueue(int len) {
        this.elementData = new Object[len + 1];
    }


    public void add(E e) {
        if (isFull()) {
            throw new RuntimeException("队列满了");
        } else {
            elementData[rear++] = e;
            if (rear == elementData.length) {
                rear = 0;
            }
        }
    }

    /**
     * 取出队头 并且删除
     *
     * @return 队头元素
     */
    @SuppressWarnings("unchecked")
    public E poll() {
        Object value = elementData[front];
        elementData[front++] = null;
        if (front == elementData.length) {
            front = 0;
        }
        return (E) value;
    }

    /**
     * 判断队列满了没有
     *
     * @return /
     */
    public boolean isFull() {
        return (rear + 1) % elementData.length == front;
    }

    /**
     * 当前队列长度
     *
     * @return /
     */
    public int size() {
        return (rear - front + elementData.length) % elementData.length;
    }
}

单是顺序存储，若不是循环队列，算法的时间性能是不高的，但循环队列又面临着数组可能会溢出的问题，所以我们还需要研究一下不需要担心队列长度的链式存储结构。

链队列

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。

java实现

/**
 * 链队列
 *
 * @author blog.unclezs.com
 * @date 2020/7/26 10:49
 */
public class LinkQueue {
    private Node head;
    private Node tail;
    private int size;

    private static class Node {
        Node front;
        Node rear;
        Object data;

        public Node(Object data) {
            this.data = data;
        }
    }

    public void add(Object e) {
        if (head == null) {
            head = new Node(e);
            tail = head;
        } else {
            Node last = new Node(e);
            last.front = tail;
            tail.rear = last;
            tail = last;
        }
        size++;
    }

    public Object poll() {
        Node value = this.head;
        head = head.rear;
        return value;
    }

    public int size() {
        return size;
    }
}

Java中的队列

以下都是基于JDK1.8版本。

Queue单向队列

介绍

Queue是Java队列的最高层接口，定义了一些常用的方法

• add添加失败抛出异常，offer添加失败不会抛出异常
• element取出队头元素不删除，队列为空则抛出NoSuchElementException异常，peek一样作用只是不会抛出异常
• remove取出队头元素并且从队列中删除，队列为空则抛出NoSuchElementException异常，poll一样作用只是不会抛出异常

拓展

• PriorityQueue优先队列，过传入一个Comparator比较器，来判断队列中元素的优先顺序，所以，队列也不一定全部都是FIFO（先进先出）的。
• BlockingQueue 阻塞队列，在操作不可行时的时候阻塞当前线程，比如想要添加一个元素， 但是队列已经满了，阻塞住当前线程直到队列可以添加元素为止，当然也可以传入等待时间。
• DelayQueue 一个无界阻塞队列，每个元素有一个延迟时间，如果延迟时间没有到，那么获取不到这个元素，因为队列每次从队列头获取元素，如果队头的元素一直没有到期，那么后面的元素将无法获取到。poll方法如果获取不到已经到期的元素则返回null，take方法会阻塞着一直等到可以获取到到期元素。
• SynchronousQueue，一个只能装一个元素的队列，插入元素到队列的线程被阻塞，直到另一个线程从队列中获取了队列中存储的元素。同样，如果线程尝试获取元素并且当前不存在任何元素，则该线程将被阻塞，直到线程将元素插入队列。
• ArrayBlockingQueue，一个阻塞有界队列，创建后队列长度将不能改变。
• LinkedBlockingQueue，一个阻塞有界链队列，可以指定长度来控制队列长度。如果不指定则默认为Integer.MAX_VALUE

Deque双向队列

介绍

一个双向队列的定义，实现了Queue接口，可以在两端进行插入删除操作，也可以当作栈来用。 在Queue基础上添加了一些可以在队列头部进行插入，队列尾部进行删除的方法。

拓展

• BlockingDeque，一个阻塞的双向队列，也就是当队列满了之后，将会阻塞等到可以添加再添加。
• LinkedList双向链表，这个类比较常用，实现了Deque与List接口。所以也可以当作一个双向队列。
• ArrayDeque，双向无界队列，基础数组实现，可以实现自动扩容，与双向链表实现区别在于，对于长度固定的可以使用这个，比较节省内存（没有头尾节点这些，直接存数据）
• ConcurrentLinkedDeque，线程安全的双向队列，无界的。