Queue

Queue繼承自 Collection，我們先來(lái)看看類結(jié)構(gòu)吧，代碼量比較少，我直接貼代碼了

public interface Queue<E> extends Collection<E> {
    boolean add(E var1);
    boolean offer(E var1);
    E remove();
    E poll();
    E element();
    E peek();
}

從方法名上不太好猜每個(gè)方法的作用，我們直接來(lái)看 API 吧

好像就除了對(duì)增刪查操作增加了一個(gè)不拋出異常的方法，沒什么特點(diǎn)吧，我們繼續(xù)看描述~

在處理元素前用于保存元素的 collection。除了基本的 Collection 操作外，隊(duì)列還提供其他的插入、提取和檢查操作。每個(gè)方法都存在兩種形式：一種拋出異常（操作失敗時(shí)），另一種返回一個(gè)特殊值（null 或 false，具體取決于操作）。插入操作的后一種形式是用于專門為有容量限制的 Queue 實(shí)現(xiàn)設(shè)計(jì)的；在大多數(shù)實(shí)現(xiàn)中，插入操作不會(huì)失敗。

就描述了這三組方法的區(qū)別，那么以后我操作隊(duì)列盡量用不拋出異常的方法總行了吧。另外也沒看出什么名堂，那么隊(duì)列這個(gè)接口到底是規(guī)范了什么行為？我記得隊(duì)列好像是一種數(shù)據(jù)常用的結(jié)構(gòu)，我們來(lái)看看百度百科的定義吧

隊(duì)列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作，和棧一樣，隊(duì)列是一種操作受限制的線性表。進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭。

看了百度百科的描述，才知道隊(duì)列規(guī)范了集合只允許在表前端刪除，在表后端插入。這不就是 FIFO 嘛~~

什么是 FIFO？

FIFO 是英語(yǔ) first in first out 的縮寫。先進(jìn)先出，想象一下，在車輛在通過(guò)不允許超車的隧道時(shí)，是不是先進(jìn)入隧道的車輛最先出隧道。

FIFO 有什么用？

這個(gè)問(wèn)題我回答不了，隊(duì)列只是一種數(shù)據(jù)結(jié)構(gòu)，在某些特定的場(chǎng)合，用隊(duì)列實(shí)現(xiàn)效率會(huì)比較高。

Queue 的抽象實(shí)現(xiàn)類

AbstractQueue 是Queue 的抽象實(shí)現(xiàn)類，和Lst、Set 的抽象實(shí)現(xiàn)類一樣，AbstractQueue 也繼承自 AbstractCollection。
AbstractQueue 實(shí)現(xiàn)的方法不多，主要就 add、remove、element 三個(gè)方法的操作失敗拋出了異常。

Queue 的實(shí)現(xiàn)類

PriorityQueue 直接繼承自 AbstractQueue，并且除序列號(hào)接口外，沒實(shí)現(xiàn)任何接口，大概算是最忠誠(chéng)的 Queue 實(shí)現(xiàn)類吧。照慣例，我們先來(lái)看看 API 介紹。

一個(gè)基于優(yōu)先級(jí)堆的無(wú)界優(yōu)先級(jí)隊(duì)列。優(yōu)先級(jí)隊(duì)列的元素按照其自然順序進(jìn)行排序，或者根據(jù)構(gòu)造隊(duì)列時(shí)提供的 Comparator 進(jìn)行排序，具體取決于所使用的構(gòu)造方法。優(yōu)先級(jí)隊(duì)列不允許使用 null 元素。依靠自然順序的優(yōu)先級(jí)隊(duì)列還不允許插入不可比較的對(duì)象.
此隊(duì)列的頭 是按指定排序方式確定的最小 元素。如果多個(gè)元素都是最小值，則頭是其中一個(gè)元素——選擇方法是任意的。隊(duì)列獲取操作 poll、remove、peek 和 element 訪問(wèn)處于隊(duì)列頭的元素。
優(yōu)先級(jí)隊(duì)列是無(wú)界的，但是有一個(gè)內(nèi)部容量，控制著用于存儲(chǔ)隊(duì)列元素的數(shù)組大小。它通常至少等于隊(duì)列的大小。隨著不斷向優(yōu)先級(jí)隊(duì)列添加元素，其容量會(huì)自動(dòng)增加。無(wú)需指定容量增加策略的細(xì)節(jié)。

進(jìn)隊(duì)列的數(shù)據(jù)還要進(jìn)行排序，每次取都是取到元素最小值，尼瑪，說(shuō)好的 FIFO 呢？好吧，我暫且當(dāng)這是一個(gè)取出時(shí)有順序的隊(duì)列，看起來(lái)和昨天學(xué)的 TreeSet 功能差不多哈。

PriorityQueue 叫優(yōu)先隊(duì)列，即優(yōu)先把元素最小值存到隊(duì)頭。想象一下，使用PriorityQueue去管理一個(gè)班的學(xué)生，根據(jù)可以年齡、成績(jī)、身高設(shè)置好對(duì)應(yīng)的 Comparator ，然后就能自動(dòng)從小到大排序呢。哈哈哈~

我們先來(lái)看一下 PriorityQueue 的實(shí)現(xiàn)吧~

類成員變量如下~

public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable {
    private static final long serialVersionUID = -7720805057305804111L;
    private static final int DEFAULT_INITIAL_CAPACITY = 11;
    transient Object[] queue;
    private int size;
    private final Comparator<? super E> comparator;
    transient int modCount;
    private static final int MAX_ARRAY_SIZE = 2147483639;
}

沒錯(cuò)，基于數(shù)組的實(shí)現(xiàn)，也能找到 grow 擴(kuò)容方法，少了 List 的各種方法，Queue 的方法我們前面也看了。那么我們就之前去看他是怎么實(shí)現(xiàn)優(yōu)先隊(duì)列的~

思考一下，既然是數(shù)組實(shí)現(xiàn)，又能按元素大小順序去取出，那么肯定是在添加元素的時(shí)候做的排序，直接把對(duì)應(yīng)的元素值大小的元素添加到對(duì)應(yīng)的位置。那么我們就從 add 方法看起吧~~

public boolean add(E var1) {
    return this.offer(var1);
}

public boolean offer(E var1) {
    if(var1 == null) {
        throw new NullPointerException();
    } else {
        ++this.modCount;
        int var2 = this.size;
        if(var2 >= this.queue.length) {
            this.grow(var2 + 1);
        }

        this.size = var2 + 1;
        if(var2 == 0) {
            this.queue[0] = var1;
        } else {
            this.siftUp(var2, var1);
        }

        return true;
    }
}
private void siftUp(int childIndex) {
    E target = elements[childIndex];
    int parentIndex;
    while (childIndex > 0) {
        parentIndex = (childIndex - 1) / 2;
        E parent = elements[parentIndex];
        if (compare(parent, target) <= 0) {
            break;
        }
        elements[childIndex] = parent;
        childIndex = parentIndex;
    }
    elements[childIndex] = target;
}

上面的方法調(diào)用都很簡(jiǎn)單，我就不寫注釋了，add 調(diào)用 offer 添加元素，如果集合里面的元素個(gè)數(shù)不為零，則調(diào)用 siftUp 方法把元素插入合適的位置。

敲黑板~~接下來(lái)的東西我看了老半天才看明白。有點(diǎn)吃力

注意了，siftUp里面的算法有點(diǎn)奇怪，我一開始還以為是二分插入法，然而并不是。

首先，我們這里走進(jìn)了一個(gè)誤區(qū)，PriorityQueue 雖然是一個(gè)優(yōu)先隊(duì)列，能夠滿足我們剛剛說(shuō)的需求，把一個(gè)班的學(xué)生按年齡大小順序取出來(lái)，但是在內(nèi)存中（數(shù)組中）的保存卻并不是按照從小到大的順序保存的，但是一直 poll，是能夠按照元素從小到大的順去取出結(jié)果。

這里我做了一個(gè)小測(cè)試。

PriorityQueue<Integer> integers = new PriorityQueue<>();
integers.add(8);                                        
integers.add(6);                                       
integers.add(5);                                       

已知 PriorityQueue 用數(shù)組存儲(chǔ)，大家猜猜我這樣存進(jìn)隊(duì)列的三個(gè)數(shù)子是怎樣存儲(chǔ)的？
一開始我以為是5、6、8的順序，但是 debug 的時(shí)候看到 PriorityQueue 里面保存數(shù)據(jù)數(shù)組里面的存放順序是5、8、6.why？

然后我調(diào)用下面這個(gè)方法打印~

while (!integers.isEmpty()) {              
    Log.e("_____", integers.poll() + "~~");
}                                          

結(jié)果是5、6、8.這他媽就尷尬了。

然后怎么辦~去找度娘唄。。。

好了，開始解析~~

不知道大家記不記得一種數(shù)據(jù)結(jié)構(gòu)叫二叉樹，這里就是使用了二叉樹的思路，所以比較難理解。

首先，這里使用的是一種特殊的二叉樹：1.父節(jié)點(diǎn)永遠(yuǎn)小于子節(jié)點(diǎn)，2.優(yōu)先填滿第 n 層樹枝再填 n+1 層樹枝。也就是說(shuō)，數(shù)組里面的5、8、6是這樣存儲(chǔ)的

依次添加元素8、6、5.
  5                         
 / \    
8   6   
    ‖
    ∨
數(shù)組角標(biāo)位置
  0
 / \
1   2

這樣能理解了吧，再回過(guò)頭去看siftUp方法，捋一下添加元素的過(guò)程。

• 添加8
  沒什么好說(shuō)的，直接添加一個(gè)元素到到數(shù)組[0]即可，二叉樹添加一個(gè)頂級(jí)節(jié)點(diǎn)

• 添加5
  首先把[1]的位置賦值給5，使得數(shù)組中的元素為{8，5}
  然后執(zhí)行siftUp(1)方法(1是剛剛插入元素5的角標(biāo))

    siftUp方法首先獲取5的父節(jié)點(diǎn)，判斷5是否小于父節(jié)點(diǎn)。
    如果小于，則交換位置繼續(xù)比較祖父節(jié)點(diǎn)
    如果大于或者已經(jīng)到頂級(jí)節(jié)點(diǎn)，結(jié)束。
  

siftUp方法后，數(shù)組變?yōu)閧5，8}

• 添加6
  重復(fù)上面的動(dòng)作，數(shù)組變?yōu)閧5，8，6}

問(wèn)：如果此時(shí)添加數(shù)字7，數(shù)組的順序是多少？
思考一下3分鐘~~

好，3分鐘過(guò)去了，結(jié)果是{5，7，6，8}
為什么會(huì)這樣？拿著數(shù)字7代入到上面的方法中去算呀，首先8在數(shù)組中的角標(biāo)是3，3要去和父節(jié)點(diǎn)比，求父節(jié)點(diǎn)的公式是（3-1）/2 = 1.于是父節(jié)點(diǎn)的角標(biāo)是1，7<8，因此交換位置，此時(shí)角標(biāo)1還有父節(jié)點(diǎn) （1-1）/2 = 0,再比較7和5，7>5，滿足大于父節(jié)點(diǎn)條件，結(jié)束。

好了，現(xiàn)在應(yīng)該明白了吧~~~沒明白再回過(guò)頭去理解一遍。
接下來(lái)，我們來(lái)看循環(huán)調(diào)用 poll() 方法是怎樣從{5，8，6}的數(shù)組中按照從小到大的順序取出5、6、8.
我們來(lái)看 poll()方法

public E poll() {
    if (isEmpty()) {
        return null;
    }
    E result = elements[0];
    removeAt(0);
    return result;
}
private void removeAt(int index) {
    size--;
    E moved = elements[size];
    elements[index] = moved;
    siftDown(index);
    elements[size] = null;
    if (moved == elements[index]) {
        siftUp(index);
    }
}
private void siftDown(int rootIndex) {
    E target = elements[rootIndex];
    int childIndex;
    while ((childIndex = rootIndex * 2 + 1) < size) {
        if (childIndex + 1 < size
                    && compare(elements[childIndex + 1], elements[childIndex]) < 0) {
            childIndex++;
        }
        if (compare(target, elements[childIndex]) <= 0) {
            break;
        }
        elements[rootIndex] = elements[childIndex];
        rootIndex = childIndex;
    }
    elements[rootIndex] = target;
}

這是 api23 里面 PriorityQueue 的方法，和 Java8 略有不同，但實(shí)現(xiàn)都是一樣的，只是方法看起來(lái)好理解一些。

首先 poll 方法取出了數(shù)組角標(biāo)0的值，這點(diǎn)不用質(zhì)疑，因?yàn)榻菢?biāo)0對(duì)應(yīng)二叉樹的最高節(jié)點(diǎn)，也就是最小值。

然后在 removeAt 方法里面把數(shù)組的最后一個(gè)元素覆蓋了第0個(gè)元素，再是將最后一個(gè)元素置空，好，到了這里，進(jìn)入第二個(gè)關(guān)鍵點(diǎn)了，黑板敲起來(lái)~~

這里在賦值之后調(diào)用了 siftDown(0);
我們來(lái)看 siftDown()方法~
這個(gè)方法從0角標(biāo)（最頂級(jí)父節(jié)點(diǎn)）開始，先判斷左右子節(jié)點(diǎn)，取較小的那個(gè)一，和父節(jié)點(diǎn)比較，然后再對(duì)比左右子節(jié)點(diǎn)。根據(jù)我們這里二叉樹的特點(diǎn)，最終能取到最小的那個(gè)元素放到頂級(jí)父節(jié)點(diǎn)，保證下一次 poll能取到當(dāng)前集合最小的元素。具體代碼不帶著讀了~~

ok，PriorityQueue 看完了。

Deque

剛剛我們一直在找 FIFO 的集合，找到個(gè) PriorityQueue，然而并不是。
然后我們繼續(xù)找唄，發(fā)現(xiàn)了 Queue 有一個(gè)子接口Deque

來(lái)看看 API 文檔的定義~

一個(gè)線性 collection，支持在兩端插入和移除元素。名稱 deque 是“double ended queue（雙端隊(duì)列）”的縮寫，通常讀為“deck”。大多數(shù) Deque 實(shí)現(xiàn)對(duì)于它們能夠包含的元素?cái)?shù)沒有固定限制，但此接口既支持有容量限制的雙端隊(duì)列，也支持沒有固定大小限制的雙端隊(duì)列。

此接口定義在雙端隊(duì)列兩端訪問(wèn)元素的方法。提供插入、移除和檢查元素的方法。每種方法都存在兩種形式：一種形式在操作失敗時(shí)拋出異常，另一種形式返回一個(gè)特殊值（null 或 false，具體取決于操作）。插入操作的后一種形式是專為使用有容量限制的 Deque 實(shí)現(xiàn)設(shè)計(jì)的；在大多數(shù)實(shí)現(xiàn)中，插入操作不能失敗。

嗯~就是一個(gè)首尾插入刪除操作都直接的接口。

我們剛剛說(shuō)了 Queue 遵循 FIFO 規(guī)則，當(dāng)有了 Deque，我們還能實(shí)現(xiàn) LIFO（后進(jìn)先出）。反正像先進(jìn)后出、后進(jìn)先出都能在 Deque 的實(shí)現(xiàn)類上做到，具體看各位 Coder 們?cè)趺床僮髁恕?/p>

總結(jié)一下 Deque 的方法~

____特么的，MD 語(yǔ)法不支持這種不對(duì)齊表格

如果想用作 LIFO 隊(duì)列，應(yīng)優(yōu)先使用此接口，而不是遺留的 Stack 類。在將雙端隊(duì)列用作堆棧時(shí)，元素被推入雙端隊(duì)列的開頭并從雙端隊(duì)列開頭彈出。堆棧方法完全等效于 Deque 方法，如下表所示：

就醬紫吧，也沒什么特別的，我個(gè)人不太喜歡這個(gè)接口，我覺得這個(gè)接口規(guī)范的行為有點(diǎn)多，不符合接口隔離原則和單一職能原則。

接下來(lái)我們就去看看 Deque 的實(shí)現(xiàn)類吧。

看兩個(gè)具有代表性的類吧，第一個(gè)是基于數(shù)組實(shí)現(xiàn)的 ArrayQeque，第二個(gè)是基于鏈表實(shí)現(xiàn)的LinkedList。

LinkedList

前面 List 的時(shí)候我們看過(guò) LinkedList，LinkedList 繼承自AbstractList，同時(shí)也實(shí)現(xiàn)了 List 接口，因此這是一個(gè)很全能的類。一句話描述就是：基于鏈表結(jié)構(gòu)實(shí)現(xiàn)的數(shù)組，同時(shí)又支持雙向隊(duì)列操作。

還記得之前在 List 結(jié)尾留的一個(gè)思考題么：怎樣用鏈表的結(jié)構(gòu)快速實(shí)現(xiàn)棧功能LinkedListStack？

public class LinkedListStack extends LinkedList{
    public LinkedListStack(){
        super();
    }

    @Override
    public void push(Object o) {
        super.push(o);
    }

    @Override
    public Object pop() {
        return super.pop();
    }

    @Override
    public Object peek() {
        return super.peek();
    }

    @Override
    public boolean isEmpty() {
        return super.isEmpty();
    }

    public int search(Object o){
        return indexOf(o);
    }
}

吶，這里給出了實(shí)現(xiàn)，其實(shí)什么都沒做，就是調(diào)用了父類方法。這個(gè)類只是看起來(lái)結(jié)構(gòu)清晰的實(shí)現(xiàn)了 LIFO，但是由于繼承自 LinkedList，還是可以調(diào)用 addFirst 等各種“非法操作方法”，這就是我說(shuō)的不理解 Java 為什么要這樣設(shè)計(jì)，還推薦使用 Deque 替換棧實(shí)現(xiàn)。項(xiàng)目實(shí)際開發(fā)中，同學(xué)們要使用棧結(jié)構(gòu)直接用 LinkedList就行了，我這里 LinkedListStack 只是便于大家理解 LinkedList 也可以用作棧集合。

ArrayDeque

照慣例先看 API 定義~

Deque接口的大小可變數(shù)組的實(shí)現(xiàn)。數(shù)組雙端隊(duì)列沒有容量限制；它們可根據(jù)需要增加以支持使用。它們不是線程安全的；在沒有外部同步時(shí)，它們不支持多個(gè)線程的并發(fā)訪問(wèn)。禁止 null 元素。此類很可能在用作堆棧時(shí)快于 Stack，在用作隊(duì)列時(shí)快于 LinkedList。

感覺 ArrayDeque 才是一個(gè)正常的 Deque 實(shí)現(xiàn)類，ArrayDeque 直接繼承自 AbstractCollection，實(shí)現(xiàn)了Deque接口。

類部實(shí)現(xiàn)和 ArrayList 一樣都是基于數(shù)組，當(dāng)頭尾下標(biāo)相等時(shí)，調(diào)用doubleCapacity（）方法，執(zhí)行翻倍擴(kuò)容操作。

頭尾操作是什么鬼？我們都知道ArrayDeque 是雙向列表，就是可以兩端一起操作的列表。因此使用了兩個(gè)指針 head 和tail 來(lái)保存當(dāng)前頭尾的 index，一開始默認(rèn)都是0角標(biāo)，當(dāng)添加一個(gè)到尾的時(shí)候，tail先加1，再把值存放到 tail 角標(biāo)的數(shù)組里面去。
那么 addFirst 是怎么操作的呢？head 是0，添加到-1的角標(biāo)上面去？其實(shí)不是的，這里 你可以把這個(gè)數(shù)組當(dāng)成是一個(gè)首尾相連的鏈表，head 是0的時(shí)候 addFirst 實(shí)際上是把值存到了數(shù)組最后一個(gè)角標(biāo)里面去了。即： 當(dāng) head 等于0的時(shí)候 head - 1 的值 數(shù)組.length - 1,代碼實(shí)現(xiàn)如下。

如圖，這是我如下代碼的執(zhí)行添加60時(shí) debug

ArrayDeque<Integer> integers = new ArrayDeque<>();
integers.addLast(8);
integers.addFirst(60);

然后當(dāng)head == tail的時(shí)候表示數(shù)組用滿了，需要擴(kuò)容，就執(zhí)行doubleCapacity擴(kuò)容，這里的擴(kuò)容和 ArrayList 的代碼差不多，就不去分析了。

總結(jié)

凡是牽涉到需要使用 FIFO 或者 LIFO 的數(shù)據(jù)結(jié)構(gòu)時(shí)，推薦使用 ArrayDeque，LinkedList 也行，還有 get(index)方法~~