JCF中的Queue、Deque集合

Queue（队列）、Deque（双端队列）集合是JCF中另一种重要的集合。队列存储的数据允许从结构的一端进行添加操作（入队操作），并且从结构的另一端进行移除操作（出队操作）。进行入队操作的一端称为队列尾部；进行出队操作的一端称为队列头部。双端队列是指可以在一端既进行入队操作，又进行出队操作的队列结构。

注意：队列和双端队列都不允许在除了队列头部或队列尾部的其他索引位上进行数据的读/写操作。在JCF中，具有队列操作特性的集合都实现或间接实现了java.util.Queue接口；具有双端队列操作特性的集合都实现或间接实现了java.util.Deque接口。

JCF中的java.util.Queue接口、java.util.Deque接口涉及的部分重要接口、抽象类及其在java.util包中的具体实现类如图2-1所示。在JCF中，还有大量关于Queue（队列）接口和Deque（双端队列）接口的实现集合位于java.util.concurrent包中，这些集合都是可以工作在高并发场景中的队列或 双 端 队 列 ， 如 LinkedBlockingDeque 队 列 、 ArrayBlockingQueue 队 列 、PriorityBlockingQueue队列等。本书会在后续章节中介绍JUC的必要知识后，再对这些队列进行详细介绍

java.util.ArrayDeque 集 合 和 java.util.PriorityQueue 队 列 分 别 是Queue （ 队 列 ） 接 口 和 Deque （ 双 端 队 列 ） 接 口 在 JCF 中 的 基 础 集 合 。

ArrayDeque集合为了保证对已有数组控件的充分利用，使用的是可循环的双指针数组（但不代表不进行扩容操作）；PriorityQueue队列使用的是小顶堆结构，对基于权值的排序性能进行了优化。

Queue集合实现——ArrayDeque

ArrayDeque集合是从JDK 1.6开始推出的，它是一个基于数组（可扩容的数组）结构实现的双端队列。与普通的数组结构相比，这种数组结构是一种可循环使用的数组结构，可以有效减少数组扩容的次数。ArrayDeque集合是线程不安全的，不能在多线程场景中使用。

ArrayDeque集合既有队列、双端队列的操作特点，又有栈结构的操作特点。因此在JDK 1.6发布后，ArrayDeque集合是官方推荐的继Stack集合和LinkedList集合后，用于进行栈结构操作的新集合。官方文档中的推荐原因如下。

在本书中，实现了Queue接口的集合都可以称为队列，这里之所以没有将ArrayDeque集合称为队列，主要是因为ArrayDeque集合实现了Deque接口（间接实现了Queue接口），因此同时具有队列和双端队列的工作特点，如果将ArrayDeque集合统称为ArrayDeque队列，则会使读者忽略其双端队列的工作特点。

ArrayDeque集合的主要结构及相关方法

ArrayDeque集合内部的主要结构是一个数组，ArrayDeque集合的设计者将这个数组设计成了可循环利用的形式，称为循环数组。循环数组是一个固定大小的数组，并且定义了一个动态的有效数据范围（这个有效数据范围的长度不会大于数组的固定长度），只有在这个有效数据范围内的数据对象才能被读/写，并且这个有效数据范围不受数组的头部和尾部限制，如图2-2所示。

根据图2-2可知，ArrayDeque集合的内部结构是一个循环数组，该循环数组在ArrayDeque集合中的变量名为elements；ArrayDeque集合中有一个名为head的属性，主要用于标识下一次进行移除操作的数据对象索引位（队列头部的索引位）；ArrayDeque集合中还有一个名为tail的属性，主要用于标识下一次进行添加操作的数据对象索引位（队列尾部的索引位）。head属性和tail属性所标识的有效数据范围在不停地变化，甚至有时tail属性记录的索引值会小于head属性记录的索引值，但这丝毫不影响它们对有效数据范围的标识。将图2-2中的循环数组展开，如图2-3所示，可以发现，tail属性记录的索引值小于head属性记录的索引值。

当tail属性指向数组中的最后一个索引位并进行下一次添加操作时，数组不一定进行扩容操作，更可能发生的情况是，tail属性重新从当前数组的0号索引位开始，循环利用有效数据范围外的数组索引位存储新的数据对象（ArrayDeque集合内部虽然是一个可以循环利用的数组结构，但同样存在扩容场景，并且在扩容时需要考虑的各种情况较为复杂，在后续章节中会进行详细说明）。