隊(duì)列是一種重要的數(shù)據(jù)結(jié)構(gòu)沦辙，Java 語言提供了隊(duì)列的支持司浪，內(nèi)置了多種類型的隊(duì)列供我們使用消痛。限于篇幅且叁，本文不會(huì)討論太多細(xì)節(jié)。

隊(duì)列數(shù)據(jù)結(jié)構(gòu)

隊(duì)列是一個(gè)先進(jìn)先出的抽象數(shù)據(jù)結(jié)構(gòu)秩伞，可類比于生活中的排隊(duì)場(chǎng)景逞带。通常情況下，隊(duì)列有數(shù)組和鏈表兩種實(shí)現(xiàn)方式纱新。

采用鏈表實(shí)現(xiàn)的隊(duì)列展氓，沒有個(gè)數(shù)限制。插入元素時(shí)直接接在鏈表的尾部脸爱，取出元素時(shí)直接從鏈表的頭部取出即可遇汞。

采用數(shù)組實(shí)現(xiàn)的隊(duì)列，通常是循環(huán)數(shù)組，受限于數(shù)組的大小空入，存在天然的個(gè)數(shù)上限络它。插入和取出元素時(shí)，必須采用隊(duì)列頭部指針和隊(duì)列尾部指針進(jìn)行隊(duì)列滿和隊(duì)列空的判斷歪赢。

Java 隊(duì)列定義

Java 定義了隊(duì)列的基本操作化戳，接口類型為?java.util.Queue，接口定義如下所示埋凯。Queue 定義了兩套隊(duì)列操作方法：

public interface Queue<E> extends Collection<E> {
    //插入元素却盘，成功返回true，失敗拋出異常
    boolean add(E e);

    //插入元素媳拴，成功返回true黄橘，失敗返回false或拋出異常 
    boolean offer(E e);

    //取出并移除頭部元素，空隊(duì)列拋出異常 
    E remove();

    //取出并移除頭部元素屈溉，空隊(duì)列返回null 
    E poll();

    //取出但不移除頭部元素塞关，空隊(duì)列拋出異常 
    E element();

    //取出但不移除頭部元素，空隊(duì)列返回null 
    E peek();
}

Queue 作為先進(jìn)先出隊(duì)列子巾，只能從頭部取元素帆赢、插入元素到尾部。Java 同樣定義了雙向隊(duì)列 Deque线梗，可以同時(shí)在頭部椰于、尾部插入和取出元素，接口定義如下所示仪搔。Deque 也同樣定義了兩套隊(duì)列操作方法瘾婿，針對(duì)頭部操作方法為 xxxFirst、針對(duì)尾部操作方法為 xxxLast：

Deque 另外還有?removeFirstOccurrence昌阿、removeLastOccurrence 方法用于刪除指定元素饥脑，元素存在則刪除恳邀，不存在則隊(duì)列不變。

public interface Deque<E> extends Queue<E> {
    //插入元素到隊(duì)列頭部好啰，失敗拋出異常 
    void addFirst(E e);

    //插入元素到隊(duì)列尾部轩娶，失敗拋出異常 ?
    void addLast(E e);

    //插入元素到隊(duì)列頭部儿奶，失敗返回false或拋出異常 
    boolean offerFirst(E e);

    //插入元素到隊(duì)列尾部框往，失敗返回false拋出異常 ?
    boolean offerLast(E e);

    //取出并移除頭部元素，空隊(duì)列拋出異常 
    E removeFirst();

    //取出并移除尾部元素闯捎，空隊(duì)列拋出異常 
    E removeLast();

    //取出并移除頭部元素椰弊，空隊(duì)列返回null
    E pollFirst();

    //取出并移除尾部元素，空隊(duì)列返回null
    E pollLast();

    //取出但不移除頭部元素瓤鼻，空隊(duì)列拋出異常
    E getFirst();

    //取出但不移除尾部元素秉版，空隊(duì)列拋出異常
    E getLast();

    //取出但不移除頭部元素，空隊(duì)列返回null
    E peekFirst();

    //取出但不移除尾部元素茬祷，空隊(duì)列返回null
    E peekLast();

    //移除指定頭部元素清焕，若不存在隊(duì)列不變，移除成功返回true 
    boolean removeFirstOccurrence(Object o);

    //移除指定尾部元素祭犯，若不存在隊(duì)列不變秸妥，移除成功返回true 
    boolean removeLastOccurrence(Object o);

    //單向隊(duì)列方法，參考Queue   
    //棧方法沃粗，參考棧
    //集合方法粥惧，參考集合定義   
}

Java 并發(fā)工具包中定義了阻塞隊(duì)列?BlockingQueue 和 BlockingDueue。阻塞隊(duì)列在前面的隊(duì)列定義基礎(chǔ)上增加了以下幾個(gè)方法最盅，來支持阻塞操作突雪。

Java 中的 Queue 實(shí)現(xiàn)

Java 中的隊(duì)列實(shí)現(xiàn)侨核，基本上都繼承了 AbstractQueue 類。AbstractQueue 抽象隊(duì)列實(shí)現(xiàn)了 add灌灾、remove搓译、element 方法，這些方法調(diào)用 offer锋喜、poll些己、peek 方法并在失敗時(shí)拋出異常豌鸡，此外還提供了清空隊(duì)列的 clear 方法和批量插入元素的 addAll 方法。

非阻塞隊(duì)列訪問隊(duì)列元素時(shí)可以立即返回段标，主要有優(yōu)先級(jí)隊(duì)列 PriorityQueue涯冠、并發(fā)隊(duì)列 ConcurrentLinkedQueue。

PriorityQueue 是一個(gè)無界優(yōu)先級(jí)隊(duì)列逼庞，基于一個(gè)優(yōu)先級(jí)堆實(shí)現(xiàn)蛇更。隊(duì)列中的元素按照自然排序先后排列，或者使用創(chuàng)建時(shí)提供的 Comparator 比較先后順序赛糟。優(yōu)先級(jí)隊(duì)列需要比較順序派任，因此不能包含 null 元素。使用自然順序排序時(shí)璧南，元素必須是可以比較大小的掌逛，否則會(huì)導(dǎo)致類型轉(zhuǎn)換異常。優(yōu)先級(jí)隊(duì)列的頭部元素是隊(duì)列中按照順序最靠前的元素司倚，如有多個(gè)元素排序相等則隨機(jī)選擇一個(gè)豆混。

ConcurrentLinkedQueue 是一個(gè)基于鏈表實(shí)現(xiàn)的線程安全的無界隊(duì)列。內(nèi)部元素按先進(jìn)先出的順序排序动知，最后插入的元素位于隊(duì)列尾部皿伺。ConcurrentLinkedQueue 不允許插入 null。當(dāng)有多個(gè)線程同時(shí)訪問隊(duì)列時(shí)拍柒，此隊(duì)列是一個(gè)比較合適的選擇心傀。

Queue 接口的子接口 BlockingQueue 定義了阻塞隊(duì)列。阻塞隊(duì)列訪問隊(duì)列元素時(shí)拆讯，可能會(huì)一直阻塞直到操作完成脂男，比如從空隊(duì)列中取元素、向滿隊(duì)列中插入元素等种呐，主要有延時(shí)隊(duì)列宰翅、同步隊(duì)列、鏈表阻塞隊(duì)列爽室、數(shù)組阻塞隊(duì)列汁讼、優(yōu)先級(jí)阻塞隊(duì)列。

DelayQueue 是一個(gè)無界延時(shí)隊(duì)列阔墩，元素只有在延時(shí)時(shí)間已經(jīng)過期的情況下才能被訪問嘿架。頭部元素是隊(duì)列中延時(shí)時(shí)間過期最久的元素。如果沒有元素過期則沒有頭部元素啸箫，取元素的方法會(huì)返回 null耸彪。當(dāng)元素過期時(shí)，調(diào)用元素的 getDelay 方法會(huì)返回 0 或 負(fù)數(shù)忘苛。未過期的元素不能被取出蝉娜，但是統(tǒng)計(jì)隊(duì)列大小時(shí)仍然包含未過期元素唱较。

SynchronousQueue 是一個(gè)同步隊(duì)列。同步隊(duì)列與其他阻塞隊(duì)列不太一樣召川，插入元素時(shí)會(huì)一直阻塞直到有另一個(gè)線程取元素南缓，取元素同樣會(huì)一直阻塞直到有另一個(gè)線程插入元素。同步隊(duì)列本身沒有容量的概念荧呐，也不保持元素汉形，可以理解為兩個(gè)線程交換數(shù)據(jù)的媒介，因此也不能執(zhí)行 size坛增、peek 類型的操作获雕。

LinkedBlockingQueue 是一個(gè)基于鏈表實(shí)現(xiàn)的有界的阻塞隊(duì)列薄腻。如未指定隊(duì)列大小收捣，默認(rèn)為Integer.MAX_VALUE。內(nèi)部元素按先進(jìn)先出的順序排序庵楷，最后插入的元素位于隊(duì)列尾部罢艾。

ArrayBlockingQueue 是一個(gè)基于數(shù)組實(shí)現(xiàn)的有界的阻塞隊(duì)列。一旦創(chuàng)建隊(duì)列的大小不會(huì)再發(fā)生變化尽纽，是一個(gè)典型的有界隊(duì)列咐蚯。內(nèi)部元素按先進(jìn)先出的順序排序，最后插入的元素位于隊(duì)列尾部弄贿。

PriorityBlockingQueue 是一個(gè)無界優(yōu)先級(jí)阻塞隊(duì)列春锋。這個(gè)隊(duì)列與 PriorityQueue 類似，但當(dāng)隊(duì)列空或滿時(shí)會(huì)阻塞相關(guān)操作差凹。

阻塞隊(duì)列經(jīng)常存在生產(chǎn)者等待消費(fèi)者消費(fèi)元素的情況期奔，BlockingQueue 的子接口 TransferQueue 定義了一種新隊(duì)列來支持這種情況，實(shí)現(xiàn)類為 LinkedTransferQueue危尿。TransferQueue?允許生產(chǎn)者調(diào)用 transfer 方法來等待消費(fèi)者調(diào)用 take 或 poll 消費(fèi)元素呐萌，如果有消費(fèi)者正在取元素則直接交給消費(fèi)者，否則便把元素插入隊(duì)列尾部并阻塞生產(chǎn)者當(dāng)前線程直到元素被消費(fèi)者取走谊娇。

Java 中的 Deque 實(shí)現(xiàn)

Deque 接口的實(shí)現(xiàn)相對(duì)較少肺孤，主要有 LinkedList、ArrayDeque济欢、ConcurrentLinkedDeque 和 LinkedBlockingDeque赠堵。

LinkedList 就是我們常用的鏈表，實(shí)現(xiàn)了 Deque 接口法褥。LinkedList 為了提高性能茫叭，本身支持從鏈表兩端插入和取出元素，與 Deque 的要求恰好一致挖胃。

ArrayDeque 是一個(gè)基于數(shù)組的雙向隊(duì)列杂靶，大小可變梆惯。ArrayDeque 是非線程安全的，在多線程并發(fā)時(shí)需要外部調(diào)用者自行處理并發(fā)吗垮。

ConcurrentLinkedDeque 是一個(gè)基于鏈表實(shí)現(xiàn)的線程安全的無界雙向隊(duì)列垛吗。內(nèi)部元素按先進(jìn)先出的順序排序，最后插入的元素位于隊(duì)列尾部烁登，不允許插入 null怯屉。當(dāng)有多個(gè)線程同時(shí)訪問雙向隊(duì)列時(shí)，此隊(duì)列是一個(gè)比較合適的選擇饵沧。

Deque 接口有一個(gè)子接口 BlockingDeque 定義了阻塞雙向隊(duì)列锨络。實(shí)現(xiàn)類為 LinkedBlockingDeque，是一個(gè)基于鏈表實(shí)現(xiàn)的有界的阻塞雙向隊(duì)列狼牺。如未指定隊(duì)列大小羡儿，默認(rèn)為Integer.MAX_VALUE。內(nèi)部元素按先進(jìn)先出的順序排序是钥，最后插入的元素位于隊(duì)列尾部掠归。

Java 中的隊(duì)列就討論到這里，歡迎留言留下您的觀點(diǎn)和看法悄泥。

分享學(xué)習(xí)筆記和技術(shù)總結(jié)虏冻，內(nèi)容涉及 Java 技術(shù)、軟件架構(gòu)弹囚、前沿技術(shù)厨相、開源框架、數(shù)據(jù)結(jié)構(gòu)與算法鸥鹉、編程感悟等多個(gè)領(lǐng)域蛮穿，歡迎關(guān)注。本文首發(fā)于微信公眾號(hào)“后端開發(fā)那點(diǎn)事兒” 宋舷。