ArrayDeque类的使用详解

迷南。 2022-06-13 13:54 195阅读 0赞

ArrayDeque不是线程安全的。   
ArrayDeque不可以存取null元素，因为系统根据某个位置是否为null来判断元素的存在。   
当作为栈使用时，性能比Stack好；当作为队列使用时，性能比LinkedList好。

一、常用方法

1.添加元素
            addFirst(E e)在数组前面添加元素
            addLast(E e)在数组后面添加元素
            offerFirst(E e) 在数组前面添加元素，并返回是否添加成功
            offerLast(E e) 在数组后天添加元素，并返回是否添加成功
    
      2.删除元素
            removeFirst()删除第一个元素，并返回删除元素的值,如果元素为null，将抛出异常
            pollFirst()删除第一个元素，并返回删除元素的值，如果元素为null，将返回null
               removeLast()删除最后一个元素，并返回删除元素的值，如果为null，将抛出异常
            pollLast()删除最后一个元素，并返回删除元素的值，如果为null，将返回null
               removeFirstOccurrence(Object o) 删除第一次出现的指定元素
            removeLastOccurrence(Object o) 删除最后一次出现的指定元素
       
    
       3.获取元素
            getFirst() 获取第一个元素,如果没有将抛出异常
            getLast() 获取最后一个元素，如果没有将抛出异常
       
    
        4.队列操作
            add(E e) 在队列尾部添加一个元素
            offer(E e) 在队列尾部添加一个元素，并返回是否成功
            remove() 删除队列中第一个元素，并返回该元素的值，如果元素为null，将抛出异常(其实底层调用的是removeFirst())
               poll()  删除队列中第一个元素，并返回该元素的值,如果元素为null，将返回null(其实调用的是pollFirst())
               element() 获取第一个元素，如果没有将抛出异常
            peek() 获取第一个元素，如果返回null
          
    
        5.栈操作
            push(E e) 栈顶添加一个元素
            pop(E e) 移除栈顶元素,如果栈顶没有元素将抛出异常
            
    
        6.其他
            size() 获取队列中元素个数
            isEmpty() 判断队列是否为空
            iterator() 迭代器，从前向后迭代
            descendingIterator() 迭代器，从后向前迭代
            contain(Object o) 判断队列中是否存在该元素
            toArray() 转成数组
            clear() 清空队列
            clone() 克隆(复制)一个新的队列

二、源码分析

1. 两个重要的索引：head和tail

Java代码   ![收藏代码][icon_star.png]

1.  // 第一个元素的索引  
2.  **private** **transient** **int** head;  
3.  // 下个要添加元素的位置，为末尾元素的索引 + 1  
4.  **private** **transient** **int** tail;

2. 构造方法

Java代码   ![收藏代码][icon_star.png]

1.  **public** ArrayDeque() \{  
2.      elements = (E\[\]) **new** Object\[16\]; // 默认的数组长度大小  
3.  \}  
4.    
5.  **public** ArrayDeque(**int** numElements) \{  
6.      allocateElements(numElements); // 需要的数组长度大小  
7.  \}  
8.    
9.  **public** ArrayDeque(Collection<? **extends** E> c) \{  
10.     allocateElements(c.size()); // 根据集合来分配数组大小  
11.     addAll(c); // 把集合中元素放到数组中  
12. \}

3. 分配合适大小的数组

Java代码   ![收藏代码][icon_star.png]

1.  **private** **void** allocateElements(**int** numElements) \{  
2.      **int** initialCapacity = MIN\_INITIAL\_CAPACITY;  
3.      // 找到大于需要长度的最小的2的幂整数。  
4.      // Tests "<=" because arrays aren't kept full.  
5.      **if** (numElements >= initialCapacity) \{  
6.          initialCapacity = numElements;  
7.          initialCapacity |= (initialCapacity >>>  1);  
8.          initialCapacity |= (initialCapacity >>>  2);  
9.          initialCapacity |= (initialCapacity >>>  4);  
10.         initialCapacity |= (initialCapacity >>>  8);  
11.         initialCapacity |= (initialCapacity >>> 16);  
12.         initialCapacity++;  
13.   
14.         **if** (initialCapacity < 0)   // Too many elements, must back off  
15.             initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements  
16.     \}  
17.     elements = (E\[\]) **new** Object\[initialCapacity\];  
18. \}

4. 扩容

Java代码   ![收藏代码][icon_star.png]

1.  // 扩容为原来的2倍。  
2.  **private** **void** doubleCapacity() \{  
3.      **assert** head == tail;  
4.      **int** p = head;  
5.      **int** n = elements.length;  
6.      **int** r = n - p; // number of elements to the right of p  
7.      **int** newCapacity = n << 1;  
8.      **if** (newCapacity < 0)  
9.          **throw** **new** IllegalStateException("Sorry, deque too big");  
10.     Object\[\] a = **new** Object\[newCapacity\];  
11.     // 既然是head和tail已经重合了，说明tail是在head的左边。  
12.     System.arraycopy(elements, p, a, 0, r); // 拷贝原数组从head位置到结束的数据  
13.     System.arraycopy(elements, 0, a, r, p); // 拷贝原数组从开始到head的数据  
14.     elements = (E\[\])a;  
15.     head = 0; // 重置head和tail为数据的开始和结束索引  
16.     tail = n;  
17. \}  
18.   
19. // 拷贝该数组的所有元素到目标数组  
20. **private** <T> T\[\] copyElements(T\[\] a) \{  
21.     **if** (head < tail) \{ // 开始索引大于结束索引，一次拷贝  
22.         System.arraycopy(elements, head, a, 0, size());  
23.     \} **else** **if** (head > tail) \{ // 开始索引在结束索引的右边，分两段拷贝  
24.         **int** headPortionLen = elements.length - head;  
25.         System.arraycopy(elements, head, a, 0, headPortionLen);  
26.         System.arraycopy(elements, 0, a, headPortionLen, tail);  
27.     \}  
28.     **return** a;  
29. \}

5. 添加元素

Java代码   ![收藏代码][icon_star.png]

1.  **public** **void** addFirst(E e) \{  
2.      **if** (e == **null**)  
3.          **throw** **new** NullPointerException();  
4.      // 本来可以简单地写成head-1，但如果head为0，减1就变为-1了，和elements.length - 1进行与操作就是为了处理这种情况，这时结果为elements.length - 1。  
5.      elements\[head = (head - 1) & (elements.length - 1)\] = e;  
6.      **if** (head == tail) // head和tail不可以重叠  
7.          doubleCapacity();  
8.  \}  
9.    
10. **public** **void** addLast(E e) \{  
11.     **if** (e == **null**)  
12.         **throw** **new** NullPointerException();  
13.     // tail位置是空的，把元素放到这。  
14.     elements\[tail\] = e;  
15.     // 和head的操作类似，为了处理临界情况 (tail为length - 1时)，和length - 1进行与操作，结果为0。  
16.     **if** ( (tail = (tail + 1) & (elements.length - 1)) == head)  
17.         doubleCapacity();  
18. \}  
19.   
20. **public** **boolean** offerFirst(E e) \{  
21.     addFirst(e);  
22.     **return** **true**;  
23. \}  
24.   
25. **public** **boolean** offerLast(E e) \{  
26.     addLast(e);  
27.     **return** **true**;  
28. \}

6. 删除元素 删除首尾元素：

Java代码   ![收藏代码][icon_star.png]

1.  **public** E removeFirst() \{  
2.      E x = pollFirst();  
3.      **if** (x == **null**)  
4.          **throw** **new** NoSuchElementException();  
5.      **return** x;  
6.  \}  
7.    
8.  **public** E removeLast() \{  
9.      E x = pollLast();  
10.     **if** (x == **null**)  
11.         **throw** **new** NoSuchElementException();  
12.     **return** x;  
13. \}  
14.   
15. **public** E pollFirst() \{  
16.     **int** h = head;  
17.     E result = elements\[h\]; // Element is null if deque empty  
18.     **if** (result == **null**)  
19.         **return** **null**;  
20.     // 表明head位置已为空  
21.     elements\[h\] = **null**;     // Must null out slot  
22.     head = (h + 1) & (elements.length - 1); // 处理临界情况（当h为elements.length - 1时），与后的结果为0。  
23.     **return** result;  
24. \}  
25.   
26. **public** E pollLast() \{  
27.     **int** t = (tail - 1) & (elements.length - 1); // 处理临界情况（当tail为0时），与后的结果为elements.length - 1。  
28.     E result = elements\[t\];  
29.     **if** (result == **null**)  
30.         **return** **null**;  
31.     elements\[t\] = **null**;  
32.     tail = t; // tail指向的是下个要添加元素的索引。  
33.     **return** result;  
34. \}

删除指定元素：

Java代码   ![收藏代码][icon_star.png]

1.  **public** **boolean** removeFirstOccurrence(Object o) \{  
2.      **if** (o == **null**)  
3.          **return** **false**;  
4.      **int** mask = elements.length - 1;  
5.      **int** i = head;  
6.      E x;  
7.      **while** ( (x = elements\[i\]) != **null**) \{  
8.          **if** (o.equals(x)) \{  
9.              delete(i);  
10.             **return** **true**;  
11.         \}  
12.         i = (i + 1) & mask; // 从头到尾遍历  
13.     \}  
14.     **return** **false**;  
15. \}  
16.   
17. **public** **boolean** removeLastOccurrence(Object o) \{  
18.     **if** (o == **null**)  
19.         **return** **false**;  
20.     **int** mask = elements.length - 1;  
21.     **int** i = (tail - 1) & mask; // 末尾元素的索引  
22.     E x;  
23.     **while** ( (x = elements\[i\]) != **null**) \{  
24.         **if** (o.equals(x)) \{  
25.             delete(i);  
26.             **return** **true**;  
27.         \}  
28.         i = (i - 1) & mask; // 从尾到头遍历  
29.     \}  
30.     **return** **false**;  
31. \}

Java代码   ![收藏代码][icon_star.png]

1.  **private** **void** checkInvariants() \{ // 有效性检查  
2.      **assert** elements\[tail\] == **null**; // tail位置没有元素  
3.      **assert** head == tail ? elements\[head\] == **null** :  
4.          (elements\[head\] != **null** &&  
5.              elements\[(tail - 1) & (elements.length - 1)\] != **null**); // 如果head和tail重叠，队列为空；否则head位置有元素，tail-1位置有元素。  
6.      **assert** elements\[(head - 1) & (elements.length - 1)\] == **null**; // head-1的位置没有元素。  
7.  \}  
8.    
9.  **private** **boolean** delete(**int** i) \{  
10.     checkInvariants();  
11.     **final** E\[\] elements = **this**.elements;  
12.     **final** **int** mask = elements.length - 1;  
13.     **final** **int** h = head;  
14.     **final** **int** t = tail;  
15.     **final** **int** front = (i - h) & mask; // i前面的元素个数  
16.     **final** **int** back  = (t - i) & mask; // i后面的元素个数  
17.   
18.     // Invariant: head <= i < tail mod circularity  
19.     **if** (front >= ((t - h) & mask)) // i不在head和tail之间  
20.         **throw** **new** ConcurrentModificationException();  
21.   
22.     // Optimize for least element motion  
23.     **if** (front < back) \{ // i的位置靠近head，移动开始的元素，返回false。  
24.         **if** (h <= i) \{  
25.             System.arraycopy(elements, h, elements, h + 1, front);  
26.         \} **else** \{ // Wrap around  
27.             System.arraycopy(elements, 0, elements, 1, i);  
28.             elements\[0\] = elements\[mask\]; // 处理边缘元素  
29.             System.arraycopy(elements, h, elements, h + 1, mask - h);  
30.         \}  
31.         elements\[h\] = **null**;  
32.         head = (h + 1) & mask; // head位置后移  
33.         **return** **false**;  
34.     \} **else** \{ // i的位置靠近tail，移动末尾的元素，返回true。  
35.         **if** (i < t) \{ // Copy the null tail as well  
36.             System.arraycopy(elements, i + 1, elements, i, back);  
37.             tail = t - 1;  
38.         \} **else** \{ // Wrap around  
39.             System.arraycopy(elements, i + 1, elements, i, mask - i);  
40.             elements\[mask\] = elements\[0\];  
41.             System.arraycopy(elements, 1, elements, 0, t);  
42.             tail = (t - 1) & mask;  
43.         \}  
44.         **return** **true**;  
45.     \}  
46. \}

示意图：  ![d51b8c33-8e97-3896-8b2b-0ce7c4e4b326.png][]  7. 获取元素

Java代码   ![收藏代码][icon_star.png]

1.  **public** E getFirst() \{  
2.      E x = elements\[head\];  
3.      **if** (x == **null**)  
4.          **throw** **new** NoSuchElementException();  
5.      **return** x;  
6.  \}  
7.    
8.  **public** E getLast() \{  
9.      E x = elements\[(tail - 1) & (elements.length - 1)\]; // 处理临界情况（当tail为0时），与后的结果为elements.length - 1。  
10.     **if** (x == **null**)  
11.         **throw** **new** NoSuchElementException();  
12.     **return** x;  
13. \}  
14.   
15. **public** E peekFirst() \{  
16.     **return** elements\[head\]; // elements\[head\] is null if deque empty  
17. \}  
18.   
19. **public** E peekLast() \{  
20.     **return** elements\[(tail - 1) & (elements.length - 1)\];  
21. \}

8. 队列操作

Java代码   ![收藏代码][icon_star.png]

1.  **public** **boolean** add(E e) \{  
2.      addLast(e);  
3.      **return** **true**;  
4.  \}  
5.    
6.  **public** **boolean** offer(E e) \{  
7.      **return** offerLast(e);  
8.  \}  
9.    
10. **public** E remove() \{  
11.     **return** removeFirst();  
12. \}  
13.   
14. **public** E poll() \{  
15.     **return** pollFirst();  
16. \}  
17.   
18. **public** E element() \{  
19.     **return** getFirst();  
20. \}  
21.   
22. **public** E peek() \{  
23.     **return** peekFirst();  
24. \}

9. 栈操作

Java代码   ![收藏代码][icon_star.png]

1.  **public** **void** push(E e) \{  
2.      addFirst(e);  
3.  \}  
4.    
5.  **public** E pop() \{  
6.      **return** removeFirst();  
7.  \}

10. 集合方法

Java代码   ![收藏代码][icon_star.png]

1.  **public** **int** size() \{  
2.      **return** (tail - head) & (elements.length - 1); // 和elements.length - 1进行与操作是为了处理当tail < head时的情况。  
3.  \}  
4.    
5.  **public** **boolean** isEmpty() \{  
6.      **return** head == tail; // tail位置的元素一定为空，head和tail相等，也为空。  
7.  \}  
8.    
9.  // 向前迭代器  
10. **public** Iterator<E> iterator() \{  
11.     **return** **new** DeqIterator();  
12. \}  
13.   
14. // 向后迭代器  
15. **public** Iterator<E> descendingIterator() \{  
16.     **return** **new** DescendingIterator();  
17. \}

Java代码   ![收藏代码][icon_star.png]

1.    **private** **class** DeqIterator **implements** Iterator<E> \{  
2.    
3.        **private** **int** cursor = head;  
4.    
5.        **private** **int** fence = tail; // 迭代终止索引，同时也为了检测并发修改。  
6.    
7.        **private** **int** lastRet = -1; // 最近的next()调用返回的索引。据此可以定位到需要删除元素的位置。  
8.    
9.        **public** **boolean** hasNext() \{  
10.           **return** cursor != fence;  
11.       \}  
12.   
13.       **public** E next() \{  
14.           **if** (cursor == fence)  
15.               **throw** **new** NoSuchElementException();  
16.           E result = elements\[cursor\];  
17.           // This check doesn't catch all possible comodifications,  
18.           // but does catch the ones that corrupt traversal  
19.           **if** (tail != fence || result == **null**)  
20.               **throw** **new** ConcurrentModificationException();  
21.           lastRet = cursor;  
22.           cursor = (cursor + 1) & (elements.length - 1); // 游标位置加1  
23.           **return** result;  
24.       \}  
25.   
26.       **public** **void** remove() \{  
27.           **if** (lastRet < 0)  
28.               **throw** **new** IllegalStateException();  
29.           **if** (delete(lastRet)) \{ // 如果将元素从右往左移，需要将游标减1。  
30.               cursor = (cursor - 1) & (elements.length - 1); // 游标位置回退1。  
31. fence = tail; // 重置阀值。  
32.    \}  
33.           lastRet = -1;  
34.       \}  
35.   \}

Java代码   ![收藏代码][icon_star.png]

1.  **private** **class** DescendingIterator **implements** Iterator<E> \{  
2.    
3.      **private** **int** cursor = tail; // 游标开始索引为tail  
4.      **private** **int** fence = head; // 游标的阀值为head  
5.      **private** **int** lastRet = -1;  
6.    
7.      **public** **boolean** hasNext() \{  
8.          **return** cursor != fence;  
9.      \}  
10.   
11.     **public** E next() \{  
12.         **if** (cursor == fence)  
13.             **throw** **new** NoSuchElementException();  
14.         cursor = (cursor - 1) & (elements.length - 1); // tail是下个添加元素的位置，所以要减1才是尾节点的索引。  
15.         E result = elements\[cursor\];  
16.         **if** (head != fence || result == **null**)  
17.             **throw** **new** ConcurrentModificationException();  
18.         lastRet = cursor;  
19.         **return** result;  
20.     \}  
21.   
22.     **public** **void** remove() \{  
23.         **if** (lastRet < 0)  
24.             **throw** **new** IllegalStateException();  
25.         **if** (!delete(lastRet)) \{ // 如果从左往右移，需要将游标加1。  
26.             cursor = (cursor + 1) & (elements.length - 1);  
27.             fence = head;  
28.         \}  
29.         lastRet = -1;  
30.     \}  
31. \}

Java代码   ![收藏代码][icon_star.png]

1.  **public** **boolean** contains(Object o) \{  
2.      **if** (o == **null**)  
3.          **return** **false**; // ArrayDeque不可以存储null元素  
4.      **int** mask = elements.length - 1;  
5.      **int** i = head;  
6.      E x;  
7.      **while** ( (x = elements\[i\]) != **null**) \{  
8.          **if** (o.equals(x))  
9.              **return** **true**;  
10.         i = (i + 1) & mask; // 处理临界情况  
11.     \}  
12.     **return** **false**;  
13. \}  
14.   
15. **public** **boolean** remove(Object o) \{  
16.     **return** removeFirstOccurrence(o);  
17. \}  
18.   
19. **public** **void** clear() \{  
20.     **int** h = head;  
21.     **int** t = tail;  
22.     **if** (h != t) \{ // clear all cells  
23.         head = tail = 0; // 重置首尾索引  
24.         **int** i = h;  
25.         **int** mask = elements.length - 1;  
26.         **do** \{  
27.             elements\[i\] = **null**; // 清除元素  
28.             i = (i + 1) & mask;  
29.         \} **while** (i != t);  
30.     \}  
31. \}  
32.   
33. **public** Object\[\] toArray() \{  
34.     **return** copyElements(**new** Object\[size()\]); // 把所有元素拷贝到新创建的Object数组上，所以对返回数组的修改不会影响该双端队列。  
35. \}  
36.   
37. **public** <T> T\[\] toArray(T\[\] a) \{  
38.     **int** size = size();  
39.     **if** (a.length < size) // 目标数组大小不够  
40.         a = (T\[\])java.lang.reflect.Array.newInstance(  
41.                 a.getClass().getComponentType(), size); // 利用反射创建类型为T，大小为size的数组。  
42. yElements(a); // 拷贝所有元素到目标数组。  
43.     **if** (a.length > size)  
44.         a\[size\] = **null**; // 结束标识  
45.     **return** a;  
46. \}

11. Object方法

Java代码   ![收藏代码][icon_star.png]

1.  **public** ArrayDeque<E> clone() \{  
2.      **try** \{  
3.          ArrayDeque<E> result = (ArrayDeque<E>) **super**.clone();  
4.          result.elements = Arrays.copyOf(elements, elements.length); // 深度复制。  
5.          **return** result;  
6.    
7.      \} **catch** (CloneNotSupportedException e) \{  
8.          **throw** **new** AssertionError();  
9.      \}  
10. \}  
11.

源码分析来自网址：http://czj4451.iteye.com/blog/1688693

[icon_star.png]: /images/20220613/dc19e9ee70b843a88877c0a12f34caa8.png
[d51b8c33-8e97-3896-8b2b-0ce7c4e4b326.png]: /images/20220613/9818874153194f04baa69f215a8e6895.png