本章内容

队列定义

队列是一种运算受限的线性表，它遵循先进先出的原则。

队列包含两个基本操作：在队尾进行入队操作和在对头进行出队操作。

队列既可以用数组来实现，也可以用链表来实现。用数组实现的队列称为顺序队列，用链表实现的队列称为链式队列。

如图所示：

队列实现

基于数组实现队列

基于数组实现队列时，需要使用两个指针（head、tail）分别记录出队和入队时元素在数据中对应的下标。

如图所示：

其中：

• head指针指向下一个出队元素的下标。
• tail指针指向下一个入队元素的下标。

代码实现

/** * @author 南秋同学 * 基于数组实现队列 */public class QueueByArray {    /**     * 数组     */    private final String[] items;    /**     * 队列容量     */    private final int size;    /**     * 队头下标     */    private int head;    /**     * 队尾下标     */    private int tail;    public QueueByArray(int capacity){        // 初始化数组大小为队列容量        this.items = new String[capacity];        // 设置队列容量        this.size = capacity;        // 初始化队头元素下标为0        this.head = 0;        // 初始化队尾元素下标为0        this.tail = 0;    }    /**     * 入队     * @param element 元素     * @return 入队是否成功     */    public boolean enqueue(String element){        // 队尾下标等于队列容量（容量已满，入队失败）        if(tail == size){            System.out.println("容量已满，入队失败！");            return false;        }        items[tail] = element;        tail++;        return true;    }    /**     * 出队     * @return 出队的元素     */    public String dequeue(){        if(head == tail){            System.out.println("队列中没有元素！");            return null;        }        String response = items[head];        items[head] = null;        head++;        return response;    }    public static void main(String[] args) {        QueueByArray queueByArray  = new QueueByArray(5);        queueByArray.enqueue("a");        queueByArray.enqueue("b");        queueByArray.enqueue("c");        queueByArray.enqueue("d");        queueByArray.enqueue("e");        queueByArray.enqueue("f");        System.out.println("队列中的元素：" + Arrays.toString(queueByArray.items));        System.out.println("出队元素1：" + queueByArray.dequeue());        System.out.println("出队元素2：" + queueByArray.dequeue());        System.out.println("出队元素3：" + queueByArray.dequeue());        System.out.println("出队元素4：" + queueByArray.dequeue());        System.out.println("出队元素5：" + queueByArray.dequeue());        System.out.println("出队元素6：" + queueByArray.dequeue());        System.out.println("队列中的元素：" + Arrays.toString(queueByArray.items));    }}

基于数组实现队列复杂度

如图所示：

图中，队列的入队和出队操作会向后移动head和tail两个指针，而数组的大小是固定的，因此，当tail指针移动到数组最右边时，即使数组中仍有剩余空间，也无法向其中继续添加元素（即：产生内存空洞）。

可以通过整体移动数组中head～tail之间的元素解决内存空洞问题。如图所示：

元素入队时，判断当tail指针是否等于数组的大小，等于则将head到tail之间的元素整体迁移到数组的最左侧，从（tail-head）处开始向数组中添加元素。

通过均摊分析法（均摊时间复杂度一般为最好情况时间复杂度）得出入队的时间复杂度为O(1)。

出队的时间复杂度为O(1)。

基于链表实现队列

基于链表实现队列时，也需要使用两个指针（head和tail）分别指向链表的第一个结点和最后一个结点。

如图所示：

注意：

• head指针指向链表的第一个结点。
• tail指针指向链表的最后一个结点（与基于数组的队列有略微区别）。

代码实现

/** * @author 南秋同学 * 基于链表实现队列 */public class QueueByList<E> {    @Data    @AllArgsConstructor    @NoArgsConstructor    static class Node<E>{        /**         * 节点数据         */        private E value;        /**         * 后继节点         */        private Node<E> next;    }    /**     * 链表头节点     */    private Node<E> head;    /**     * 链表尾节点     */    private Node<E> tail;    /**     * 入队     * @param element 元素     */    public void enqueue(E element){        // 如果尾节点为空，则说明队列中没有元素        if(tail == null){            // 将新增元素封装成节点            Node<E> newNode = new Node<>(element,null);            // 设置头节点            head=newNode;            // 设置尾节点            tail = newNode;        }else {            // 直接将新增元素封装成节点并添加到链表的末尾            tail.next = new Node<>(element,null);            // 设置尾节点尾新增节点            tail = tail.next;        }    }    /**     * 出队     * @return 出队的元素     */    public E dequeue(){        // 头节点为null，说明队列中没有元素，则直接返回null        if(head == null){            return null;        }        // 头节点不为null，取出头节点数据        Node<E> node = head;        // 设置头节点的后继节点为head节点        head = head.next;        // 如果头节点的后继节点为null，则说明队列中没有元素，重置尾节点为null        if(head == null){            tail = null;        }        return node.getValue();    }    /**     * 打印队列中所有元素     */    public void printQueue() {        Node<E> point = head;        while (point != null) {            System.out.print(point.getValue() + " ");            point = point.next;        }        System.out.println();    }    public static void main(String[] args) {        QueueByList queueByList  = new QueueByList();        queueByList.enqueue("a");        queueByList.enqueue("b");        queueByList.enqueue("c");        queueByList.enqueue("d");        queueByList.enqueue("e");        queueByList.enqueue("f");        System.out.print("入队后，队列中所有元素：");        queueByList.printQueue();        System.out.println("第一次出队元素：" + queueByList.dequeue());        System.out.println("第二次出队元素：" + queueByList.dequeue());        System.out.println("第三次出队元素：" + queueByList.dequeue());        System.out.print("出队后，队列中所有元素：");        queueByList.printQueue();    }}

基于链表实现队列复杂度

基于链表实现队列的出入队时间复杂度均为O(1)。

循环队列

循环队列指的是将顺序队列首尾相连，把存储队列元素的表从逻辑上看成一个环，成为循环队列。

如图所示：

图中，队列大小为6，当前head=2，tail=5。当有一个新的元素x入队时，将其放入下标为5的位置。此时并不将tail更新为6，而是将其在环中后移一位，移动到下标为0的位置。当再有一个元素y入队时，就将y放入下标为0的位置，然后tail加1更新为1。如图所示：

循环队列实现最关键部分是确定队空和队满的判定条件。在用数组实现的非循环队列中，队满的判断条件为tail == n，队空的判断条件为head == tail。在循环队列中，队空的判断条件仍然为head == tail，队满的判断条件为(tail+1)%n=head。

注意：当队列满时，循环队列的tail指针指向的位置实际上是没有存储数据的。因此，循环队列会浪费一个元素的存储空间。

代码实现

/** * @author 南秋同学 * 循环队列 */public class CirculateQueue {    /**     * 数组     */    private final String[] items;    /**     * 队列容量     */    private final int size;    /**     * 队头下标     */    private int head;    /**     * 队尾下标     */    private int tail;    public CirculateQueue(int capacity){        // 初始化数组大小为队列容量        this.items = new String[capacity];        // 设置队列容量        this.size = capacity;        // 初始化队头元素下标为0        this.head = 0;        // 初始化队尾元素下标为0        this.tail = 0;    }    /**     * 入队     * @param element 元素     * @return 入队是否成功     */    public boolean enqueue(String element){        // 队满判断条件（此处与非循环数据区别）        if((tail+1)%size==head){            System.out.println("容量已满，入队失败！");            return false;        }        items[tail] = element;        //tail++;        // 此处与非循环数据区别        tail = (tail+1)%size;        return true;    }    /**     * 出队     * @return 出队的元素     */    public String dequeue(){        if(head == tail){            System.out.println("队列中没有元素！");            return null;        }        String response = items[head];        items[head] = null;        // head++;        // 此处与非循环数据区别        head = (head+1)%size;        return response;    }    public static void main(String[] args) {        CirculateQueue circulateQueue  = new CirculateQueue(5);        circulateQueue.enqueue("a");        circulateQueue.enqueue("b");        circulateQueue.enqueue("c");        circulateQueue.enqueue("d");        circulateQueue.enqueue("e");        System.out.println("队列中的元素：" + Arrays.toString(circulateQueue.items));        System.out.println("出队元素1：" + circulateQueue.dequeue());        System.out.println("出队元素2：" + circulateQueue.dequeue());        System.out.println("出队元素3：" + circulateQueue.dequeue());        System.out.println("出队元素4：" + circulateQueue.dequeue());        System.out.println("出队元素5：" + circulateQueue.dequeue());        System.out.println("队列中的元素：" + Arrays.toString(circulateQueue.items));    }}

基于队列的特殊队列

阻塞队列

阻塞队列是在队列基础上增加了阻塞操作：

• 队列为空时，从队头获取数据会被阻塞，直到队列中有数据才能返回。
• 队列已满时，从队尾插入数据会被阻塞，直到队列中有空闲位置后再插入数据。

阻塞队列支持生产者 - 消费者模式，如图所示：

阻塞队列的实现原理主要涉及到两个方面：线程安全和阻塞等待。

• 线程安全实现：阻塞队列的线程安全实现主要依靠锁（ReentrantLock）和同步机制来保证多线程访问的安全。在Java中，常用的锁有ReentrantLock和synchronized，它们可以保证同一时刻只有一个线程可以访问共享资源。
• 阻塞等待实现：阻塞队列的阻塞等待实现主要依靠条件变量来实现。在Java中，常用的条件变量有Condition和wait/notify机制，它们可以使线程在满足特定条件时挂起等待，直到条件满足时被唤醒。

常用的阻塞队列有：ArrayBlockingQueue、LinkedBlockingQueue、PriorityBlockingQueue。

高性能队列Disruptor

Disruptor高性能的原因：

• 循环队列：采用基于数组的循环队列可以有效的避免内存回收。
• 无锁设计：添加和读取元素是采用CAS无锁方式保证线程安全。

【阅读推荐】

想了解常用数据结构与算法（如：数组、链表、栈、快速排序、堆与堆排序、二分查找、动态规划、广度优先搜索算法（BFS）、深度优先搜索算法（DFS）等）的同学请移步->数据结构与算法系列合集（持续更新中）。

更多精彩内容请移步【南秋同学】个人主页进行查阅。

【作者简介】

一枚热爱技术和生活的老贝比，专注于Java领域，关注【南秋同学】带你一起学习成长～