4.Queue

(1)Queue

Queue用于模拟队列这种数据结构，实现“FIFO”等数据结构。即第一个放进去就是第一个拿出来的元素（从一端进去，从另一端出来）。队列常作被当作一个可靠的将对象从程序的某个区域传输到另一个区域的途径。通常，队列不允许随机访问队列中的元素。

Queue 接口并未定义阻塞队列的方法，而这在并发编程中是很常见的。BlockingQueue 接口定义了那些等待元素出现或等待队列中有可用空间的方法，这些方法扩展了此接口。

Queue 实现通常不允许插入 null 元素，尽管某些实现（如 LinkedList）并不禁止插入 null。即使在允许 null 的实现中，也不应该将 null 插入到 Queue 中，因为 null 也用作 poll 方法的一个特殊返回值，表明队列不包含元素。

LinkedList提供了方法以支持队列的行为，并且实现了Queue接口。通过LinkedList向上转型（up cast）为Queue，看Queue的实现就知道相对于LinkedList，Queue添加了element、offer、peek、poll、remove方法
offer：在允许的情况下，将一个元素插入到队尾，或者返回false
peek，element：在不移除的情况下返回队头，peek在队列为空返回null，element抛异常NoSuchElementException
poll,remove：移除并返回队头，poll当队列为空是返回null，remove抛出NoSuchElementException异常
注意：queue.offer在自动包装机制会自动的把random.nextInt转化程Integer，把char转化成Character

(2)Deque

Deque是Queue的子接口,我们知道Queue是一种队列形式,而Deque则是双向队列,它支持从两个端点方向检索和插入元素,因此Deque既可以支持LIFO形式也可以支持LIFO形式.Deque接口是一种比Stack和Vector更为丰富的抽象数据形式,因为它同时实现了以上两者.
添加功能
void push(E) 向队列头部插入一个元素,失败时抛出异常
void addFirst(E) 向队列头部插入一个元素,失败时抛出异常
void addLast(E) 向队列尾部插入一个元素,失败时抛出异常
boolean offerFirst(E) 向队列头部加入一个元素,失败时返回false
boolean offerLast(E) 向队列尾部加入一个元素,失败时返回false
获取功能
E getFirst() 获取队列头部元素,队列为空时抛出异常
E getLast() 获取队列尾部元素,队列为空时抛出异常
E peekFirst() 获取队列头部元素,队列为空时返回null
E peekLast() 获取队列尾部元素,队列为空时返回null
删除功能
boolean removeFirstOccurrence(Object) 删除第一次出现的指定元素,不存在时返回false
boolean removeLastOccurrence(Object) 删除最后一次出现的指定元素,不存在时返回false
弹出功能
E pop() 弹出队列头部元素,队列为空时抛出异常
E removeFirst() 弹出队列头部元素,队列为空时抛出异常
E removeLast() 弹出队列尾部元素,队列为空时抛出异常
E pollFirst() 弹出队列头部元素,队列为空时返回null
E pollLast() 弹出队列尾部元素,队列为空时返回null
迭代器
Iterator descendingIterator() 返回队列反向迭代器

同Queue一样,Deque的实现也可以划分成通用实现和并发实现.
　　通用实现主要有两个实现类ArrayDeque和LinkedList.
　　ArrayDeque是个可变数组,它是在Java 6之后新添加的,而LinkedList是一种链表结构的list,LinkedList要比ArrayDeque更加灵活,因为它也实现了List接口的所有操作,并且可以插入null元素,这在ArrayDeque中是不允许的.
　　从效率来看,ArrayDeque要比LinkedList在两端增删元素上更为高效,因为没有在节点创建删除上的开销.最适合使用LinkedList的情况是迭代队列时删除当前迭代的元素.此外LinkedList可能是在遍历元素时最差的数据结构,并且也LinkedList占用更多的内存,因为LinkedList是通过链表连接其整个队列,它的元素在内存中是随机分布的,需要通过每个节点包含的前后节点的内存地址去访问前后元素.
　　总体ArrayDeque要比LinkedList更优越,在大队列的测试上有3倍与LinkedList的性能,最好的是给ArrayDeque一个较大的初始化大小,以避免底层数组扩容时数据拷贝的开销.
　　LinkedBlockingDeque是Deque的并发实现,在队列为空的时候,它的takeFirst,takeLast会阻塞等待队列处于可用状态

(3)ArrayDeque

ArrayDeque类是双端队列的实现类，类的继承结构如下面，继承自AbastractCollection（该类实习了部分集合通用的方法，其实现了Collection接口），其实现的接口Deque接口中定义了双端队列的主要的方法，比如从头删除，从尾部删除，获取头数据，获取尾部数据等等。
public class ArrayDeque extends AbstractCollection implements Deque, Cloneable, Serializable

ArrayDeque基本特征
就其实现而言，ArrayDeque采用了循环数组的方式来完成双端队列的功能。
1. 无限的扩展，自动扩展队列大小的。（当然在不会内存溢出的情况下。）
2. 非线程安全的，不支持并发访问和修改。
3. 支持fast-fail.
4. 作为栈使用的话比比栈要快.
5. 当队列使用比linklist要快。
6. null元素被禁止使用。

最小初始化容量限制8(必须是2的幂次)

扩容:之所以说该ArrayDeque容量无限制，是因为只要检测到head==tail的时候，就直接调用doubleCapacity方法进行扩容。

删除元素:删除元素的基本思路为确定那一侧的数据少，少的一侧移动元素位置，这样效率相对于不比较更高些，然后，判断head是跨越最大值还是为跨越最大值，继而可以分两种不同的情况进行拷贝。但是该方法比较慢，因为存在数组的拷贝。

获取并删除元素:这里在举个简单点的例子，中间判断是不是null，可以看出该队列不支持null,通过把其值设为null就算是将其删除了。然后head向递增的方向退一位即可。

ArrayDeque和LinkedList是Deque的两个通用实现
ArrayDeque不是线程安全的。
ArrayDeque不可以存取null元素，因为系统根据某个位置是否为null来判断元素的存在。
当作为栈使用时，性能比Stack好；当作为队列使用时，性能比LinkedList好。

1.添加元素
addFirst(E e)在数组前面添加元素
addLast(E e)在数组后面添加元素
offerFirst(E e) 在数组前面添加元素，并返回是否添加成功
offerLast(E e) 在数组后天添加元素，并返回是否添加成功

2.删除元素
removeFirst()删除第一个元素，并返回删除元素的值,如果元素为null，将抛出异常
pollFirst()删除第一个元素，并返回删除元素的值，如果元素为null，将返回null
removeLast()删除最后一个元素，并返回删除元素的值，如果为null，将抛出异常
pollLast()删除最后一个元素，并返回删除元素的值，如果为null，将返回null
removeFirstOccurrence(Object o) 删除第一次出现的指定元素
removeLastOccurrence(Object o) 删除最后一次出现的指定元素

3.获取元素
getFirst() 获取第一个元素,如果没有将抛出异常
getLast() 获取最后一个元素，如果没有将抛出异常

4.队列操作
add(E e) 在队列尾部添加一个元素
offer(E e) 在队列尾部添加一个元素，并返回是否成功
remove() 删除队列中第一个元素，并返回该元素的值，如果元素为null，将抛出异常(其实底层调用的removeFirst()) poll() 删除队列中第一个元素，并返回该元素的值,如果元素为null，将返回null(其实调用的是pollFirst())
element() 获取第一个元素，如果没有将抛出异常
peek() 获取第一个元素，如果返回null

5.栈操作
push(E e) 栈顶添加一个元素
pop(E e) 移除栈顶元素,如果栈顶没有元素将抛出异常

6.其他
size() 获取队列中元素个数
isEmpty() 判断队列是否为空
iterator() 迭代器，从前向后迭代
descendingIterator() 迭代器，从后向前迭代
contain(Object o) 判断队列中是否存在该元素
toArray() 转成数组
clear() 清空队列
clone() 克隆(复制)一个新的队列

(4)PriorityQueue

我们知道队列是遵循先进先出（First-In-First-Out）模式的，但有些时候需要在队列中基于优先级处理对象。举个例子，比方说我们有一个每日交易时段生成股票报告的应用程序，需要处理大量数据并且花费很多处理时间。客户向这个应用程序发送请求时，实际上就进入了队列。我们需要首先处理优先客户再处理普通用户。在这种情况下，Java的PriorityQueue(优先队列)会很有帮助。

PriorityQueue类在Java1.5中引入并作为 Java Collections Framework 的一部分。PriorityQueue是基于优先堆的一个无界队列，这个优先队列中的元素可以默认自然排序或者通过提供的Comparator（比较器）在队列实例化的时排序。
优先队列不允许空值，而且不支持non-comparable（不可比较）的对象，比如用户自定义的类。优先队列要求使用Java Comparable和Comparator接口给对象排序，并且在排序时会按照优先级处理其中的元素。
优先队列的头是基于自然排序或者Comparator排序的最小元素。如果有多个对象拥有同样的排序，那么就可能随机地取其中任意一个。当我们获取队列时，返回队列的头对象。
优先队列的大小是不受限制的，但在创建时可以指定初始大小。当我们向优先队列增加元素的时候，队列大小会自动增加。
PriorityQueue是非线程安全的，所以Java提供了PriorityBlockingQueue（实现BlockingQueue接口）用于Java多线程环境。
由于知道PriorityQueue是基于Heap的，当新的元素存储时，会调用siftUpUsingComparator方法


PriorityQueue的逻辑结构是一棵完全二叉树，存储结构其实是一个数组。逻辑结构层次遍历的结果刚好是一个数组。
PriorityQueue优先队列,它逻辑上使用堆结构（完全二叉树）实现，物理上使用动态数组实现，并非像TreeMap一样完全有序，但是如果按照指定方式出队，结果可以是有序的。
这里的堆是一种数据结构而非计算机内存中的堆栈。堆结构在逻辑上是完全二叉树，物理存储上是数组。
完全二叉树并不是堆结构，堆结构是不完全有序的完全二叉树。

(5)BlockingQueue

Java中Queue的最重要的应用大概就是其子类BlockingQueue了。
考虑到生产者消费者模型，我们有多个生产者和多个消费者，生产者不断提供资源给消费者，但如果它们的生产/消费速度不匹配或者不稳定，则会造成大量的生产者闲置/消费者闲置。此时，我们需要使用一个缓冲区来存储资源，即生产者将资源置于缓冲区，而消费者不断地从缓冲区中取用资源，从而减少了闲置和阻塞。
BlockingQueue，阻塞队列，即可视之为一个缓冲区应用于多线程编程之中。当队列为空时，它会阻塞所有消费者线程，而当队列为满时，它会阻塞所有生产者线程。
在queue的基础上，BlockingQueue又添加了以下方法：
put：队列末尾添加一个元素，若队列已满阻塞。
take：移除并返回队列头部元素，若队列已空阻塞。
drainTo:一次性获取所有可用对象，可以用参数指定获取的个数，该操作是原子操作，不需要针对每个元素的获取加锁。

(6) ArrayBlockingQueue

由一个定长数组和两个标识首尾的整型index标识组成，生产者放入数据和消费者取出数据对于ArrayBlockingQueue而言使用了同一个锁（一个私有的ReentrantLock），因而无法实现真正的并行。可以在初始化时除长度参数以外，附加一个boolean类型的变量，用于给其私有的ReentrantLock进行初始化（初始化是否为公平锁，默认为false）。

(7) LinkedBlockingQueue

LinkedBlockingQueue的最大特点是，若没有指定最大容量，其可以视为无界队列（有默认最大容量限制,往往系统资源耗尽也无法达到）。即，不对生产者的行为加以限制，只在队列为空的时候限制消费者的行为。LinkedBlockingQueue采用了读写分离的两个ReentrantLock去控制put和take，因而有了更好的性能（类似读写锁提供读写场景下更好的性能），如下：
/ Lock held by take, poll, etc */ private final ReentrantLock takeLock = new ReentrantLock(); / Wait queue for waiting takes / private final Condition notEmpty = takeLock.newCondition(); /** Lock held by put, offer, etc / private final ReentrantLock putLock = new ReentrantLock(); /* Wait queue for waiting puts / private final Condition notFull = putLock.newCondition();
ArrayBlockingQueue和LinkedBlockingQueue是最常用的两种阻塞队列。

(8) PriorityBlockingQueue

PriorityBlockingQueue是对PriorityQueue的包装，因而也是一个优先队列。其优先级默认是直接比较，大者先出队，也可以从构造器传入自定义的Comparator。由于PriorityQueue从实现上是一个无界队列，PriorityBlockingQueue同样是一个无界队列，对生产者不做限制。

(9) DelayQueue

DelayQueue是在PriorityBlockingQueue的基础上包装产生的，它用于存放Delayed对象，该队列的头部是延迟期满后保存时间最长的Delayed元素（即，以时间为优先级利用PriorityBlockingQueue），当没有元素延迟期满时，对其进行poll操作将会返回Null。take操作会阻塞。

(10) SynchronousQueue

SynchronousQueue十分特殊，它没有容量——换言之，它是一个长度为0的BlockingQueue，生产者和消费者进行的是无中介的直接交易，当生产者/消费者没有找到合适的目标时，即会发生阻塞。但由于减少了环节，其整体性能在一些系统中可能更加适合。该方法同样支持在构造时确定为公平/默认的非公平模式，如果是非公平模式，有可能会导致某些生产者/消费者饥饿。