集合：Queue

一、 队列

队列与栈是相对的一种数据结构。只允许在一端进行插入操作，而在另一端进行删除操作的线性表。栈的特点是后进先出，而队列的特点是先进先出。其中队列包括单向队列和双向对列：

1、单向队列

单向队列比较简单，只能向队尾添加元素，从队头删除元素。
一个队列只要能入队，和出队就可以了。这个队列的接口就定义好了，具体的实现有很多种办法，例如，可以使用数组做存储，也可以使用链表做存储。

public interface Queue {
    public boolean add(Object element); // 将一个元素放到队尾，如果成功，返回true
    public Object remove(); // 将一个元素从队头删除，如果成功，返回true
}

2、双端对列

如果一个队列的头和尾都支持元素入队，出队，那么这种队列就称为双向队列，英文是Deque。

public interface Deque<E> extends Queue<E> {
void addFirst(E e);
void addLast(E e);
E removeLast();
E removeFirst();//NoSuchElementException if this deque is empty

从源代码中可以发现这四个实现了双端对列的含义，可以removeFirst头删（如果不满足就会抛出异常下面几个也类似）、尾删、头部添加、尾部添加；

二、 双端对列Deque

Deque接口是Queue接口子接口。它代表一个双端队列。Deque接口在Queue接口的基础上增加了一些针对双端添加和删除元素的方法。LinkedList也实现了Deque接口，所以也可以被当作双端队列使用。

E pop();
E peek();
E peekFirst();
E peekLast();

从源代码中可以看出Deque也可以当做一个栈来使用，因为其中有pop、peek这两种方法。其中还有一些是后面加First和Last表明其从哪端进行操作。

1. ArrayDeque

ArrayDeque是一个循环队列。它的实现比较高效，它的思路是:引入两个游标，head 和 tail，如果向队列里，插入一个元素，就把 tail 向后移动。如果从队列中删除一个元素，就把head向后移动。

• 底层实现

底层是基于数组实现的，并且没有容量的限制，可根据需求自动进行扩容的双端对列。

transient Object[] elements;

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable
{

从这可以看出其实现了Deque接口

• 容量机制

public ArrayDeque() {
    elements = new Object[16];
}

默认的初始容量为16；最小为8；

非默认情况下的初始容量：构造函数ArrayDeque（int n）传入参数n，allocateElements（n）寻找大于n的最近2的幂，作为初始容量 。

• 扩容机制

private void doubleCapacity() {
    assert head == tail;
    int p = head;
    int n = elements.length;
    int r = n - p; // number of elements to the right of p
    int newCapacity = n << 1;
    if (newCapacity < 0)
        throw new IllegalStateException("Sorry, deque too big");
    Object[] a = new Object[newCapacity];
    System.arraycopy(elements, p, a, 0, r);
    System.arraycopy(elements, 0, a, r, p);
    elements = a;
    head = 0;
    tail = n;
}

可以看出其底层需要扩容的话，先把数组长度扩大一倍，之后把原数据拷贝到新数组中。如果都节点和尾结点相等时就需要扩容。

• 效率

  当用作栈stack时，比stack快，当用作对列Queue时，比LinkedList快。（一是因为它内部结构是一个循环数组只需要操作索引，二是没有Synchronized修饰方法）

• 线程安全性

  由于它的方法没有Synchronized修饰所以它是线程非安全的。

三、优先对列PriorityQueue

• 简介PriprityQueue

  PriorityQueue又叫做优先级队列，保存队列元素的顺序不是按照及加入队列的顺序，而是按照队列元素的大小进行重新排序。因此当调用peek()或poll()方法取出队列中头部的元素时，并不是取出最先进入队列的元素，而是取出队列的最小元素。（小根堆）

  PriorityQueue使用了一个高效的数据结构：堆。底层是使用数组保存数据。还会进行排序，优先将元素的最小值存到队头。

• PriorityQueue的排序方法

  PriorityQueue中的元素可以默认自然排序或者通过提供的Comparator（比较器）在队列实例化时指定的排序方式进行排序。

 @throws ClassCastException if elements of the specified collection
 *         cannot be compared to one another according to the priority
 *         queue's ordering

当PriorityQueue中没有指定的Comparator时，加入PriorityQueue的元素必须实现了Comparable接口（元素是可以进行比较的），否则会导致 ClassCastException。

• PriorityQueue本质

PriorityQueue 本质也是一个动态数组，在这一方面与ArrayList是一致的。构造方法：

public PriorityQueue() {
    this(DEFAULT_INITIAL_CAPACITY, null);
}
public PriorityQueue(Comparator<? super E> comparator) {
    this(DEFAULT_INITIAL_CAPACITY, comparator);
}
public PriorityQueue(int initialCapacity,
                     Comparator<? super E> comparator) {
    // Note: This restriction of at least one is not actually needed,
    // but continues for 1.5 compatibility
    if (initialCapacity < 1)
        throw new IllegalArgumentException();
    this.queue = new Object[initialCapacity];
    this.comparator = comparator;
}

PriorityQueue调用默认的构造方法时，使用默认的初始容量（DEFAULT_IITIAL_CAPACITY = 11）创建一个PriorityQueue，并根据其自然顺序来排序其元素（使用加入其中的集合元素实现的Comparable）。

当使用指定容量的构造方法时，使用指定的初始容量创建一个 PriorityQueue，并根据其自然顺序来排序其元素（使用加入其中的集合元素实现的Comparable）

当使用指定的初始容量创建一个 PriorityQueue，并根据指定的比较器comparator来排序其元素。当添加元素到集合时，会先检查数组是否还有余量，有余量则把新元素加入集合，没余量则调用 grow()方法增加容量，然后调用siftUp将新加入的元素排序插入对应位置。

• PriorityQueue注意事项

1.PriorityQueue不是线程安全的。如果多个线程中的任意线程从结构上修改了列表， 则这些线程不应同时访问 PriorityQueue 实例，这时请使用线程安全的PriorityBlockingQueue 类。
2.不允许插入 null 元素。
3.PriorityQueue实现插入方法（offer、poll、remove() 和 add 方法） 的时间复杂度是O(log(n)) ；实现 remove(Object) 和 contains(Object) 方法的时间复杂度是O(n) ；实现检索方法（peek、element 和 size）的时间复杂度是O(1)。所以在遍历时，若不需要删除元素，则以peek的方式遍历每个元素。
4.方法iterator()中提供的迭代器并不保证以有序的方式遍历PriorityQueue中的元素。