摘要：隊(duì)列中有元素時(shí)，就說(shuō)明有過(guò)期了，線程繼續(xù)執(zhí)行，然后元素出隊(duì)，根據(jù)相應(yīng)的移除緩存。所以嚴(yán)格來(lái)說(shuō)，雖然實(shí)現(xiàn)了隊(duì)列接口，但是它的目的卻并不是隊(duì)列，而是將生產(chǎn)者消費(fèi)者線程配對(duì)。轉(zhuǎn)移隊(duì)列鏈?zhǔn)睫D(zhuǎn)移隊(duì)列。

本周在編寫短信驗(yàn)證碼頻率限制切面的時(shí)候，經(jīng)潘老師給的實(shí)現(xiàn)思路，使用隊(duì)列進(jìn)行實(shí)現(xiàn)。

看了看java.util包下的Queue接口，發(fā)現(xiàn)還從來(lái)沒(méi)用過(guò)呢！

Collection集合類接口，由它派生出List、Set和Queue，Map屬于另一個(gè)獨(dú)立的接口，和Collection沒(méi)有繼承關(guān)系。

List、Set和Map我們用的都是已經(jīng)相當(dāng)熟練了，今天，我們就來(lái)學(xué)習(xí)這個(gè)隊(duì)列Queue！

隊(duì)列與棧都是數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)話題，隊(duì)列：先進(jìn)先出；棧：后進(jìn)先出。

Queue接口中聲明了六個(gè)方法，分成三對(duì)來(lái)使用。

入隊(duì)操作

出隊(duì)操作

取隊(duì)頭操作

在java.util包中，除抽象類外，直接實(shí)現(xiàn)Queue接口的只有PriorityQueue優(yōu)先級(jí)隊(duì)列。

優(yōu)先級(jí)隊(duì)列比普通的隊(duì)列要高級(jí)，普通的隊(duì)列如果是先進(jìn)的肯定是在隊(duì)頭的，而優(yōu)先級(jí)隊(duì)列根據(jù)優(yōu)先級(jí)判斷當(dāng)前隊(duì)頭元素是什么。很適合實(shí)現(xiàn)操作系統(tǒng)中的按優(yōu)先級(jí)實(shí)現(xiàn)進(jìn)程調(diào)度。

如果需要使用優(yōu)先級(jí)隊(duì)列進(jìn)行排序時(shí)，需要傳入比較器。

該隊(duì)列使用數(shù)組實(shí)現(xiàn)，線程不安全。

java.util包中，Deque接口繼承Queue接口。

Deque：double-ended queue，雙端隊(duì)列。

雙端隊(duì)列，相比普通隊(duì)列就是可操作兩端，有兩個(gè)隊(duì)頭，也有兩個(gè)隊(duì)尾。

所以再去看Deque接口中聲明的方法，都是兩套的。offerFirst、offerLast、pollFirst、pollLast等。

所以說(shuō)，如果使用雙端隊(duì)列，不僅可以當(dāng)隊(duì)列用，也可以當(dāng)棧用，因?yàn)榭梢宰约嚎刂瞥龅氖顷?duì)頭還是隊(duì)尾。

Deque有兩個(gè)實(shí)現(xiàn)類：ArrayDeque和LinkedList。

原來(lái)LinkedList不僅實(shí)現(xiàn)了List接口，還實(shí)現(xiàn)了Deque接口。

兩者的區(qū)別顯而易見(jiàn)，一個(gè)是數(shù)組方式實(shí)現(xiàn)的，一個(gè)是鏈表的方式實(shí)現(xiàn)的。

這些都是java.util包下的，都是線程不安全的實(shí)現(xiàn)，JDK所有線程安全的隊(duì)列實(shí)現(xiàn)都在java.util.concurrent包下，也就是阻塞隊(duì)列BlockingQueue。

在concurrent包下，自然是做了線程安全處理的了，在多線程環(huán)境下操作隊(duì)列需要使用。

與阻塞隊(duì)列最密切的就是生產(chǎn)者消費(fèi)者模型了，我們一起來(lái)探討一下。

生產(chǎn)者消費(fèi)者模型，最初出現(xiàn)在操作系統(tǒng)中，多進(jìn)程/多線程進(jìn)行協(xié)作，完成同一任務(wù)，必然需要相互合作與相互制約。

舉一個(gè)符合實(shí)際的例子，我想喝可樂(lè)。

可口可樂(lè)公司就是生產(chǎn)者，用于生產(chǎn)商品。

超市就相當(dāng)于緩沖區(qū)，用于存儲(chǔ)生產(chǎn)者生產(chǎn)出來(lái)的可樂(lè)，公司生產(chǎn)出可樂(lè)，然后放到超市里賣。

我就是消費(fèi)者，去超市買可樂(lè)(消費(fèi)過(guò)程)。

所以就會(huì)有一個(gè)同步的問(wèn)題：

假設(shè)場(chǎng)景：超市能容量100瓶可樂(lè)。

所以，消費(fèi)者去購(gòu)買的前提是：超市內(nèi)有可樂(lè)，要不去了也買不著。

生產(chǎn)者生產(chǎn)的前提是：超市內(nèi)有空余位置，要不生產(chǎn)了往哪送呢？

類比到程序設(shè)計(jì)中，就是進(jìn)程或線程之間的相互制約，也就是所謂的同步！

線程類比

一圖勝千言，我就不贅述了。

消費(fèi)者線程想去找緩沖區(qū)要數(shù)據(jù)，先判斷緩沖區(qū)內(nèi)有沒(méi)有數(shù)據(jù)，如果沒(méi)有，消費(fèi)者就拿不到，這個(gè)線程就等待，直到：緩沖區(qū)內(nèi)有數(shù)據(jù)。如果有，就從緩沖區(qū)將數(shù)據(jù)拿走。

生產(chǎn)者線程要去生產(chǎn)數(shù)據(jù)，先判斷緩沖區(qū)內(nèi)有沒(méi)有空余位置，如果沒(méi)有，生產(chǎn)者就等待，直到：緩沖區(qū)內(nèi)有空位，如果有，就生產(chǎn)數(shù)據(jù)，放入緩沖區(qū)。

阻塞隊(duì)列正適合生產(chǎn)者消費(fèi)者模型，當(dāng)隊(duì)列滿時(shí)，入隊(duì)操作就會(huì)被阻塞，當(dāng)隊(duì)列空時(shí)，出隊(duì)操作就會(huì)被阻塞。

入隊(duì)出隊(duì)的offer方法和poll方法與原隊(duì)列接口的方法相比，多了時(shí)間的參數(shù)。當(dāng)發(fā)生阻塞時(shí)，如果超過(guò)了設(shè)置的時(shí)間，線程就會(huì)退出，畢竟如果最壞的情況，一直不滿足條件，也不能一直阻塞下去。

boolean offer(E e, long timeout, TimeUnit unit) throws InterruptedException;
E poll(long timeout, TimeUnit unit) throws InterruptedException;

ArrayBlockingQueue：數(shù)組實(shí)現(xiàn)的阻塞隊(duì)列。

LinkedBlockingQueue：鏈表實(shí)現(xiàn)的阻塞隊(duì)列。

PriorityBlockingQueue：優(yōu)先級(jí)阻塞隊(duì)列。

這個(gè)簡(jiǎn)單，就是同時(shí)實(shí)現(xiàn)了BlockingQueue和Deque接口。

java.util.concurrent包下只有一個(gè)雙向阻塞隊(duì)列的實(shí)現(xiàn)：LinkedBlockingDeque。

延時(shí)隊(duì)列：DelayQueue，看這個(gè)類名，無(wú)疑了，此隊(duì)列定與時(shí)間有關(guān)。

當(dāng)一個(gè)元素入隊(duì)時(shí)，它并不是馬上進(jìn)入隊(duì)列，而是根據(jù)設(shè)定的時(shí)間延時(shí)之后再入隊(duì)。

假設(shè)offer一個(gè)元素，設(shè)置時(shí)間為10s，在10s內(nèi)訪問(wèn)隊(duì)列，是訪問(wèn)不到元素的。

在延時(shí)之后，也就是10s之后，再去訪問(wèn)，該元素才在隊(duì)列中。

使用場(chǎng)景

相關(guān)使用場(chǎng)景就是定時(shí)緩存。

HashMap和DelayQueue配合使用。用DelayQueue來(lái)存儲(chǔ)緩存的key，如果隊(duì)列中有元素，表示該key就已經(jīng)過(guò)期。

然后再建一個(gè)線程去清理緩存，執(zhí)行到poll方法時(shí)，使用不傳時(shí)間的方法，如果隊(duì)列為空，該線程就一直阻塞在這，不往下走。

隊(duì)列中有元素時(shí)，就說(shuō)明有key過(guò)期了，線程繼續(xù)執(zhí)行，然后元素出隊(duì)，根據(jù)相應(yīng)的key移除緩存。

細(xì)節(jié)

延時(shí)隊(duì)列中存儲(chǔ)的元素需要實(shí)現(xiàn)Delayed接口。

public interface Delayed extends Comparable {
    long getDelay(TimeUnit unit);
}

getDelay方法返回剩余的延時(shí)時(shí)間，如果返回值大于0，表示還未到入隊(duì)時(shí)間。

SynchronousQueue：同步隊(duì)列。

最好的解釋自然是官方文檔：A BlockingQueue in which each insert operation must wait for a corresponding remove operation by another thread, and vice versa.

這是一個(gè)阻塞隊(duì)列，它的特點(diǎn)是在執(zhí)行插入操作時(shí)必須等待另一個(gè)線程的移除操作。什么意思呢？

通俗的來(lái)說(shuō)就是買可樂(lè)不需要去超市了，我(消費(fèi)者)直接和廠家(生產(chǎn)者)購(gòu)買。

所以，生產(chǎn)者和消費(fèi)者同時(shí)存在時(shí)，這個(gè)交易才能執(zhí)行，兩方達(dá)成約定后，生產(chǎn)者生產(chǎn)可樂(lè)，賣給消費(fèi)者。缺少任何一方另一方都會(huì)被阻塞，條件滿足時(shí)會(huì)喚醒對(duì)方繼續(xù)執(zhí)行，這就是所謂的同步。

代碼層面講就是：put和take方法都被調(diào)用的時(shí)候，兩者才開始執(zhí)行，并完成了數(shù)據(jù)的傳遞。

所以嚴(yán)格來(lái)說(shuō)，雖然SynchronousQueue實(shí)現(xiàn)了隊(duì)列接口，但是它的目的卻并不是隊(duì)列，而是將生產(chǎn)者消費(fèi)者線程配對(duì)。

LinkedTransferQueue：鏈?zhǔn)睫D(zhuǎn)移隊(duì)列。雖然放在了最后，但是查閱相關(guān)文檔發(fā)現(xiàn)，實(shí)際的生產(chǎn)環(huán)境中，這個(gè)隊(duì)列最常用。

怎么轉(zhuǎn)移的呢？

消費(fèi)者找隊(duì)列拿數(shù)據(jù)，如果沒(méi)有數(shù)據(jù)可用，就設(shè)置一個(gè)標(biāo)志位，表示我這里期待著一個(gè)數(shù)據(jù)，然后消費(fèi)者就開始等。

等著等著，直到生產(chǎn)者來(lái)了，判斷，如果有等著的，就直接把數(shù)據(jù)給它，實(shí)現(xiàn)了數(shù)據(jù)轉(zhuǎn)移。如果沒(méi)有呢？就去執(zhí)行數(shù)據(jù)入隊(duì)相關(guān)的操作。

點(diǎn)開了阻塞隊(duì)列的源碼，發(fā)現(xiàn)線程安全是使用鎖實(shí)現(xiàn)的。

再看看面試問(wèn)的東西：樂(lè)觀鎖、悲觀鎖、自旋鎖、偏向鎖、公平鎖，這都是寫啥東西呀？

吾生也有涯，而Java無(wú)涯。