数据结构与算法分析：（七）队列

红太狼 2023-07-11 08:35 42阅读 0赞

## 一、队列的定义 ##

队列是一种特殊的线性表，是一种`先进先出`（FIFO）的数据结构。它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

我们知道，栈只支持两个基本操作：入栈 push()和出栈 pop()。队列跟栈非常相似，支持的操作也很有限，最基本的操作也是两个：`入队 enqueue()`，放一个数据到队列尾部；`出队 dequeue()`，从队列头部取一个元素。

![在这里插入图片描述][20200304192947690.png]

所以，队列跟栈一样，也是一种操作受限的线性表数据结构。

我们先来一下看一下Queue的实现：

**1、没有实现的阻塞接口的**

内置的不阻塞队列： `PriorityQueue` 和 `ConcurrentLinkedQueue`

PriorityQueue 和 ConcurrentLinkedQueue 类在 Collection Framework 中加入两个具体集合实现。

`PriorityQueue` 类实质上维护了一个有序列表。加入到 Queue 中的元素根据它们的天然排序（通过其 java.util.Comparable 实现）或者根据传递给构造函数的 java.util.Comparator 实现来定位。

`ConcurrentLinkedQueue` 是基于链接节点的、线程安全的队列。并发访问不需要同步。因为它在队列的尾部添加元素并从头部删除它们，所以只要不需要知道队列的大小，　　　　 　　ConcurrentLinkedQueue 对公共集合的共享访问就可以工作得很好。收集关于队列大小的信息会很慢，需要遍历队列。

**2、实现阻塞接口的**

java.util.concurrent 中加入了 `BlockingQueue` 接口和`五个阻塞队列类`。它实质上就是一种带有一点扭曲的 FIFO 数据结构。不是立即从队列中添加或者删除元素，线程执行操作阻塞，直到有空间或者元素可用。

五个队列所提供的各有不同：

*  `ArrayBlockingQueue` ：一个由数组支持的有界队列。
 *  `LinkedBlockingQueue` ：一个由链接节点支持的可选有界队列。
 *  `PriorityBlockingQueue` ：一个由优先级堆支持的无界优先级队列。
 *  `DelayQueue` ：一个由优先级堆支持的、基于时间的调度队列。
 *  `SynchronousQueue` ：一个利用 BlockingQueue 接口的简单聚集（rendezvous）机制。

![在这里插入图片描述][20200304201028212.png]

关于阻塞队列与非阻塞队列的详细分析可以关注: [源码解读专栏][Link 1]

## 二、如何实现一个队列？ ##

跟栈一样，队列可以用数组来实现，也可以用链表来实现。用数组实现的栈叫作顺序栈，用链表实现的栈叫作链式栈。同样，用数组实现的队列叫作`顺序队列`，用链表实现的队列叫作`链式队列`。

**1、顺序队列**

我们先来看下基于数组的实现方法

/** * 用数组实现的队列 */
    public class ArrayQueue { 
        // 数组：items，数组大小：n
        private String[] items;
        private int n = 0;
        // head表示队头下标，tail表示队尾下标
        private int head = 0;
        private int tail = 0;
    
        // 申请一个大小为capacity的数组
        public ArrayQueue(int capacity) { 
            items = new String[capacity];
            n = capacity;
        }
    
        // 入队
        public boolean enqueue(String item) { 
            // 如果tail == n 表示队列已经满了
            if (tail == n) return false;
            items[tail] = item;
            ++tail;
            return true;
        }
    
        // 出队
        public String dequeue() { 
            // 如果head == tail 表示队列为空
            if (head == tail) return null;
            String temp = items[head];
            ++head;
            return temp;
        }
    }

对比前面讲的栈来说稍微有点复杂。对于栈来说，我们只需要一个`栈顶指针`就可以了。但是队列需要两个指针：一个是 `head 指针`，指向队头；一个是 `tail 指针`，指向队尾。

--------------------

我们还是像前面讲的来分析下时间、空间复杂度。

不难发现，随着不停地进行入队、出队操作，head 和 tail 都会持续往后移动。当 tail 移动到最右边，即使数组中还有空闲空间，也无法继续往队列中添加数据了。这个问题该如何解决呢？

你是否还记得我们前面有讲过数组的删除操作会导致数组中的数据不连续。当时我们用的`数据搬移`。但是，每次进行出队操作都相当于删除数组下标为 0 的数据，要搬移整个队列中的数据，这样出队操作的时间复杂度就会从原来的 O(1) 变为 O(n)。能否优化一下呢？

实际上，我们在出队时可以不用搬移数据。如果没有空闲空间了，我们只需要在入队时，再集中触发一次数据的搬移操作。借助这个思想，出队函数 dequeue() 保持不变，我们稍加改造一下入队函数 enqueue() 的实现，就可以解决了。如下代码：

// 入队操作，将item放入队尾
    public boolean enqueue(String item) { 
        // 如果tail == n 表示队列已经满了
        if (tail == n) { 
            // tail ==n && head==0，表示整个队列都占满了
            if (head == 0) return false;
            for (int i = head; i < tail; i++) { 
                items[i - head] = items[i];
            }
            // 搬移完之后重新更新head和tail
            tail -= head;
            head = 0;
        }
        items[tail] = item;
        ++tail;
        return true;
    }

从代码中我们看到，当队列的 tail 指针移动到数组的最右边后，如果有新的数据入队，我们可以将 head 到 tail 之间的数据，整体搬移到数组中 0 到 tail-head 的位置。

--------------------

Q：这种实现思路中，出队操作的时间复杂度仍然是 O(1)，但入队操作的时间复杂度还是 O(1) 吗？

A：

*  如果队尾没有满，可以直接入队，时间复杂度为O(1)。
 *  如果队尾已满的情况下，就必须进行数据搬移了，tail=n,搬移的时间复杂度为O(n)。
 *  总体情况来看，tail的可能是0 ~ n的任意值，在0 ~ n-1的时候队列入队的时间复杂度都是O(1)，不需要搬移直接入队即可；只有当tail=n的时候时间复杂度才迅速飙升为O(n)，即需要进行n次搬移，此时n次的搬移如果均摊到0~n-1这n次上，其实总体的均摊复杂度还是O(1)。

**2、链式队列**

基于链表的实现，我们同样需要两个指针：head 指针和 tail 指针。它们分别指向链表的第一个结点和最后一个结点。如图所示，入队时，tail->next= new\_node, tail = tail->next；出队时，head = head->next。

如下代码：

/** * 基于链表实现的队列 */
    public class LinkedListQueue { 
        // 队列的队首和队尾
        private Node head = null;
        private Node tail = null;
    
        // 入队
        public void enqueue(String value) { 
            if (tail == null) { 
                Node newNode = new Node(value, null);
                head = newNode;
                tail = newNode;
            } else { 
                tail.next = new Node(value, null);
                tail = tail.next;
            }
        }
    
        // 出队
        public String dequeue() { 
            if (head == null) return null;
            String temp = head.data;
            head = head.next;
            if (head == null) tail = null;
            return temp;
        }
    
        public void printAll() { 
            Node temp = head;
            while (temp != null) { 
                System.out.print(temp.data + "->");
                temp = temp.next;
            }
            System.out.println();
        }
    
        private static class Node { 
            private String data;
            private Node next;
    
            public Node(String data, Node next) { 
                this.data = data;
                this.next = next;
            }
    
            public String getData() { 
                return data;
            }
        }
    }

**3、循环队列**

我们刚才用数组来实现队列的时候，在 tail==n 时，会有数据搬移操作，这样入队操作性能就会受到影响。那有没有办法能够避免数据搬移呢？我们来看看循环队列的解决思路。

循环队列就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列结构中，当存储空间的最后一个位置已被使用而再要进入队运算时，只需要存储空间的第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。循环队列可以更简单防止伪溢出的发生，但队列大小是固定的。

如下图：

![在这里插入图片描述][20200304214117291.png]

我们可以看到，图中这个队列的大小为 8，当前 head=4，tail=7。当有一个新的元素 a 入队时，我们放入下标为 7 的位置。但这个时候，我们并不把 tail 更新为 8，而是将其在环中后移一位，到下标为 0 的位置。当再有一个元素 b 入队时，我们将 b 放入下标为 0 的位置，然后 tail 加 1 更新为 1。所以，在 a，b 依次入队之后，循环队列中的元素就变成了下面的样子：

![在这里插入图片描述][2020030421430817.png]

通过这样的方法，我们成功避免了数据搬移操作。看着好像简单了，但要写出没有bug的循环队列还是有点难度的。最关键的是，要**确定好队空和队满的判定条件**。

在用数组实现的非循环队列中，队满的判断条件是 tail == n，队空的判断条件是 head == tail。那针对循环队列，如何判断队空和队满呢？

队列为空的判断条件仍然是 head == tail。但队列满的判断条件就稍微有点复杂了。请看下图：

![在这里插入图片描述][20200304214825116.png]

tail=3，head=4，n=8，所以总结一下规律就是：(3+1)%8=4。多画几张队满的图，你就会发现，当队满时，`(tail+1)%n=head`。

你有没有发现，当队列满时，图中的 tail 指向的位置实际上是没有存储数据的。所以，循环队列会浪费一个数组的存储空间。

我们接下来来看下代码实现：

/** * 基于数组实现的循环队列 */
    public class CircularQueue { 
        // 数组：items，数组大小：n
        private String[] items;
        private int n = 0;
        // head表示队头下标，tail表示队尾下标
        private int head = 0;
        private int tail = 0;
    
        // 申请一个大小为capacity的数组
        public CircularQueue(int capacity) { 
            items = new String[capacity];
            n = capacity;
        }
    
        // 入队
        public boolean enqueue(String item) { 
            // 队列满了
            if ((tail + 1) % n == head) return false;
            items[tail] = item;
            tail = (tail + 1) % n;
            return true;
        }
    
        // 出队
        public String dequeue() { 
            // 如果head == tail 表示队列为空
            if (head == tail) return null;
            String temp = items[head];
            head = (head + 1) % n;
            return temp;
        }
    
        public void printAll() { 
            if (0 == n) return;
            for (int i = head; i % n != tail; i = (i + 1) % n) { 
                System.out.print(items[i] + "->");
            }
            System.out.println();
        }
    
    }

**4、阻塞队列**

`阻塞队列`其实就是在队列基础上增加了阻塞操作。简单来说，就是在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。

![在这里插入图片描述][2020030422153610.png]

你应该已经发现了，上述的定义就是一个“生产者 - 消费者模型”！是的，我们可以使用阻塞队列，轻松实现一个“生产者 - 消费者模型”！

这种基于阻塞队列实现的“生产者 - 消费者模型”，可以有效地协调生产和消费的速度。当“生产者”生产数据的速度过快，“消费者”来不及消费时，存储数据的队列很快就会满了。这个时候，生产者就阻塞等待，直到“消费者”消费了数据，“生产者”才会被唤醒继续“生产”。

而且不仅如此，基于阻塞队列，我们还可以通过协调“生产者”和“消费者”的个数，来提高数据的处理效率。比如前面的例子，我们可以多配置几个“消费者”，来应对一个“生产者”。

![在这里插入图片描述][20200304221652517.png]

前面的几个基础队列不怎么用得到感觉，但这个阻塞队列可是我们搞后端的常客了吧，大名鼎鼎的MQ消息队列就是基于阻塞队列实现的。

**5、并发队列**

在并发队列上JDK提供了两套实现：

*  一个是以`ConcurrentLinkedQueue`为代表的高性能队列，
 *  一个是以`BlockingQueue`接口为代表的阻塞队列，

无论哪种都继承自Queue。

**(1)、ConcurrentLinkedQueue**

ConcurrentLinkedQueue是一个适用于高并发场景下的队列，通过无锁的方式，实现了高并发状态下的高性能。通常ConcurrentLinkedQueue性能好于BlockingQueue。它是一个基于链接节点的无界线程安全队列，该队列的元素遵循先进先出的原则。头是最先加入的，尾是最近加入的，该队列不允许null元素。

ConcurrentLinkedQueue重要方法:

*  add() 和offer() 都是加入元素的方法(在ConcurrentLinkedQueue中这两个方法没有任何区别)
 *  poll() 和peek() 都是取头元素节点，区别在于前者会删除元素（出队列），后者不会。

**(2)、BlockingQueue**

阻塞队列（BlockingQueue）是一个支持两个附加操作的队列。  
这两个附加的操作是：

*  在队列为空时，获取元素的线程会等待队列变为非空。
 *  当队列满时，存储元素的线程会等待队列可用。

阻塞队列常用于生产者和消费者的场景，生产者是往队列里添加元素的线程，消费者是从队列里拿元素的线程。阻塞队列就是生产者存放元素的容器，而消费者也只从容器里拿元素。

BlockingQueue即阻塞队列，从阻塞这个词可以看出，在某些情况下对阻塞队列的访问可能会造成阻塞。  
被阻塞的情况主要有如下两种：

*  当队列满了的时候进行入队列操作
 *  当队列空了的时候进行出队列操作

因此，当一个线程试图对一个已经满了的队列进行入队列操作时，它将会被阻塞，除非有另一个线程做了出队列操作；同样，当一个线程试图对一个空队列进行出队列操作时，它将会被阻塞，除非有另一个线程进行了入队列操作。

在Java中，BlockingQueue的接口位于java.util.concurrent 包中(在Java5版本开始提供)，由上面介绍的阻塞队列的特性可知，阻塞队列是线程安全的。  
在新增的Concurrent包中，BlockingQueue很好的解决了多线程中，如何高效安全“传输”数据的问题。通过这些高效并且线程安全的队列类，为我们快速搭建高质量的多线程程序带来极大的便利。

常用的队列主要有以下两种：（当然通过不同的实现方式，还可以延伸出很多不同类型的队列，DelayQueue就是其中的一种）

*  先进先出（FIFO）：先插入的队列的元素也最先出队列，类似于排队的功能。从某种程度上来说这种队列也体现了一种公平性。
 *  后进先出（LIFO）：后插入队列的元素最先出队列，这种队列优先处理最近发生的事件。

最简单直接的实现方式是直接在 enqueue()、dequeue() 方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操作。实际上，基于数组的循环队列，利用 CAS 原子操作，可以实现非常高效的并发队列。

多线程环境中，通过队列可以很容易实现数据共享，比如经典的“生产者”和“消费者”模型中，通过队列可以很便利地实现两者之间的数据共享。假设我们有若干生产者线程，另外又有若干个消费者线程。如果生产者线程需要把准备好的数据共享给消费者线程，利用队列的方式来传递数据，就可以很方便地解决他们之间的数据共享问题。但如果生产者和消费者在某个时间段内，万一发生数据处理速度不匹配的情况呢？理想情况下，如果生产者产出数据的速度大于消费者消费的速度，并且当生产出来的数据累积到一定程度的时候，那么生产者必须暂停等待一下（阻塞生产者线程），以便等待消费者线程把累积的数据处理完毕，反之亦然。然而，在concurrent包发布以前，在多线程环境下，我们每个程序员都必须去自己控制这些细节，尤其还要兼顾效率和线程安全，而这会给我们的程序带来不小的复杂度。好在此时，强大的concurrent包横空出世了，而它也给我们带来了强大的BlockingQueue。（在多线程领域：所谓阻塞，在某些情况下会挂起线程（即阻塞），一旦条件满足，被挂起的线程又会自动被唤醒）

## 三、知识拓展 ##

Q：我们前面说过，队列有基于链表和基于数组这两种实现方式。这两种实现方式对于排队请求又有什么区别呢？

A：

*  基于链表的实现方式，可以实现一个支持无限排队的无界队列（unbounded queue），但是可能会导致过多的请求排队等待，请求处理的响应时间过长。所以，针对响应时间比较敏感的系统，基于链表实现的无限排队的线程池是不合适的。
 *  而基于数组实现的有界队列（bounded queue），队列的大小有限，所以线程池中排队的请求超过队列大小时，接下来的请求就会被拒绝，这种方式对响应时间敏感的系统来说，就相对更加合理。不过，设置一个合理的队列大小，也是非常有讲究的。队列太大导致等待的请求太多，队列太小会导致无法充分利用系统资源、发挥最大性能。

--------------------

Q：如何实现无锁并发队列？

A：

*  CAS，Compare and Swap即比较并替换。CAS实现原理：CAS有三个操作数：内存值V、预期值A、要修改的值B，当且仅当预期值A和内存值V相同时，将内存值修改为B并返回true，否则什么都不做并返回false。
 *  这里就可以让下标索引来进行CAS操作，但这里会出现ABA问题，因为CAS操作的时候检查下下标索引有没有变化，如果没有发生变化则更新，但是如果一个值原来是A，变成了B，又变成了A，那么使用CAS进行检查时会发现它的值没有发生变化，但是实际上却变化了。ABA问题的解决思路就是使用版本号。在变量前面追加上版本号，每次变量更新的时候把版本号加一，那么A－B－A 就会变成1A-2B－3A。从Java1.5开始JDK的atomic包里提供了一个类AtomicStampedReference来解决ABA问题。这个类的compareAndSet方法作用是首先检查当前引用是否等于预期引用，并且当前标志是否等于预期标志，如果全部相等，则以原子方式将该引用和该标志的值设置为给定的更新值。

[20200304192947690.png]: https://img-blog.csdnimg.cn/20200304192947690.png
[20200304201028212.png]: https://img-blog.csdnimg.cn/20200304201028212.png
[Link 1]: https://blog.csdn.net/riemann_/category_8810412.html
[20200304214117291.png]: https://img-blog.csdnimg.cn/20200304214117291.png
[2020030421430817.png]: https://img-blog.csdnimg.cn/2020030421430817.png
[20200304214825116.png]: https://img-blog.csdnimg.cn/20200304214825116.png
[2020030422153610.png]: https://img-blog.csdnimg.cn/2020030422153610.png
[20200304221652517.png]: https://img-blog.csdnimg.cn/20200304221652517.png