當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

ArrayDeque(双端队列的线性实现)详解

發布時間：2023/12/14 编程问答 37 豆豆

生活随笔收集整理的這篇文章主要介紹了 ArrayDeque(双端队列的线性实现)详解小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

ArrayDeque 是 java 中對雙端隊列的線性實現

一. 特性

無容量大小限制，容量按需增長；

非線程安全隊列，無同步策略，不支持多線程安全訪問；

當用作棧時，性能優于Stack，當用于隊列時，性能優于LinkedList

兩端都可以操作

具有 fail-fast 特征

不能存儲null

支持雙向迭代器遍歷

注意: ArrayDeque 的迭代器和大多數容器迭代器一樣，都是快速失敗 (fail-fast），但是程序不能利用這個特性決定是或否進行了并發操作。

二. 數據結構

為了更好的理解使用線性數組實現的雙端隊列，這里我們先來圖解線性數組實現基本數據結構 - 隊列：

如上圖所示，head 指向隊頭，入隊加元素時，tail 隊尾向后移動，出隊時從 head 出取出元素并移除，這樣就利用了線性數組實現先進先出的隊列數據結構，當 head 等于 tail 時，則表示隊列為空。但是這樣存在問題：當不斷出隊時，head 向后移動，前面空出來的空間就被浪費，導致不斷入隊時，需要數組擴容，出隊時造成大量空間無法使用，空間利用率低下！假設，如果能將前面空出來的空間也利用起來進行存儲末尾的元素，則空間使用率將提高，這里就需要有個循環的思維，把這種線性的彎曲成一個圓環，這樣就可以反復使用空出來的空間，入隊時使用出隊空余出來的空間，就解決以上的問題，圖解如下：

同樣，當 head 等于 tail 時，則表示循環隊列為空。head 和 tail 也是循環的，像鐘表中的時針，具有周期性。這里 head 和 tail 需要對長度 lenth 取模，這樣 head 和 tail 將一直在長度范圍內，可以作為數組的下標。

對于如何將數據分布到相應大小的連續空間中，常用的方式就是取模運算，即 position=index%len，利用整數倍的周期性，將剩余的部分作為空間索引。

三. 源碼分析

1. ArrayDeque 數據域

/***?The?array?in?which?the?elements?of?the?deque?are?stored.*?The?capacity?of?the?deque?is?the?length?of?this?array,?which?is*?always?a?power?of?two.?The?array?is?never?allowed?to?become*?full,?except?transiently?within?an?addX?method?where?it?is*?resized?(see?doubleCapacity)?immediately?upon?becoming?full,*?thus?avoiding?head?and?tail?wrapping?around?to?equal?each*?other.??We?also?guarantee?that?all?array?cells?not?holding*?deque?elements?are?always?null.*/ transient?Object[]?elements;?//?non-private?to?simplify?nested?class?access/***?The?index?of?the?element?at?the?head?of?the?deque?(which?is?the*?element?that?would?be?removed?by?remove()?or?pop());?or?an*?arbitrary?number?equal?to?tail?if?the?deque?is?empty.*/ transient?int?head;/***?The?index?at?which?the?next?element?would?be?added?to?the?tail*?of?the?deque?(via?addLast(E),?add(E),?or?push(E)).*/ transient?int?tail;/***?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;

首先看下 ArrayDeque 持有的成員域，其中非常核心的是 elements，head，tail 三個。下面逐一介紹：

elements: 該數組用于存儲隊列元素，且是大小總是 2 的冪次方（后面會介紹為什么？）。這個數組不會滿容量，會在add方法中擴容，使得頭 head 和 tail 不會纏繞在一起（即 head 增長或不會超過 tail，head 減小時不會溢出到 tail），這里隊列長度是 2 的冪次方的原因后續會闡明；
head: 雙端隊列的頭位置，出隊時或者彈出棧時的元素位置，加入雙端隊列頭端元素位置，表示當前頭元素位置；
tail: 雙端隊列的尾，入隊和進棧時的元素位置，加入雙端隊列尾端的下個元素的索引，tail 位總是空的；
MIN_INITIAL_CAPACITY: 最小的初始化容量

2. 構造函數

/***?Constructs?an?empty?array?deque?with?an?initial?capacity*?sufficient?to?hold?16?elements.*/ public?ArrayDeque()?{elements?=?new?Object[16]; }/***?Constructs?an?empty?array?deque?with?an?initial?capacity*?sufficient?to?hold?the?specified?number?of?elements.**?@param?numElements??lower?bound?on?initial?capacity?of?the?deque*/ public?ArrayDeque(int?numElements)?{allocateElements(numElements); }/***?Constructs?a?deque?containing?the?elements?of?the?specified*?collection,?in?the?order?they?are?returned?by?the?collection's*?iterator.??(The?first?element?returned?by?the?collection's*?iterator?becomes?the?first?element,?or?<i>front</i>?of?the*?deque.)**?@param?c?the?collection?whose?elements?are?to?be?placed?into?the?deque*?@throws?NullPointerException?if?the?specified?collection?is?null*/ public?ArrayDeque(Collection<??extends?E>?c)?{allocateElements(c.size());addAll(c); }

第一個默認的無參構造函數：創建初始化大小為 16 的隊列
第二個構造函數：根據參數numElements創建隊列，如果numElements小于 8，則隊列初始化大小為 8；如果numElements大于 8，則初始化大小為大于numElements的最小 2 的冪次方。如：numElements=17，則初始化大小為 32
第三個構造函數：根據集合元素創建隊列，初始化大小為大于集合大小的最小 2 的冪次方

這里重點看下第二個構造器的過程。其中調用allocateElements(numElements)方法，該方法用來實現容量分配，下面看下內部具體實現：

/***?Allocates?empty?array?to?hold?the?given?number?of?elements.**?@param?numElements??the?number?of?elements?to?hold*/ private?void?allocateElements(int?numElements)?{int?initialCapacity?=?MIN_INITIAL_CAPACITY;//?Find?the?best?power?of?two?to?hold?elements.//?Tests?"<="?because?arrays?aren't?kept?full.if?(numElements?>=?initialCapacity)?{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?offinitialCapacity?>>>=?1;//?Good?luck?allocating?2?^?30?elements}elements?=?new?Object[initialCapacity]; }

首先判斷指定大小 numElements 與MIN_INITIAL_CAPACITY的大小關系。如果小于MIN_INITIAL_CAPACITY，則直接分配大小為MIN_INITIAL_CAPACITY的數組；如果大于MIN_INITIAL_CAPACITY，則進行無符號右移操作，然后在加 1，這樣就可以尋找到大于 numElements 的最小 2 的冪次方。原理：無符號右移再進行按位或操作，就是將其低位全部補成 1，然后再自加加一次，就是再向前進一位。這樣就能得到其最小的 2 次冪。之所以需要最多移 16 位，是為了能夠處理大于 2^16 次方數。

最后再判斷值是否小于 0，因為如果初始值在 int 最大值 2^{31-1 和 2}30 之間，進行一系列移位操作后將得到 int 最大值，再加 1，則溢出變成負數，所以需要檢測臨界值，然后再右移 1 位！！！

接下來再來分析下 ArrayDeque 的幾個重要雙端操作。對于雙端隊列有哪些重要的雙端操作，可以移步至我的之前寫的另一篇文章 Java 中 Deque 特性及 API

在詳細介紹 ArrayDeque 的重要 API 實現之前，以圖解的方式看下 ArrayDeque 構造函數初始化出的隊列的數據結構：

![](https://images2018.cnblogs.com/blog/1286175/201805/1286175-20180524004648915-1877176182.png

" width="800" high="15">

初始化ArrayDeque后，head和tail都是0，指向數組的0下標位置。在了解初始化后的數據構成后，再首先來看下addFirst方法

<h6 id=")3\." 重要行為=""addFirst 方法/***?Inserts?the?specified?element?at?the?front?of?this?deque.**?@param?e?the?element?to?add*?@throws?NullPointerException?if?the?specified?element?is?null*/ public?void?addFirst(E?e)?{if?(e?==?null)throw?new?NullPointerException();elements[head?=?(head?-?1)?&?(elements.length?-?1)]?=?e;if?(head?==?tail)doubleCapacity(); }

先用圖解的方式分析下這個方法，在第一次調用這個方法后，數據變化如下：

根據圖的變化來分析下代碼實現。首先判斷插入元素是否為空，再計算即將插入的位置，計算出后將元素賦值給相應的槽位，最后再判斷隊列容量進行擴容。

將數組的高位端作為雙端隊列的頭部，將低位作為雙端隊列尾部。沒從頭部加入一個元素時，head 頭逆時針向 tail 尾方向移動一個位置，實現上即將 head 減 1 后對數組的最大下標按位與運算。這里就利用了 2 的冪次方的特性，隊列容量設置為 2 的冪次方后，數組的最大下標位置等于 2 的冪次方減 1，在二進制表示時，就是所有二進制位都是 1。這樣 head 位置減 1 后與其進行按位與運算就能得到頭部插入的位置。

當 head 等于 tail 時，就表示隊列已經滿了。這時需要進行擴容。

下面再來看下擴容策略：

/***?Doubles?the?capacity?of?this?deque.??Call?only?when?full,?i.e.,*?when?head?and?tail?have?wrapped?around?to?become?equal.*/ private?void?doubleCapacity()?{assert?head?==?tail;int?p?=?head;int?n?=?elements.length;int?r?=?n?-?p;?//?number?of?elements?to?the?right?of?pint?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?=?a;head?=?0;tail?=?n; }

按照 2 倍方式擴容

擴容后，將原隊列中從頭部插入的元素即 head 右邊元素從擴容后新數組的 0 位置開始排放，然后將左邊的元素緊接著排放進新數組。

將 head 置 0，tail 置成擴容前數組長度。

如果從頭端插入，則 head 繼續逆時針旋轉方式插入新元素。從以上圖中不難看出 addFirst 是操作雙端隊列頭端，且是逆時針方式旋轉插入。接下來再看看從尾端插入的過程

addLast 方法

/***?Inserts?the?specified?element?at?the?end?of?this?deque.**?<p>This?method?is?equivalent?to?{@link?#add}.**?@param?e?the?element?to?add*?@throws?NullPointerException?if?the?specified?element?is?null*/ public?void?addLast(E?e)?{if?(e?==?null)throw?new?NullPointerException();elements[tail]?=?e;if?(?(tail?=?(tail?+?1)?&?(elements.length?-?1))?==?head)doubleCapacity(); }

上述的 addFirst 是逆時針的插入方式，addLast 剛好與其相反，即順時針方向插入，且 tail 表示的是下一個插入的元素的位置。

判斷元素是否為空，然后直接將元素插入 tail 槽位

然后 tail 向后移動一位，再按位與（控制循環）作為新的 tail 槽位

判斷新的 tail 槽位是否與 head 相等，然后依此進行擴容（這里擴容與上述擴容過程一樣，不再贅述）。

pollFirst 方法

public?E?pollFirst()?{int?h?=?head;@SuppressWarnings("unchecked")E?result?=?(E)?elements[h];//?Element?is?null?if?deque?emptyif?(result?==?null)return?null;elements[h]?=?null;?????//?Must?null?out?slothead?=?(h?+?1)?&?(elements.length?-?1);return?result; }

取出頭元素，如果頭元素為空，則返回null

否則，將頭元素槽位置為空（因為 pollFirst 是移除操作）

再將 head 順時針向后移動一位，即加 1 再和數組最大下標按位與計算出新的 head

注：讀到這里，相信讀者已經已經對雙端隊列的數據結構已經非常清晰，即雙端操作的數組，tail 向前（順時針）移動即從尾端插入元素或者向后移動即從尾端移除元素，head 向后（逆時針）移動即從頭端插入元素或者向前移動即從頭端移除元素。這幾個過程正好具有 FIFO 和 LIFO 的特點，所以 ArrayDeque 既可以作為隊列 Queue 又可以作為棧 Stack。

pollLast 方法

public?E?pollLast()?{int?t?=?(tail?-?1)?&?(elements.length?-?1);@SuppressWarnings("unchecked")E?result?=?(E)?elements[t];if?(result?==?null)return?null;elements[t]?=?null;tail?=?t;return?result; }

從以上描述的 ArrayDeque 的數據結構和 tail 的含義中，可以大致思考下，從尾端移除元素的過程。

先將 tail 向后（逆時針）移動一位，然后對數組最大下標按位與計算出將要移除元素的槽位

取出計算出的槽位中元素，判斷是否為空，為空則返回null

如果不為空，則將該槽位置為空，將槽位下標作為新的 tail

以上的過程基就是 ArrayDeque 的工作原理的最基本實現，其他的行為大都是基于這些過程實現：

offer 方法：內部調用 offerLast 插入元素，返回插入結果 true/false

add 方法：內部調用 addLast 實現

poll 方法：內部調用 pollFirst 實現

remove 方法：內部調用 removeFirst 實現

peek 方法：內部調用 peekFirst 實現

element 方法：內部調用 getFirst 實現

pop 方法：內部調用 addFirst 實現

push 方法：內部調用 removeFirst 實現

這里不再詳述每個操作的具體實現，因為這些操作都是基于 addFirst、addLast、pollFirst 和 pollLast 實現。具體調用這些基礎行為實現的細節，讀者可以閱讀 ArrayDeque 源碼。

參考：

位運算總結 (按位與, 或, 異或) https://blog.csdn.net/sinat_35121480/article/details/53510793 Java 中 >> 和 >>> 的區別 https://www.cnblogs.com/leo0705/p/8473071.html java int short long float double 精度最大值整理 https://blog.csdn.net/truelove12358/article/details/48522437

作者：懷瑾握瑜

來源鏈接：

https://www.cnblogs.com/lxyit/p/9080590.html

總結

以上是生活随笔為你收集整理的ArrayDeque(双端队列的线性实现)详解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。