ArrayDeque

ArrayDeque是基于数组实现到的一个*双端队列，容量可扩展，不允许null元素，因为移除位的元素将使用null填充。队列的容量是数组的长度，并且数组长度始终是2的次幂。使用ArrayDeque实现栈或者队列比使用Stack、LinkedList效率高。

双端队列可以从头部和尾部新增或移除元素。使用head和tail两个指针标识头节点和尾节点，(tail - head ) & (elements.length - 1)计算元素个数。当head = tail ，表明存储数组已满，扩容数组大小一倍。除去扩容，其余时间整个队列中tail != head，所以找到第一个null元素，数组遍历结束。

关键属性

// 底层元素存储， 默认长度为8
transient Object[] elements;
// 队列头部元素
transient int head;
// 队列尾部元素
transient int tail;
// 默认最小容量，如果传递的容量小于8，则使用8作为传递容量，最后实际容量被修改为16
private static final int MIN_INITIAL_CAPACITY = 8;

构造函数

/**
 * 默认数组长度为16
 */
public ArrayDeque() {
    elements = new Object[16];
}

/**
 * 指定数组长度，如果小于8，则使用8作为容量计算基础；如果大于8，则使用2的次幂长度。最终初始大小最小为16
 */
public ArrayDeque(int numElements) {
    allocateElements(numElements);
}

/**
 * 填充集合元素到双端队列
 */
public ArrayDeque(Collection<? extends E> c) {
    allocateElements(c.size());
    addAll(c);
}

/**
 * 初始化存储数组大小为numElements
 */
private void allocateElements(int numElements) {
    elements = new Object[calculateSize(numElements)];
}

/**
 * 修改数组长度
 * 如果数组长度小于8，则使用8,；如果初始容量不是2的次幂，转换为2的次幂
 */
private static int calculateSize(int numElements) {
    int initialCapacity = MIN_INITIAL_CAPACITY;
    // Find the best power of two to hold elements.
    // Tests "<=" because arrays aren't kept full.
    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
    }
    return initialCapacity;
}

新增元素

/**
 * 尾部添加
 */
public boolean add(E e) {
    addLast(e);
    return true;
}

public void addLast(E e) {
    if (e == null)
        throw new NullPointerException();
    // 将新增元素添加到tail索引
    elements[tail] = e;
    // 触发扩容   
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)
        // 扩容
        doubleCapacity();
}

/**
 * 扩容
 * 数组大小扩容为两倍，先复制头节点到数组末尾的元素到新数组，再复制数组头部到尾节点的元素
 */
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];
    // 从旧数组(elements)头节点位置(p)复制到新数组(a)，复制到0位置，复制头节点到数组末尾元素
    System.arraycopy(elements, p, a, 0, r);
    // 从旧数组(elements)
    System.arraycopy(elements, 0, a, r, p);
    elements = a;
    head = 0;
    tail = n;
}

/**
 * 头部添加
 */
public void addFirst(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[head = (head - 1) & (elements.length - 1)] = e;
    if (head == tail)
        doubleCapacity();
}

移除元素

/**
 * 移除元素。从头部移除
 * 移除并返回头部元素(index = head)，如果头部元素为null，则返回null
 */
public E poll() {
    return pollFirst();
}

public E pollFirst() {
    int h = head;
    @SuppressWarnings("unchecked")
    // 获取到头元素
    E result = (E) 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;
}

/**
 * 移除元素。从头部移除
 * 移除元素并返回头部元素(index = head)，如果头部元素为null，抛出异常
 */
public E remove() {
    return removeFirst();
}

public E removeFirst() {
    E x = pollFirst();
    if (x == null)
        throw new NoSuchElementException();
    return x;
}

/**
 * 头部移除元素
 */
public E pollFirst() {
    int h = head;
    @SuppressWarnings("unchecked")
    E result = (E) 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);
    @SuppressWarnings("unchecked")
    E result = (E) elements[t];
    if (result == null)
        return null;
    elements[t] = null;
    tail = t;
    return result;
}

public E removeFirst() {
    E x = pollFirst();
    if (x == null)
        throw new NoSuchElementException();
    return x;
}

public E removeLast() {
    E x = pollLast();
    if (x == null)
        throw new NoSuchElementException();
    return x;
}

contains

/**
 * 是否包含指定元素
 * 从头部元素开始遍历，寻找与指定元素相等的元素，如果寻找过程中发现null元素，表明查找结束（只有扩容期间
 * 才可能出现没有null元素的情况，所以一旦搜索中发现null元素，即查找结束），不包含指定元素，返回false
 */
public boolean contains(Object o) {
    if (o == null)
        return false;
    int mask = elements.length - 1;
    int i = head;
    Object x;
    while ( (x = elements[i]) != null) {
        if (o.equals(x))
            return true;
        i = (i + 1) & mask;
    }
    return false;
}

元素个数

public int size() {
    return (tail - head) & (elements.length - 1);
}