Java集合ArrayDeque類實例分析

Java集合ArrayDeque類實例分析

公司主營業(yè)務：網站制作、成都網站設計、移動網站開發(fā)等業(yè)務。幫助企業(yè)客戶真正實現互聯(lián)網宣傳，提高企業(yè)的競爭能力。成都創(chuàng)新互聯(lián)是一支青春激揚、勤奮敬業(yè)、活力青春激揚、勤奮敬業(yè)、活力澎湃、和諧高效的團隊。公司秉承以“開放、自由、嚴謹、自律”為核心的企業(yè)文化，感謝他們對我們的高要求，感謝他們從不同領域給我們帶來的挑戰(zhàn)，讓我們激情的團隊有機會用頭腦與智慧不斷的給客戶帶來驚喜。成都創(chuàng)新互聯(lián)推出萊山免費做網站回饋大家。

前言

ArrayDeque類是雙端隊列的實現類，類的繼承結構如下面，繼承自AbastractCollection（該類實習了部分集合通用的方法，其實現了Collection接口），其實現的接口Deque接口中定義了雙端隊列的主要的方法，比如從頭刪除，從尾部刪除，獲取頭數據，獲取尾部數據等等。

public class ArrayDeque<E> extends AbstractCollection<E>
   implements Deque<E>, Cloneable, Serializable

ArrayDeque基本特征

就其實現而言，ArrayDeque采用了循環(huán)數組的方式來完成雙端隊列的功能。

1. 無限的擴展，自動擴展隊列大小的。（當然在不會內存溢出的情況下。）
2. 非線程安全的，不支持并發(fā)訪問和修改。
3. 支持fast-fail.
4. 作為棧使用的話比比棧要快.
5. 當隊列使用比linklist要快。
6. null元素被禁止使用。

ArrayDeque實現方法解讀

最小初始化容量限制

 /**
  * The minimum capacity that we'll use for a newly created deque.
  * Must be a power of 2.
  */
 private static final int MIN_INITIAL_CAPACITY = 8;

這里根據注釋中提及，必須是2的冪次。僅僅通過這里是不會知道為何要這樣設定的。

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

addFirst方法中使用了head-1和length-1相與的形式來計算，那么，length-1這里是多少，因為規(guī)定了length必須是2的冪次，所以length-1后二進制低位將全部為1，然后與head-1相與相當于對其進行取模。

擴容

之所以說該ArrayDeque容量無限制，是因為只要檢測到head==tail的時候，就直接調用doubleCapacity方法進行擴容。
這個時候將數組展開，head和tail指向的是同一個位置，那么，因為是循環(huán)數組，所以head左邊可能存在一部分元素為p個，右邊也可能存在一部分數據r=n-p個，右邊的部分復制到從0到r,左邊的部分復制到從r到結束。這樣原來的數據從0開始往下排列。

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

刪除元素

刪除元素的基本思路為確定那一側的數據少，少的一側移動元素位置，這樣效率相對于不比較更高些，然后，判斷head是跨越最大值還是為跨越最大值，繼而可以分兩種不同的情況進行拷貝。但是該方法比較慢，因為存在數組的拷貝。

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
    // 拷貝i后面的部分數據前置
    System.arraycopy(elements, i + 1, elements, i, back);
    tail = t - 1;
   } else { // Wrap around
    // 跨越中間最大值的時候
    // 后面向前拷貝
    // 0處的值單獨處置放在最大的下標處
    // 后面的部分從1開始向前移動一個，原來的1在0處
    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;
  }
 }

獲取并刪除元素

這里在舉個簡單點的例子，中間判斷是不是null，可以看出該隊列不支持null,通過把其值設為null就算是將其刪除了。然后head向遞增的方向退一位即可。

 public E pollFirst() {
  int h = head;
  E result = 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;
 }

感謝閱讀，希望能幫助大家，謝謝大家對本站的支持！

文章標題：Java集合ArrayDeque類實例分析
網址分享：http://www.rwnh.cn/article6/igpoog.html

成都網站建設公司_創(chuàng)新互聯(lián)，為您提供Google、虛擬主機、企業(yè)網站制作、電子商務、商城網站、品牌網站制作

聲明：本網站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內容

中文字幕日韩精品一区二区免费_精品一区二区三区国产精品无卡在_国精品无码专区一区二区三区_国产αv三级中文在线

Java集合ArrayDeque類實例分析