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

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

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

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

List、Set和Map我們用的都是已經(jīng)相當熟練了，今天，我們就來學習這個隊列Queue！

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

Queue接口中聲明了六個方法，分成三對來使用。

入隊操作

出隊操作

取隊頭操作

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

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

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

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

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

Deque：double-ended queue，雙端隊列。

雙端隊列，相比普通隊列就是可操作兩端，有兩個隊頭，也有兩個隊尾。

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

所以說，如果使用雙端隊列，不僅可以當隊列用，也可以當棧用，因為可以自己控制出的是隊頭還是隊尾。

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

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

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

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

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

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

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

舉一個符合實際的例子，我想喝可樂。

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

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

我就是消費者，去超市買可樂(消費過程)。

所以就會有一個同步的問題：

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

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

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

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

線程類比

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

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

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

阻塞隊列正適合生產(chǎn)者消費者模型，當隊列滿時，入隊操作就會被阻塞，當隊列空時，出隊操作就會被阻塞。

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

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

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

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

PriorityBlockingQueue：優(yōu)先級阻塞隊列。

這個簡單，就是同時實現(xiàn)了BlockingQueue和Deque接口。

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

延時隊列：DelayQueue，看這個類名，無疑了，此隊列定與時間有關(guān)。

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

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

在延時之后，也就是10s之后，再去訪問，該元素才在隊列中。

使用場景

相關(guān)使用場景就是定時緩存。

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

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

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

細節(jié)

延時隊列中存儲的元素需要實現(xiàn)Delayed接口。

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

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

SynchronousQueue：同步隊列。

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

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

通俗的來說就是買可樂不需要去超市了，我(消費者)直接和廠家(生產(chǎn)者)購買。

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

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

所以嚴格來說，雖然SynchronousQueue實現(xiàn)了隊列接口，但是它的目的卻并不是隊列，而是將生產(chǎn)者消費者線程配對。

LinkedTransferQueue：鏈式轉(zhuǎn)移隊列。雖然放在了最后，但是查閱相關(guān)文檔發(fā)現(xiàn)，實際的生產(chǎn)環(huán)境中，這個隊列最常用。

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

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

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

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

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

吾生也有涯，而Java無涯。