JDK 6 更新内容

// 也是基于数组结构存储元素
private transient E[] elements;

// 队头队尾下标
private transient int head;

private transient int tail;

public ArrayDeque() {
	elements = (E[]) new Object[16];	// 默认创建容量为16的数组
}

public ArrayDeque(int numElements) {
	allocateElements(numElements);	// 也可以指定数组容量
}

private void allocateElements(int numElements) {
	int initialCapacity = MIN_INITIAL_CAPACITY;	// 默认大小8
	// Find the best power of two to hold elements.
	// Tests "<=" because arrays aren't kept full.
	if (numElements >= initialCapacity) {	// 容量大小必须是2的整数倍
		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];
}

// 添加到队列头
public void addFirst(E e) {
	if (e == null)	// 元素不允许为null，因为ArrayDeque是根据null来判断// 对应下标位置是否被有元素存在
		throw new NullPointerException();
	elements[head = (head - 1) & (elements.length - 1)] = e;
	if (head == tail)
		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];
	System.arraycopy(elements, p, a, 0, r);	// 复制到新数组
	System.arraycopy(elements, 0, a, r, p);
	elements = (E[])a;
	head = 0;
	tail = n;
}

// 删除指定位置的元素
private boolean delete(int i) {
	checkInvariants();
	final E[] elements = this.elements;
	final int mask = elements.length - 1;
	final int h = head;
	final int t = tail;
	final int front = (i - h) & mask;
	final int back  = (t - i) & mask;

	// Invariant: head <= i < tail mod circularity
	if (front >= ((t - h) & mask))
		throw new ConcurrentModificationException();

	// Optimize for least element motion
	if (front < back) {
		if (h <= i) {
		System.arraycopy(elements, h, elements, h + 1, front);
		} else { // Wrap around
		System.arraycopy(elements, 0, elements, 1, i);
		elements[0] = elements[mask];
		System.arraycopy(elements, h, elements, h + 1, mask - h);
		}
		elements[h] = null;
		head = (h + 1) & mask;
		return false;
	} else {
		if (i < t) { // Copy the null tail as well
		System.arraycopy(elements, i + 1, elements, i, back);
		tail = t - 1;
		} else { // Wrap around
		System.arraycopy(elements, i + 1, elements, i, mask - i);
		elements[mask] = elements[0];
		System.arraycopy(elements, 1, elements, 0, t);
		tail = (t - 1) & mask;
		}
		return true;
	}
}