集合框架 Queue篇（1）---ArrayDeque

Queue

------------
1.ArrayDeque, （数组双端队列）
2.PriorityQueue, （优先级队列）
3.ConcurrentLinkedQueue, （基于链表的并发队列）

4.DelayQueue,                                         （延期阻塞队列）（阻塞队列实现了BlockingQueue接口）
5.ArrayBlockingQueue,           （基于数组的并发阻塞队列）
6.LinkedBlockingQueue,        （基于链表的FIFO阻塞队列）
7.LinkedBlockingDeque, （基于链表的FIFO双端阻塞队列）
8.PriorityBlockingQueue,        （带优先级的无界阻塞队列）
9.SynchronousQueue                       （并发同步阻塞队列）
-----------------------------------------------------

队列是只能对头尾两个元素操作的数据结构，

单向队列只能从头remove（poll），从尾add（offer），

双端队列则头尾均可执行插入和删除操作。

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

看一下  Queue接口的API：

public interface Queue<E> extends Collection<E>

在处理元素前用于保存元素的collection。除了基本的Collection操作以外，队列还提供了插入、提取、和检查操作。每个方法都有两种形式：一种抛出异常（操作失败时），另一种返回一个特殊值（null或false，具体取决于操作）。插入操作的后一种形式是用于专门为有容量限制的 Queue实现设计的；在大多数实现中，插入操作不会失败。

抛出异常返回特殊值插入add(e)offer(e)移除remove()poll()检查element()peek()

队列通常（但并非一定）以 FIFO（先进先出）的方式排序各个元素。不过优先级队列和 LIFO 队列（或堆栈）例外，前者根据提供的比较器或元素的自然顺序对元素进行排序，后者按 LIFO（后进先出）的方式对元素进行排序。无论使用哪种排序方式，队列的头都是调用 或 所移除的元素。在 FIFO 队列中，所有的新元素都插入队列的末尾。其他种类的队列可能使用不同的元素放置规则。每个 Queue实现必须指定其顺序属性。

如果可能， 方法可插入一个元素，否则返回 false。这与 方法不同，该方法只能通过抛出未经检查的异常使添加元素失败。offer方法设计用于正常的失败情况，而不是出现异常的情况，例如在容量固定（有界）的队列中。

和 方法可移除和返回队列的头。到底从队列中移除哪个元素是队列排序策略的功能，而该策略在各种实现中是不同的。remove()和 poll()方法仅在队列为空时其行为有所不同：remove()方法抛出一个异常，而 poll()方法则返回 null。

和 返回，但不移除，队列的头。

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

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

Queue实现通常未定义 equals和 hashCode方法的基于元素的版本，而是从 Object类继承了基于身份的版本，因为对于具有相同元素但有不同排序属性的队列而言，基于元素的相等性并非总是定义良好的。

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

看一下 BlockingQueue(阻塞队列)的API：

public interface BlockingQueue<E> extends <E>

支持两个附加操作的 ，这两个操作是：获取元素时等待队列变为非空，以及存储元素时等待空间变得可用。

BlockingQueue方法以四种形式出现，对于不能立即满足但可能在将来某一时刻可以满足的操作，这四种形式的处理方式不同：第一种是抛出一个异常，第二种是返回一个特殊值（null或 false，具体取决于操作），第三种是在操作可以成功前，无限期地阻塞当前线程，第四种是在放弃前只在给定的最大时间限制内阻塞。下表中总结了这些方法：

抛出异常特殊值阻塞超时插入add(e)offer(e)put(e)offer(e, time, unit)移除remove()poll()take()poll(time, unit)检查element()peek()不可用不可用

BlockingQueue不接受 null元素。试图 add、put或 offer一个 null元素时，某些实现会抛出 NullPointerException。null被用作指示 poll操作失败的警戒值。

BlockingQueue可以是限定容量的。它在任意给定时间都可以有一个 remainingCapacity，超出此容量，便无法无阻塞地 put附加元素。没有任何内部容量约束的 BlockingQueue总是报告 Integer.MAX_VALUE的剩余容量。

BlockingQueue实现主要用于生产者-使用者队列，但它另外还支持 接口。因此，举例来说，使用 remove(x)从队列中移除任意一个元素是有可能的。然而，这种操作通常不会有效执行，只能有计划地偶尔使用，比如在取消排队信息时。

BlockingQueue实现是线程安全的。所有排队方法都可以使用内部锁或其他形式的并发控制来自动达到它们的目的。然而，大量的Collection 操作（addAll、containsAll、retainAll和 removeAll）没有必要自动执行，除非在实现中特别说明。因此，举例来说，在只添加了 c中的一些元素后，addAll(c)有可能失败（抛出一个异常）。

BlockingQueue实质上不支持使用任何一种“close”或“shutdown”操作来指示不再添加任何项。这种功能的需求和使用有依赖于实现的倾向。例如，一种常用的策略是：对于生产者，插入特殊的 end-of-stream或 poison对象，并根据使用者获取这些对象的时间来对它们进行解释。

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

看一下 Deque(双端队列)的API：

public interface Deque<E> extends <E>

一个线性 collection，支持在两端插入和移除元素。名称 deque是“double ended queue（双端队列）”的缩写，通常读为“deck”。大多数 Deque实现对于它们能够包含的元素数没有固定限制，但此接口既支持有容量限制的双端队列，也支持没有固定大小限制的双端队列。

此接口定义在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。每种方法都存在两种形式：一种形式在操作失败时抛出异常，另一种形式返回一个特殊值（null或 false，具体取决于操作）。插入操作的后一种形式是专为使用有容量限制的 Deque实现设计的；在大多数实现中，插入操作不能失败。

下表总结了上述 12 种方法：

第一个元素（头部）最后一个元素（尾部）抛出异常特殊值抛出异常特殊值插入addFirst(e)offerFirst(e)addLast(e)offerLast(e)移除removeFirst()pollFirst()removeLast()pollLast()检查getFirst()peekFirst()getLast()peekLast()

此接口扩展了 接口。在将双端队列用作队列时，将得到 FIFO（先进先出）行为。将元素添加到双端队列的末尾，从双端队列的开头移除元素。从 Queue接口继承的方法完全等效于 Deque方法，如下表所示：

Queue方法等效 Deque方法add(e)addLast(e)offer(e)offerLast(e)remove()removeFirst()poll()pollFirst()element()getFirst()peek()peekFirst()

双端队列也可用作 LIFO（后进先出）堆栈。应优先使用此接口而不是遗留 类。在将双端队列用作堆栈时，元素被推入双端队列的开头并从双端队列开头弹出。堆栈方法完全等效于 Deque方法，如下表所示：

堆栈方法等效 Deque方法push(e)addFirst(e)pop()removeFirst()peek()peekFirst()

注意，在将双端队列用作队列或堆栈时， 方法同样正常工作；无论哪种情况下，都从双端队列的开头抽取元素。

此接口提供了两种移除内部元素的方法： 和 。

与 接口不同，此接口不支持通过索引访问元素。

虽然 Deque实现没有严格要求禁止插入 null 元素，但建议最好这样做。建议任何事实上允许 null 元素的 Deque实现用户最好不要利用插入 null 的功能。这是因为各种方法会将 null用作特殊的返回值来指示双端队列为空。

Deque实现通常不定义基于元素的 equals和 hashCode方法，而是从 Object类继承基于身份的 equals和 hashCode方法。

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

ArrayDeque（数组双端队列）


ArrayDeque实现了Deque双端队列接口，大小可变的数组实现并且没有容量的限制（不过，容量应该<=2 ^ 30）。

//数组双端队列ArrayDeque的源码解析
public class ArrayDeque<E> extends AbstractCollection<E> implements Deque<E>, Cloneable, Serializable{
    /**
     * 存放队列元素的数组，数组的长度为“2的指数”
     */
    private transient E[] elements;

    /**
     *队列的头部索引位置，（被remove（）或pop（）操作的位置），当为空队列时，首尾index相同
     */
    private transient int head;

    /**
     * 队列的尾部索引位置，(被 addLast(E), add(E), 或 push(E)操作的位置).
     */
    private transient int tail;

    /**
     * 队列的最小容量（大小必须为“2的指数”）
     */
    private static final int MIN_INITIAL_CAPACITY = 8;

    // ******  Array allocation and resizing utilities ******

    /**
     * 根据所给的数组长度，得到一个比该长度大的最小的2^p的真实长度，并建立真实长度的空数组
     */
    private void allocateElements(int numElements) {
        int initialCapacity = MIN_INITIAL_CAPACITY;
        if (numElements >= initialCapacity) {
            initialCapacity = numElements;
            initialCapacity |= (initialCapacity >>>  1);
            initialCapacity |= (initialCapacity >>>  2);
            initialCapacity |= (initialCapacity >>>  4);
            initialCapacity |= (initialCapacity >>>  8);
            initialCapacity |= (initialCapacity >>> 16);
            initialCapacity++;

            if (initialCapacity < 0)   // Too many elements, must back off
                initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
        }
        elements = (E[]) new Object[initialCapacity];
    }

    /**
     * 当队列首尾指向同一个引用时，扩充队列的容量为原来的两倍，并对元素重新定位到新数组中
     */
    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 = (E[])a;
        head = 0;
        tail = n;
    }

    /**
     * 拷贝队列中的元素到新数组中
     */
    private <T> T[] copyElements(T[] a) {
        if (head < tail) {
            System.arraycopy(elements, head, a, 0, size());
        } else if (head > tail) {
            int headPortionLen = elements.length - head;
            System.arraycopy(elements, head, a, 0, headPortionLen);
            System.arraycopy(elements, 0, a, headPortionLen, tail);
        }
        return a;
    }

    /**
     * 默认构造队列，初始化一个长度为16的数组
     */
    public ArrayDeque() {
        elements = (E[]) new Object[16];
    }

    /**
     * 指定元素个数的构造方法
     */
    public ArrayDeque(int numElements) {
        allocateElements(numElements);
    }

    /**
     * 用一个集合作为参数的构造方法
     */
    public ArrayDeque(Collection<? extends E> c) {
        allocateElements(c.size());
        addAll(c);
    }

    //插入和删除的方法主要是： addFirst(),addLast(), pollFirst(), pollLast()。
    //其他的方法依赖于这些实现。
    /**
     * 在双端队列的前端插入元素,元素为null抛异常
     */
    public void addFirst(E e) {
        if (e == null)
            throw new NullPointerException();
        elements[head = (head - 1) & (elements.length - 1)] = e;
        if (head == tail)
            doubleCapacity();
    }

    /**
     *在双端队列的末端插入元素，元素为null抛异常
     */
    public void addLast(E e) {
        if (e == null)
            throw new NullPointerException();
        elements[tail] = e;
        if ( (tail = (tail + 1) & (elements.length - 1)) == head)
            doubleCapacity();
    }

    /**
     * 在前端插入，调用addFirst实现，返回boolean类型
     */
    public boolean offerFirst(E e) {
        addFirst(e);
        return true;
    }

    /**
     * 在末端插入，调用addLast实现，返回boolean类型
     */
    public boolean offerLast(E e) {
        addLast(e);
        return true;
    }

    /**
     * 删除前端，调用pollFirst实现
     */
    public E removeFirst() {
        E x = pollFirst();
        if (x == null)
            throw new NoSuchElementException();
        return x;
    }

    /**
     * 删除后端，调用pollLast实现
     */
    public E removeLast() {
        E x = pollLast();
        if (x == null)
            throw new NoSuchElementException();
        return x;
    }
    //前端出对（删除前端）
    public E pollFirst() {
        int h = head;
        E result = elements[h]; // Element is null if deque empty
        if (result == null)
            return null;
        elements[h] = null;     // Must null out slot
        head = (h + 1) & (elements.length - 1);
        return result;
    }
    //后端出对（删除后端）
    public E pollLast() {
        int t = (tail - 1) & (elements.length - 1);
        E result = elements[t];
        if (result == null)
            return null;
        elements[t] = null;
        tail = t;
        return result;
    }

    /**
     * 得到前端头元素
     */
    public E getFirst() {
        E x = elements[head];
        if (x == null)
            throw new NoSuchElementException();
        return x;
    }

    /**
     * 得到末端尾元素
     */
    public E getLast() {
        E x = elements[(tail - 1) & (elements.length - 1)];
        if (x == null)
            throw new NoSuchElementException();
        return x;
    }
    public E peekFirst() {
        return elements[head]; // elements[head] is null if deque empty
    }

    public E peekLast() {
        return elements[(tail - 1) & (elements.length - 1)];
    }

    /**
     * 移除此双端队列中第一次出现的指定元素（当从头部到尾部遍历双端队列时）。
     */
    public boolean removeFirstOccurrence(Object o) {
        if (o == null)
            return false;
        int mask = elements.length - 1;
        int i = head;
        E x;
        while ( (x = elements[i]) != null) {
            if (o.equals(x)) {
                delete(i);
                return true;
            }
            i = (i + 1) & mask;
        }
        return false;
    }

    /**
     * 移除此双端队列中最后一次出现的指定元素（当从头部到尾部遍历双端队列时）。
     */
    public boolean removeLastOccurrence(Object o) {
        if (o == null)
            return false;
        int mask = elements.length - 1;
        int i = (tail - 1) & mask;
        E x;
        while ( (x = elements[i]) != null) {
            if (o.equals(x)) {
                delete(i);
                return true;
            }
            i = (i - 1) & mask;
        }
        return false;
    }

    // *** 队列方法（Queue methods） ***
    /**
     * add方法，添加到队列末端
     */
    public boolean add(E e) {
        addLast(e);
        return true;
    }
    /**
     * 同上
     */
    public boolean offer(E e) {
        return offerLast(e);
    }
    /**
     * remove元素，删除队列前端
     */
    public E remove() {
        return removeFirst();
    }
    /**
     * 弹出前端（出对，删除前端）
     */
    public E poll() {
        return pollFirst();
    }
    public E element() {
        return getFirst();
    }
    public E peek() {
        return peekFirst();
    }

    // *** 栈 方法（Stack methods） ***
    public void push(E e) {
        addFirst(e);
    }
    public E pop() {
        return removeFirst();
    }
    private void checkInvariants() { ……    }
    private boolean delete(int i) {   ……   }

    // *** 集合方法（Collection Methods） ***
    ……

    // *** Object methods ***
    ……
}

整体来说:1个数组，2个index（head 索引和tail索引）。实现比较简单，容易理解。