Queue

Queue繼承自 Collection，我們先來(lái)看看類(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è)不拋出異常的方法蛾狗，沒(méi)什么特點(diǎn)吧晋涣，我們繼續(xù)看描述~

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

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

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

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

什么是 FIFO禁舷？

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

FIFO 有什么用洁桌？

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

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

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

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

PriorityQueue 直接繼承自 AbstractQueue雀瓢，并且除序列號(hào)接口外枢析，沒(méi)實(shí)現(xiàn)任何接口，大概算是最忠誠(chéng)的 Queue 實(shí)現(xiàn)類(lèi)吧刃麸。照慣例醒叁，我們先來(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)吧~

類(lèi)成員變量如下~

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

沒(méi)錯(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)單包雀，我就不寫(xiě)注釋了，add 調(diào)用 offer 添加元素亲铡，如果集合里面的元素個(gè)數(shù)不為零才写，則調(diào)用 siftUp 方法把元素插入合適的位置。

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

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

首先，我們這里走進(jìn)了一個(gè)誤區(qū)疑务，PriorityQueue 雖然是一個(gè)優(yōu)先隊(duì)列沾凄，能夠滿(mǎn)足我們剛剛說(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ǔ)的涤垫？
一開(kāi)始我以為是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.這他媽就尷尬了。

然后怎么辦~去找度娘唄镰惦。迷守。。

好了旺入，開(kāi)始解析~~

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

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

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

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

• 添加8
  沒(méi)什么好說(shuō)的活箕，直接添加一個(gè)元素到到數(shù)組[0]即可力麸，二叉樹(shù)添加一個(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已维，滿(mǎn)足大于父節(jié)點(diǎn)條件，結(jié)束已日。

好了垛耳，現(xiàn)在應(yīng)該明白了吧~~~沒(méi)明白再回過(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)二叉樹(shù)的最高節(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)）開(kāi)始啦逆，先判斷左右子節(jié)點(diǎn)，取較小的那個(gè)一笛洛，和父節(jié)點(diǎn)比較夏志，然后再對(duì)比左右子節(jié)點(diǎn)。根據(jù)我們這里二叉樹(shù)的特點(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，支持在兩端插入和移除元素宣蠕。名稱(chēng) deque 是“double ended queue（雙端隊(duì)列）”的縮寫(xiě)例隆，通常讀為“deck”。大多數(shù) Deque 實(shí)現(xiàn)對(duì)于它們能夠包含的元素?cái)?shù)沒(méi)有固定限制抢蚀，但此接口既支持有容量限制的雙端隊(duì)列镀层，也支持沒(méi)有固定大小限制的雙端隊(duì)列。

此接口定義在雙端隊(duì)列兩端訪問(wèn)元素的方法皿曲。提供插入唱逢、移除和檢查元素的方法。每種方法都存在兩種形式：一種形式在操作失敗時(shí)拋出異常屋休，另一種形式返回一個(gè)特殊值（null 或 false坞古，具體取決于操作）。插入操作的后一種形式是專(zhuān)為使用有容量限制的 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)類(lèi)上做到，具體看各位 Coder 們?cè)趺床僮髁恕?/p>

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

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

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

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

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

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

LinkedList

前面 List 的時(shí)候我們看過(guò) LinkedList巷怜，LinkedList 繼承自AbstractList葛超，同時(shí)也實(shí)現(xiàn)了 List 接口，因此這是一個(gè)很全能的類(lèi)延塑。一句話(huà)描述就是：基于鏈表結(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í)什么都沒(méi)做宋雏，就是調(diào)用了父類(lèi)方法芜飘。這個(gè)類(lèi)只是看起來(lái)結(jié)構(gòu)清晰的實(shí)現(xiàn)了 LIFO，但是由于繼承自 LinkedList磨总，還是可以調(diào)用 addFirst 等各種“非法操作方法”嗦明，這就是我說(shuō)的不理解 Java 為什么要這樣設(shè)計(jì)，還推薦使用 Deque 替換棧實(shí)現(xiàn)舍败。項(xiàng)目實(shí)際開(kāi)發(fā)中招狸，同學(xué)們要使用棧結(jié)構(gòu)直接用 LinkedList就行了，我這里 LinkedListStack 只是便于大家理解 LinkedList 也可以用作棧集合邻薯。

ArrayDeque

照慣例先看 API 定義~

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

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

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

頭尾操作是什么鬼？我們都知道ArrayDeque 是雙向列表难菌，就是可以?xún)啥艘黄鸩僮鞯牧斜硎运荨Ｒ虼耸褂昧藘蓚€(gè)指針 head 和tail 來(lái)保存當(dāng)前頭尾的 index，一開(kāi)始默認(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ù)組用滿(mǎn)了慢叨，需要擴(kuò)容纽匙，就執(zhí)行doubleCapacity擴(kuò)容，這里的擴(kuò)容和 ArrayList 的代碼差不多拍谐，就不去分析了烛缔。

總結(jié)

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