Queue之ArrayDeque源码

 1 public interface Queue<E> extends Collection<E> {
 2     // 增加一个元素到队尾，如果队列已满，则抛出一个IIIegaISlabEepeplian异常
 3     boolean add(E e);
 4     // 添加一个元素到队尾并返回true，如果队列已满，则返回false
 5     boolean offer(E e);
 6     // 移除并返回队列头部的元素，如果队列为空，则抛出一个NoSuchElementException异常
 7     E remove();
 8     // 移除并返问队列头部的元素，如果队列为空，则返回null
 9     E poll();
10     // 返回队列头部的元素，如果队列为空，则抛出一个NoSuchElementException异常
11     E element();
12     // 返问队列头部的元素，如果队列为空，则返回null
13     E peek();
14 }

 1     /**
 2      * 默认构造方法，数组的初始容量为16
 3      */
 4     public ArrayDeque() {
 5         elements = (E[]) new Object[16];
 6     }
 7  
 8     /**
 9      * 使用一个指定的初始容量构造一个ArrayDeque
10      */
11     public ArrayDeque( int numElements) {
12         allocateElements(numElements);
13     }
14 
15     /**
16      * 构造一个指定Collection集合参数的ArrayDeque
17      */
18     public ArrayDeque(Collection<? extends E> c) {
19         allocateElements(c.size());
20         addAll(c);
21     }
22 
23     /**
24      * 分配合适容量大小的数组，确保初始容量是大于指定numElements的最小的2的n次幂
25      */
26     private void allocateElements(int numElements) {
27         int initialCapacity = MIN_INITIAL_CAPACITY;
28         // 找到大于指定容量的最小的2的n次幂
29         // Find the best power of two to hold elements.
30         // Tests "<=" because arrays aren‘t kept full.
31         // 如果指定的容量小于初始容量8，则执行一下if中的逻辑操作
32         if (numElements >= initialCapacity) {
33             initialCapacity = numElements;
34             initialCapacity |= (initialCapacity >>>  1);
35             initialCapacity |= (initialCapacity >>>  2);
36             initialCapacity |= (initialCapacity >>>  4);
37             initialCapacity |= (initialCapacity >>>  8);
38             initialCapacity |= (initialCapacity >>> 16);
39             initialCapacity++;
40 
41             if (initialCapacity < 0)   // Too many elements, must back off
42                 initialCapacity >>>= 1; // Good luck allocating 2 ^ 30 elements
43         }
44         elements = (E[]) new Object[initialCapacity];
45     }

2^1 = 10
2^2 = 100
2^3 = 1000
2^n = 1(n个0)

2^1 - 1 = 01
2^2 - 1 = 011
2^3 - 1 = 0111
2^n - 1 = 0(n个1)

 1     /**
 2      * 数组将要满了的时候(tail==head)将，数组进行2倍扩容
 3      */
 4     private void doubleCapacity() {
 5         // 验证head和tail是否相等
 6         assert head == tail;
 7         int p = head ;
 8         // 记录数组的长度
 9         int n = elements .length;
10         // 计算head后面的元素个数，这里没有采用jdk中自带的英文注释right，是因为所谓队列的上下左右，只是我们看的方位不同而已，如果上面画的图，这里就应该是left而非right
11         int r = n - p; // number of elements to the right of p
12         // 将数组长度扩大2倍
13         int newCapacity = n << 1;
14         // 如果此时长度小于0，则抛出IllegalStateException异常，什么时候newCapacity会小于0呢，前面我们说过了int值<<1越界
15         if (newCapacity < 0)
16             throw new IllegalStateException( "Sorry, deque too big" );
17         // 创建一个长度是原数组大小2倍的新数组
18         Object[] a = new Object[newCapacity];
19         // 将原数组head后的元素都拷贝值新数组
20         System. arraycopy(elements, p, a, 0, r);
21         // 将原数组head前的元素都拷贝到新数组
22         System. arraycopy(elements, 0, a, r, p);
23         // 将新数组赋值给elements
24         elements = (E[])a;
25         // 重置head为数组的第一个位置索引0
26         head = 0;
27         // 重置tail为数组的最后一个位置索引+1（(length - 1) + 1）
28         tail = n;
29     }