共计 8352 个字符，预计需要花费 21 分钟才能阅读完成。
今日分享开始啦，请大家多多指教~
明天给大家介绍 Queue 队列，在计算机中是必不可少的角色。这是一种数据结构，大家能够把他设想成一个数组。给大家具体分享一下局部内容，篇幅比拟长，大家须要急躁观看哦！
这次咱们重点来看看 Java 中的 Queue 家族，总共波及到 18 种 Queue。
本篇次要内容如下：
一、Queue
队列原理图
1.1 Queue 的介绍
有一个重要的敌人，他的英文名叫 Queue，中文名叫队列，无论现实生活中还是计算机的世界中，都是一个很重要的角色。
它是一种数据结构，大家能够把他设想成一个数组，元素从它的一头进入、从另外一头进来，称为 FIFO 准则（先进先出准则）。
他还有两个亲兄弟：List（列表）、Set（集），他们都是 Collection 的儿子，他还有一个远房亲戚：Map（映射）。他们都是 java.util 包这个小家庭的成员哦！
1.2 现实生活中的场景
海底捞排号等位（先排号的优先进餐厅）
邮政员寄送函件（信箱是队列）
1.3 计算机世界中的场景
音讯队列 RabbitMQ
UDP 协定（接收端将音讯寄存在队列中，从队列中读取数据）
二、高屋建瓴，纵览全局
18 种队列分为三大类：接口、抽象类、一般类。
弄清楚上面的继承实现关系对前面了解 18 种队列有很大帮忙。
Queue 接口继承 Collection 接口，Collection 接口继承 Iterable 接口。
BlockingQueue 接口、Deque 接口继承 Queue 接口；
AbstractQueue 抽象类实现 Queue 接口；
BlockingDeque 接口、TransferQueue 接口继承 BlockingQueue 接口；
BlockingDeque 接口继承 Deque 接口；
LinkedBlockingDeque 类实现 BlockingDeque 接口；
LinkedTransferQueue 类接口实现 TransferQueue 接口；
LinkedList 类、ArrayDeque 类、ConcurrentLinkedDeque 类实现了 Deque 接口；
ArrayBlockingQueue 类、LinkendBlockingQueue 类、LinkedBlockingDeque 类、LinkedTransferQueue 类、SynchronousQueue 类、PriorityBlockQueue 类、DelayQueue 类继承了 AbstractQueue 抽象类和实现了 BlockingQueue 接口；
PriorityQueue 类和 ConcurrentLinkedQueue 类继承了 AbstractQueue 抽象类；留神：
Deque：全称 Double-Ended queue，示意双端队列。
类实现接口，用 implements
接口继承接口，用 extends
类继承类，用 extends
三、万物归宗 Queue 接口
2.1 深刻了解 Queue 接口的实质
Queue 接口是一种 Collection，被设计用于解决之前长期保留在某处的元素。
除了根本的 Collection 操作之外，队列还提供了额定的插入、提取和查看操作。每一种操作都有两种模式：如果操作失败，则抛出一个异样；如果操作失败，则返回一个非凡值（null 或 false，取决于是什么操作）。
队列通常是以 FIFO（先进先出）的形式排序元素，然而这不是必须的。
只有优先级队列能够依据提供的比拟器对元素进行排序或者是采纳失常的排序。无论怎么排序，队列的头将通过调用 remove()或 poll()办法进行移除。在 FIFO 队列中，所有新的元素被插入到队尾。其余品种的队列可能应用不同的布局来寄存元素。
每个 Queue 必须指定排序属性。
2.2 Queue 接口的外围办法
总共有 3 组办法，每一组办法对应两个办法。如下图所示：
Queue 的外围办法
（1）比方增加（Insert）元素的动作，会有两种形式：add(e)和 offer(e)。如果调用 add(e)办法时，增加失败，则会抛异样，而如果调用的是 offer(e)办法失败时，则会返回 false。offer 办法用于异样是失常的状况下应用，比方在有界队列中，优先应用 offer 办法。如果队列满了，不能增加元素，offer 办法返回 false，这样咱们就晓得是队列满了，而不是去 handle 运行时抛出的异样。
（2）同理，移除（Remove）元素的动作，队列为空时，remove 办法抛异样，而 poll 返回 null。如果移除头部的元素胜利，则返回移除的元素。
（3）同理，检测（Examine）元素的动作，返回头部元素（最开始退出的元素），但不删除元素，如果队列为空，则 element()办法抛异样，而 peek()返回 false。
（4）Queue 接口没有定义阻塞队列的办法，这些办法在 BlockQueue 接口中定义了。
（5）Queue 实现类通常不容许插入 null 元素，只管一些实现类比方 LinkedList 不禁止插入 null，然而还是不倡议插入 null，因为 null 也被用在 poll 办法的非凡返回值，以阐明队列不蕴含元素。
四、双端可用 Deque 接口
4.1 深刻了解 Deque 接口的原理
双端队列 Deque
（1）Deque 概念：反对两端元素插入和移除的线性汇合。名称 deque 是双端队列的缩写，通常发音为 deck。大多数实现 Deque 的类，对它们蕴含的元素的数量没有固定的限度的，反对有界和无界。
（2）Deque 办法阐明：
该列表蕴含蕴含拜访 deque 两端元素的办法，提供了插入，移除和查看元素的办法。
这些办法中的每一种都存在两种模式：如果操作失败，则会抛出异样，另一种办法返回一个非凡值（null 或 false，取决于具体操作）。
插入操作的后一种模式专门设计用于容量限度的 Deque 实现，大多数实现中，插入操作不能失败，所以能够用插入操作的后一种模式。
Deque 接口扩大了 Queue 接口，当应用 deque 作为队列时，作为 FIFO。元素将增加到 deque 的开端，并从头开始删除。
作为 FIFO 时等价于 Queue 的办法如下表所示：
比方 Queue 的 add 办法和 Deque 的 addLast 办法等价。
Deque 也能够用作 LIFO（后进先出）栈，这个接口优于传统的 Stack 类。当作为栈应用时，元素被 push 到 deque 队列的头，而 pop 也是从队列的头 pop 进去。
Stack（栈）的办法正好等同于 Deque 的如下办法：
留神：peek 办法不论是作为栈还是队列，都是从队列的检测队列的头，返回最先退出的元素。比方第一次 put 100，第二次 put 200，则 peek 返回的是 100。如下图所示：
4.1 哪些类实现了 Deque 接口
LinkedList 类
ArrayDeque 类
ConcurrentLinkedDeque 类
LinkedBlockingDeque 类
4.2 哪些类继承了 Deque 接口
BlockingDeque 接口
五、队列骨架 AbstractQueue 抽象类
5.1 深刻了解 AbstractQueue 抽象类
AbstractQueue 是一个抽象类，继承了 Queue 接口，提供了一些 Queue 操作的骨架实现。
AbstractQueue 的办法
办法 add、remove、element 办法基于 offer、poll 和 peek。也就是说如果不能失常操作，则抛出异样。咱们来看下 AbstactQueue 是怎么做到的。
AbstractQueue 的 add 办法
AbstractQueue 的 remove 办法
AbstractQueue 的 element 办法
留神：
如果继承 AbstractQueue 抽象类则必须保障 offer 办法不容许 null 值插入。
5.2 哪些类继承了 AbstractQueue 抽象类
ArrayBlockingQueue 类、LinkendBlockingQueue 类、LinkedBlockingDeque 类、LinkedTransferQueue 类、SynchronousQueue 类、PriorityBlockQueue 类、DelayQueue 类继承了 AbstractQueue 抽象类
PriorityQueue 类和 ConcurrentLinkedQueue 类继承了 AbstractQueue 抽象类
六、阻塞缓冲 BlockingQueue 接口
6.1 宏观来看 BlockingQueue（阻塞队列）
BlockQueue 满了，PUT 操作被阻塞
阻塞队列满了的状况
BlockQueue 为空，Take 操作被阻塞
阻塞队列为空的状况
（1）BlockingQueue（阻塞队列）也是一种队列，反对阻塞的插入和移除办法。
（3）阻塞的插入：当队列满时，队列会阻塞插入元素的线程，直到队列不满。
（4）阻塞的移除：当队列为空，获取元素的线程会期待队列变为非空。
（5）利用场景：生产者和消费者，生产者线程向队列里增加元素，消费者线程从队列里移除元素，阻塞队列时获取和寄存元素的容器。
（6）为什么要用阻塞队列：生产者生产和消费者生产的速率不一样，须要用队列来解决速率差问题，当队列满了或空的时候，则须要阻塞生产或生产动作来解决队列满或空的问题。
6.2 案例解析
线程 A 往阻塞队列（Blocking Queue）中增加元素，而线程 B 从阻塞队列中移除元素。
当阻塞队列为空的时候（一个元素都没有），则从队列中获取元素的操作将会被阻塞。
生存中的案例：去海底捞吃火锅的时候，早上 8 点没人来吃火锅，所以须要等客人过去。
翻译成线程：当初没有元素须要增加，而且阻塞队列为空，所以线程 B 不须要从队列中拿元素进去，所以线程 B 获取元素的操作被阻塞了。
当阻塞队列满了的时候（所有地位都放有元素），则从队列中增加元素的操作将会被阻塞。
生存中的案例：去海底捞吃火锅的时候，人太多了，须要排号，等其余桌空进去了能力进去。
翻译成线程：线程 A 往阻塞队列中增加元素，将队列填满了，线程 B 当初正在忙，无奈拿出队列中的元素，所以阻塞队列没有中央再放元素了，这个时候线程 A 增加元素的操作就被阻塞了
6.3 操刀 BlockingQueue 接口
BlockingQueue 接口的 10 个外围办法：
10 个外围办法总结如下：
有三大类操作：插入、移除、查看。
插入有四种办法：add、offer、put、offer 超时版。
IllegalStateException – 队列满了
ClassCastException – 增加的元素类型不匹配
NullPointerException – 增加的元素为 null
IllegalArgumentException – 增加的元素某些属性不匹配
add 办法特别之处用于增加失败时抛出异样，共有四种异样：
offer 办法特别之处用于增加失败时只返回 false
put 办法特别之处用于当阻塞队列满时，生产者如果往队列里 put 元素，则队列会始终阻塞生产者线程，直到队列可用或者响应中断退出
offer 超时办法特别之处用于当阻塞队列满时，生产者如果往队列外面插入元素，队列会阻塞生产者线程一段时间，如果超过了指定工夫，生产者线程会退出，并返回 false。
移除有四种办法：remove、poll、take、poll 超时版
NoSuchElementException – 如果这个队列是空的
remove 办法特别之处用于移除失败时抛出异样
poll 办法特别之处用于移除失败时返回 null
take 办法特别之处用于当阻塞队列为空时，消费者线程如果从队列外面移除元素，则队列会始终阻塞消费者线程，直到队列不为空
poll 超时办法特别之处用于当阻塞队列空时，消费者如果从队列外面删除元素，则队列会始终阻塞消费者线程，如果超过了指定工夫，消费者线程会退出，并返回 null
查看有两种办法：element、peek
element 办法用于检测头部元素的存在性，如果队列为空，则抛出异样，否则返回头部元素。
peek 办法用于检测头部元素的存在性，如果队列为空，返回非凡值 null，否则返回头部的元素。
6.4 BlockingQueue 通过什么来阻塞插入和移除的？
当往队列里插入一个元素时，如果队列不可用，那么阻塞生产者次要通过 LockSupport. park（this）来实现。
park 这个办法会阻塞以后线程，只有以下 4 种状况中的一种产生时，该办法才会返回。
与 park 对应的 unpark 执行或曾经执行时。“曾经执行”是指 unpark 先执行，而后再执行 park 的状况。
线程被中断时。
期待完 time 参数指定的毫秒数时。
异常现象产生时，这个异常现象没有任何起因。
6.5 哪些类继承了 BlockingQueue 接口？
BlockingDeque 接口 – 双端阻塞队列
TransferQueue 接口 – 传输队列
6.6 哪些类实现了 BlockingQueue 接口？
ArrayBlockingQueue 类 – 由数组形成的有界阻塞队列
LinkedBlockingQueue 类 – 由链表形成的有界阻塞队列，界线默认大小为 Integer.MAX_Value（2^31-1），值十分大，相当于无界。
LinkedBlockingDeque 类 – 由链表形成的双向阻塞队列
LinkedTransferQueue 类 – 由链表形成的无界阻塞队列
SynchronousQueue 类 – 不存储元素的阻塞队列，只有一个元素进行数据传递。
LinkedTransferQueue 类 – 由链表形成的无界阻塞 TransferQueue 队列
DelayQueue 类 – 应用优先级队列实现的提早无界阻塞队列
6.6 BlockingQueue 接口继承了哪些接口
BlockingQueue 接口继承了 Queue 接口，可作为队列应用
七、双端阻塞 BlockingDeque 接口
7.1 从原理图上了解 BlockDeque
BlockQueue 满了，两端的 Take 操作被阻塞
BlockingDeque 满了
BlockQueue 为空，两端的 Take 操作被阻塞
BlockQueue 为空
7.2 BlockingDeque 接口办法
是阻塞队列 BlockingQueue 和双向队列 Deque 接口的联合。有如下办法：
最初队列中的元素程序如下：
300, test1, 400。
先增加了 test1 放到队列的头部，而后在头部的后面放入 300，所以 300 在最后面，成为头部，而后将 400 放入队列的尾部，所以最初的后果是 300, test1, 400。
7.3 BlockDeque 和 BlockQueue 的对等办法
7.4 BlockingDeque 的特点
线程平安。
不容许应用 null 元素。
无界和有界都能够。
7.5 BlockingDeque 接口继承了哪些接口？
Queue 接口，具备队列的性能
Deque 接口，具备双端队列的性能
BlockingQueue 接口，可作为阻塞队列应用
7.6 哪些类实现了 BlockDeque 接口？
LinkedBlockingDeque
八、使命必达 TransferQueue 接口
8.1 Transfer 怎么了解？
如果有消费者正在获取元素，则将队列中的元素传递给消费者。如果没有消费者，则期待消费者生产。我把它称作使命必达队列，必须将工作实现能力返回。
8.2 生存中的案例
针对 TransferQueue 的 transfer 办法
圆通快递员要将小明的 2 个快递送货到门，韵达快递员也想将小明的 2 个快递送货到门。小明一次只能拿一个，快递员必须等小明拿了一个后，能力持续给第二个。
针对 TransferQueue 的 tryTransfer 办法
圆通快递员要将小明的 2 个快递送货到门，韵达快递员也想将小明的 2 个快递送货到门。发现小明不在家，就把快递间接放到菜鸟驿站了。
针对 TransferQueue 的 tryTransfer 超时办法
圆通快递员要将小明的 2 个快递送货到门，韵达快递员也想将小明的 2 个快递送货到门。发现小明不在家，于是先等了 5 分钟，发现小明还没有回来，就把快递间接放到菜鸟驿站了。
8.3 TransferQueue 的原理解析
transfer 办法的原理
原理图解释：生产者线程 Producer Thread 尝试将元素 B 传给消费者线程，如果没有消费者线程，则将元素 B 放到尾节点。并且生产者线程期待元素 B 被生产。当元素 B 被生产后，生产者线程返回。
如果以后有消费者正在期待接管元素（消费者通过 take 办法或超时限度的 poll 办法时），transfer 办法能够把生产者传入的元素立即 transfer（传输）给消费者。
如果没有消费者期待接管元素，transfer 办法会将元素放在队列的 tail（尾）节点，并等到该元素被消费者生产了才返回。
tryTransfer(E e)
试探生产者传入的元素是否能间接传给消费者。
如果没有消费者期待接管元素，则返回 false。
和 transfer 办法的区别是，无论消费者是否接管，办法立刻返回。
tryTransfer(E e, long timeout, TimeUnit unit)
带有工夫限度的 tryTransfer 办法。
试图把生产者传入的元素间接传给消费者。
如果没有消费者生产该元素则期待指定的工夫再返回。
如果超时了还没有生产元素，则返回 false。
如果在超时工夫内生产了元素，则返回 true。
getWaitingConsumerCount()
获取通过 BlockingQueue.take()办法或超时限度 poll 办法期待承受元素的消费者数量。近似值。
返回期待接管元素的消费者数量。
hasWaitingConsumer()
获取是否有通过 BlockingQueue.tabke()办法或超时限度 poll 办法期待承受元素的消费者。
返回 true 则示意至多有一个期待消费者。
8.3 TransferQueue 接口继承了哪些接口？
BlockingQueue 接口，可作为阻塞队列应用
Queue 接口，可作为队列应用
8.4 哪些类实现了 TransferQueue 接口？
LinkedTranferQueue 接口
九、优先由你 PriorityQueue 类
9.1 了解 PriorityQueue 类
本应该依照升序排序
依照倒序排序
依照自定义优先级排序
PriorityQueue 是一个反对优先级的无界阻塞队列。
默认天然程序升序排序。
能够通过结构参数 Comparator 来对元素进行排序。
public PriorityQueue(Comparator<? super E> comparator) {this(DEFAULT_INITIAL_CAPACITY, comparator);
}自定义实现 comapreTo()办法来指定元素排序规定。
public Comparator<? super E> comparator() {return comparator;}不容许插入 null 元素。
实现 PriorityQueue 接口的类，不保障线程平安，除非是 PriorityBlockingQueue。
PriorityQueue 的迭代器不能保障以任何特定程序遍历元素，如果须要有序遍历，请思考应用 Arrays.sort(pq.toArray)。
进列 (offer、add) 和入列（poll、remove()）的工夫复杂度 O(log(n))。
remove(Object) 和 contains(Object)的算法工夫复杂度 O(n)。
peek、element、size 的算法工夫复杂度为 O(1)。
9.2 PriorityQueue 类继承了哪些类？
AbstractQueue 抽象类，具备队列的性能
9.2 PriorityQueue 类实现了哪些接口？
Queue 接口，可作为队列应用。
十、双向链表 LinkedList 类
10.1 LinkedList 的构造
LinkedList 实现了 List 和 Deque 接口，所以是一种双链表构造，能够当作堆栈、队列、双向队列应用。
一个双向列表的每一个元素都有三个整数值：元素、向后的节点链接、向前的节点链接
LinkedList 的构造
咱们来看下节点类 Node
10.2 与 ArrayList 的区别
1.LinkedList 的减少和删除效率绝对较高，而查找和批改的效率绝对较低。
2. 以下状况倡议应用 ArrayList 频繁拜访列表中的一个元素。只在列表的首尾增加元素。
3. 以下状况倡议应用 LinkedList 频繁地在列表结尾、两头、开端增加和删除元素。须要通过循环迭代来拜访列表中的元素。
10.3 LinkedList 不是线程平安的
LinkedList 不是线程平安的，所以能够应用如下形式保障线程平安。
List list = Collections.synchronizedList(new LinkedList<>());
小结
Java 中的 Queue 家族，总共波及到 18 种 Queue，明天给大家分享的局部内容，其余部分今天再给大家分享哈~
今日份分享已完结，请大家多多包涵和指导！
