JCF中的Queue、Deque集合
Queue（隊列）、Deque（雙端隊列）集合是JCF中另一種重要的集合。隊列存儲的數(shù)據(jù)允許從結(jié)構(gòu)的一端進行添加操作（入隊操作），并且從結(jié)構(gòu)的另一端進行移除操作（出隊操作）。進行入隊操作的一端稱為隊列尾部；進行出隊操作的一端稱為隊列頭部。雙端隊列是指可以在一端既進行入隊操作，又進行出隊操作的隊列結(jié)構(gòu)。
注意：隊列和雙端隊列都不允許在除了隊列頭部或隊列尾部的其他索引位上進行數(shù)據(jù)的讀/寫操作。在JCF中，具有隊列操作特性的集合都實現(xiàn)或間接實現(xiàn)了java.util.Queue接口；具有雙端隊列操作特性的集合都實現(xiàn)或間接實現(xiàn)了java.util.Deque接口。
JCF中的java.util.Queue接口、java.util.Deque接口涉及的部分重要接口、抽象類及其在java.util包中的具體實現(xiàn)類如圖2-1所示。在JCF中，還有大量關(guān)于Queue（隊列）接口和Deque（雙端隊列）接口的實現(xiàn)集合位于java.util.concurrent包中，這些集合都是可以工作在高并發(fā)場景中的隊列或 雙 端 隊 列 ， 如 LinkedBlockingDeque 隊 列 、 ArrayBlockingQueue 隊 列 、PriorityBlockingQueue隊列等。本書會在后續(xù)章節(jié)中介紹JUC的必要知識后，再對這些隊列進行詳細介紹
java.util.ArrayDeque 集 合 和 java.util.PriorityQueue 隊 列 分 別 是Queue （ 隊 列 ） 接 口 和 Deque （ 雙 端 隊 列 ） 接 口 在 JCF 中 的 基 礎 集 合 。
ArrayDeque集合為了保證對已有數(shù)組控件的充分利用，使用的是可循環(huán)的雙指針數(shù)組（但不代表不進行擴容操作）；PriorityQueue隊列使用的是小頂堆結(jié)構(gòu)，對基于權(quán)值的排序性能進行了優(yōu)化。
Queue集合實現(xiàn)——ArrayDeque
ArrayDeque集合是從JDK 1.6開始推出的，它是一個基于數(shù)組（可擴容的數(shù)組）結(jié)構(gòu)實現(xiàn)的雙端隊列。與普通的數(shù)組結(jié)構(gòu)相比，這種數(shù)組結(jié)構(gòu)是一種可循環(huán)使用的數(shù)組結(jié)構(gòu)，可以有效減少數(shù)組擴容的次數(shù)。ArrayDeque集合是線程不安全的，不能在多線程場景中使用。
ArrayDeque集合既有隊列、雙端隊列的操作特點，又有棧結(jié)構(gòu)的操作特點。因此在JDK 1.6發(fā)布后，ArrayDeque集合是官方推薦的繼Stack集合和LinkedList集合后，用于進行棧結(jié)構(gòu)操作的新集合。官方文檔中的推薦原因如下。
在本書中，實現(xiàn)了Queue接口的集合都可以稱為隊列，這里之所以沒有將ArrayDeque集合稱為隊列，主要是因為ArrayDeque集合實現(xiàn)了Deque接口（間接實現(xiàn)了Queue接口），因此同時具有隊列和雙端隊列的工作特點，如果將ArrayDeque集合統(tǒng)稱為ArrayDeque隊列，則會使讀者忽略其雙端隊列的工作特點。
ArrayDeque集合的主要結(jié)構(gòu)及相關(guān)方法
ArrayDeque集合內(nèi)部的主要結(jié)構(gòu)是一個數(shù)組，ArrayDeque集合的設計者將這個數(shù)組設計成了可循環(huán)利用的形式，稱為循環(huán)數(shù)組。循環(huán)數(shù)組是一個固定大小的數(shù)組，并且定義了一個動態(tài)的有效數(shù)據(jù)范圍（這個有效數(shù)據(jù)范圍的長度不會大于數(shù)組的固定長度），只有在這個有效數(shù)據(jù)范圍內(nèi)的數(shù)據(jù)對象才能被讀/寫，并且這個有效數(shù)據(jù)范圍不受數(shù)組的頭部和尾部限制，如圖2-2所示。
根據(jù)圖2-2可知，ArrayDeque集合的內(nèi)部結(jié)構(gòu)是一個循環(huán)數(shù)組，該循環(huán)數(shù)組在ArrayDeque集合中的變量名為elements；ArrayDeque集合中有一個名為head的屬性，主要用于標識下一次進行移除操作的數(shù)據(jù)對象索引位（隊列頭部的索引位）；ArrayDeque集合中還有一個名為tail的屬性，主要用于標識下一次進行添加操作的數(shù)據(jù)對象索引位（隊列尾部的索引位）。head屬性和tail屬性所標識的有效數(shù)據(jù)范圍在不停地變化，甚至有時tail屬性記錄的索引值會小于head屬性記錄的索引值，但這絲毫不影響它們對有效數(shù)據(jù)范圍的標識。將圖2-2中的循環(huán)數(shù)組展開，如圖2-3所示，可以發(fā)現(xiàn)，tail屬性記錄的索引值小于head屬性記錄的索引值。
當tail屬性指向數(shù)組中的最后一個索引位并進行下一次添加操作時，數(shù)組不一定進行擴容操作，更可能發(fā)生的情況是，tail屬性重新從當前數(shù)組的0號索引位開始，循環(huán)利用有效數(shù)據(jù)范圍外的數(shù)組索引位存儲新的數(shù)據(jù)對象（ArrayDeque集合內(nèi)部雖然是一個可以循環(huán)利用的數(shù)組結(jié)構(gòu)，但同樣存在擴容場景，并且在擴容時需要考慮的各種情況較為復雜，在后續(xù)章節(jié)中會進行詳細說明）。