作者 |? 小鹿

來源 |? 小鹿動畫學(xué)編程

寫在前邊

像線程池、異步隊列、消息隊列等有限的資源容器中，往往存儲大量的任務(wù)事件，這些大量的任務(wù)事件需要進(jìn)行有條理的進(jìn)行任務(wù)分發(fā)以及各種情況處理，為了能夠使得資源容器的正常運行，不得不使用一定的容器結(jié)構(gòu)設(shè)計和策略，那么這些結(jié)構(gòu)和策略如何實現(xiàn)的呢？

那小鹿不買官司了，就是用我們今天即將學(xué)到的數(shù)據(jù)結(jié)構(gòu)“隊列”。雖然我們初學(xué)者實際中接觸的少，但是它的實際用途廣著呢，學(xué)好這部分是非常關(guān)鍵的。

思維導(dǎo)圖

1

什么是隊列？

何為隊列？顧名思義，排隊就是一個很好的例子。如果我們餐廳刷卡買飯，學(xué)生依次排隊，已購買完飯的在隊頭走了，剛來的同學(xué)就要排在隊尾后邊排隊。而不能直接在排好隊中插隊，這樣也壞了排隊這種“先來先去”規(guī)矩。

2

隊列的特點？

棧有出棧和入棧兩種，隊列也有入隊和出隊兩種操作，只不過是棧是先來后走，隊列則相反，先來先走。

正是因為隊列這種特點，使得它在一些有限的資源容器中的到廣泛的應(yīng)用，比如線程池、資源池、消息隊列等。

3

如何實現(xiàn)隊列？

隊列和棧一樣，也有兩種實現(xiàn)方式，一種是順序隊列，一種是鏈?zhǔn)疥犃小５俏覀冎暗奈恼轮姓f過，無論是順序還是鏈?zhǔn)?#xff0c;都是由數(shù)組和鏈表演化而來，只不過是操作上進(jìn)行了改進(jìn)。

1、順序隊列

對于上邊的數(shù)組順序隊列，不知道大家有沒有發(fā)現(xiàn)一個問題就是，如果我一直的出隊、入隊會出現(xiàn)下邊這樣一種情況。

此時隊列再入隊，但是隊尾已滿，但是我們看到的明明隊頭還有空間的，如果此時擴大容量不就相當(dāng)于浪費空間嗎？

那還有一個方法就是，每入隊一個元素，整體數(shù)據(jù)就往前移動一個空間，你可能會說，這樣操作起來是不是很費勁，而且效率不高，是的，這樣的確效率不高。

如果我們稍微改進(jìn)一下，如果隊尾有空間，我們就讓元素一直入隊，直到隊尾沒有空間位置，然后進(jìn)行整體進(jìn)行一次搬移，這樣優(yōu)化了入隊的效率。將這一次性進(jìn)行大量搬移數(shù)據(jù)平均到每次上，平均時間復(fù)雜度還是 O(1)。

2、鏈?zhǔn)疥犃?/strong>

鏈?zhǔn)疥犃惺且枣湵斫M成的，它的優(yōu)點就是可以無限的進(jìn)行入隊，不用動態(tài)擴容。

4

隊列的種類？

4.1 循環(huán)隊列

循環(huán)隊列，顧名思義，將一般的隊列進(jìn)行頭尾相接，形成一個圓，聲明兩個指針，一個帶邊隊頭，一個代表隊尾，入隊和出隊的時候，直接操作對應(yīng)的指針即可。

但是為什么會出現(xiàn)循環(huán)隊列呢？是否還記得我們上邊所述，普通的隊列需要進(jìn)行大量數(shù)據(jù)搬移，而循環(huán)隊列則沒有這個缺點。

但是循環(huán)隊列有一個比較重要的點就是判空和判斷是否已滿。

如上圖所示，判空的條件很簡單，頭指針等于尾指針的時候，此時循環(huán)隊列為空。

循環(huán)隊列滿的時候，我們要發(fā)現(xiàn)其上邊的規(guī)律得出隊滿的條件，(尾指針 + 1)% n = 頭指針。此時的循環(huán)隊列會浪費一個空間。

上邊我們涉及到的隊列是從結(jié)構(gòu)上進(jìn)行來區(qū)分的，下面我們就從實際開發(fā)功能上進(jìn)行劃分。其實就是對一些功能的需求對隊列操作上設(shè)定了一定的要求。

4.2 阻塞隊列

我們拿一個例子入手，如果你學(xué)習(xí)過Android開發(fā)，里邊有個MessageQueue消息隊列。如果沒有接觸過，也沒關(guān)系，可以將其理解為放置消息的一個容器。

這個容器主要存放系統(tǒng)給它分發(fā)的任務(wù)消息，然后當(dāng)有線程來分配任務(wù)的時候，此時該容器，也就是消息隊列就會在隊列中拿出任務(wù)然后分發(fā)給線程去執(zhí)行。但是有這樣兩種情況需要進(jìn)行設(shè)計。

第一種情況就是當(dāng)任務(wù)消息隊列沒有任務(wù)的時候，此時線程來拿任務(wù)，該怎么辦？

第二種情況就是，當(dāng)沒有空閑線程來取任務(wù)，此時任務(wù)消息隊列已經(jīng)滿了，系統(tǒng)再分發(fā)新的任務(wù)時，又該如何處理呢？

那我相對于這兩種情況，就用到我們的阻塞隊列。當(dāng)遇到第一種情況時，此時消息隊列為空，在隊頭拿數(shù)據(jù)的時候會被阻塞，也就是被阻止了，因為隊列中為空，只有等到隊列中有新的數(shù)據(jù)時，線程才可以拿去新的任務(wù)。

當(dāng)遇到第二種情況，如果隊列已經(jīng)滿了，此時沒有空余線程來取任務(wù)，此時隊列也被阻塞了，當(dāng)有空余線程來獲取任務(wù)的時候，任務(wù)隊列才可取數(shù)據(jù)。

其實上邊的設(shè)計思路和我們所涉及到的設(shè)計模式中的 “發(fā)布-訂閱者模式”相同。

生產(chǎn)者代表往消息隊列中增加數(shù)據(jù)，消費者代表線程不斷的拿去任務(wù)去執(zhí)行，我們可以通過調(diào)節(jié)生產(chǎn)著和消費者的數(shù)量來調(diào)節(jié)隊列匯總的任務(wù)數(shù)量，從而達(dá)到高效的系統(tǒng)運行。

4.3 并發(fā)隊列

上邊我們涉及到的阻塞隊列會有很多的消費者(線程)去操作隊列。我們舉個具體點的例子，還是拿排隊打飯的例子，如果一個窗口沒有排序秩序，100 多個人都往窗口買飯，如果你作為賣飯的，想象一下會出現(xiàn)什么情況呢？

學(xué)生爭來爭去到底先給哪一個盛飯呢？一旦人一多，可能整個餐廳窗口擠爆，會出現(xiàn)打架的情況。

話說回來，在系統(tǒng)中也可能出現(xiàn)這種情況的，那我們怎么對付這種情況呢？此時的隊列不再叫做阻塞隊列，叫做并發(fā)隊列。

我們只需要設(shè)置一個鎖機制，當(dāng)有一個消費者來取任務(wù)的時候，我們此時加一個鎖，說明其他的消費者不能進(jìn)行操作了，當(dāng)這個消費者讀取完任務(wù)時，在解鎖，依次類推，這樣保證了系統(tǒng)的正常運行。

總結(jié)

最后我們來總結(jié)一下隊列的應(yīng)用，像我們開篇所說，隊列一般應(yīng)用在有限的資源場景中，比如消息隊列、異步隊列、CPU 的線程執(zhí)行隊列等。對于這些應(yīng)用場景，都是利用了隊列先來先去的服務(wù)調(diào)度方式，從而能夠準(zhǔn)確的對資源進(jìn)行把控。

隊列在實際應(yīng)用中也分為兩種，一種是基于數(shù)組的順序隊列，另一種是基于鏈表的鏈?zhǔn)疥犃小Ｋ鼈儍烧吒饔袃?yōu)缺點，所謂的優(yōu)缺點也是由數(shù)組和兩邊本身的優(yōu)缺點演化而來。

數(shù)組大小固定，如果有過多的請求，就會導(dǎo)致長時間排隊等候，請求響應(yīng)時間過長。而鏈?zhǔn)疥犃须m然可以動態(tài)的添加任務(wù)，但是如果過于太長，在實際應(yīng)用中也是不允許的。

對于如何在實際應(yīng)用中設(shè)計一個合適的隊列，需要根于已有的資源容量以及需求，還有系統(tǒng)的響應(yīng)時間要求進(jìn)行設(shè)計。如果隊列太長，會導(dǎo)致等待請求過多，隊列太小，就無法充分利用系統(tǒng)的資源。

基礎(chǔ)知識

基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)：【動畫】如何輕松手寫鏈表？

三分鐘基礎(chǔ)知識：什么是棧？

三分鐘基礎(chǔ)知識：互斥那點事兒(上)

三分鐘基礎(chǔ)知識：互斥那點事兒(下)

三分鐘基礎(chǔ)知識：用動畫給面試官解釋 TCP 三次握手過程

三分鐘基礎(chǔ)知識：用動畫給女朋友講解 TCP 四次分手過程