JDK容器学习之Queue: ArrayDeque

transient Object[] elements;

transient int head;

transient int tail;

public E poll() {
    if (size == 0) // 队列为空
        return null;
    int s = --size;
    modCount++;
    // 数组中第一个为队列头
    E result = (E) queue[0]; 
    E x = (E) queue[s];
    queue[s] = null;
    if (s != 0) 
        // 队列非空时，重排剩下的元素
        siftDown(0, x);
    return result;
}

public void addLast(E e) {
    if (e == null) // 不支持向队列中塞入null对象
        throw new NullPointerException();
    elements[tail] = e;
    if ( (tail = (tail + 1) & (elements.length - 1)) == head) {
    // tail 后移一位，若tail长度超过数组长度，则tail转到数组头
    // 上面的与操作等价于对数组长度进行求余
    // 若tail和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) // int逸出判断
        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;
}

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;
}