一、什么是隊列？

1.先進(jìn)先出，后進(jìn)后出，這就是典型的“隊列”結(jié)構(gòu)。

2.支持兩個操作：入隊enqueue()，放一個數(shù)據(jù)到隊尾；出隊dequeue()，從隊頭取一個元素。

3.所以，和棧一樣，隊列也是一種操作受限的線性表。

二、隊列有哪些常見的應(yīng)用？

1.阻塞隊列

1）在隊列的基礎(chǔ)上增加阻塞操作，就成了阻塞隊列。

2）阻塞隊列就是在隊列為空的時候，從隊頭取數(shù)據(jù)會被阻塞，因為此時還沒有數(shù)據(jù)可取，直到隊列中有了數(shù)據(jù)才能返回；如果隊列已經(jīng)滿了，那么插入數(shù)據(jù)的操作就會被阻塞，直到隊列中有空閑位置后再插入數(shù)據(jù)，然后在返回。

3）從上面的定義可以看出這就是一個“生產(chǎn)者-消費者模型”。這種基于阻塞隊列實現(xiàn)的“生產(chǎn)者-消費者模型”可以有效地協(xié)調(diào)生產(chǎn)和消費的速度。當(dāng)“生產(chǎn)者”生產(chǎn)數(shù)據(jù)的速度過快，“消費者”來不及消費時，存儲數(shù)據(jù)的隊列很快就會滿了，這時生產(chǎn)者就阻塞等待，直到“消費者”消費了數(shù)據(jù)，“生產(chǎn)者”才會被喚醒繼續(xù)生產(chǎn)。不僅如此，基于阻塞隊列，我們還可以通過協(xié)調(diào)“生產(chǎn)者”和“消費者”的個數(shù)，來提高數(shù)據(jù)處理效率，比如配置幾個消費者，來應(yīng)對一個生產(chǎn)者。

2.并發(fā)隊列

1）在多線程的情況下，會有多個線程同時操作隊列，這時就會存在線程安全問題。能夠有效解決線程安全問題的隊列就稱為并發(fā)隊列。

2）并發(fā)隊列簡單的實現(xiàn)就是在enqueue()、dequeue()方法上加鎖，但是鎖粒度大并發(fā)度會比較低，同一時刻僅允許一個存或取操作。

3）實際上，基于數(shù)組的循環(huán)隊列利用CAS原子操作，可以實現(xiàn)非常高效的并發(fā)隊列。這也是循環(huán)隊列比鏈?zhǔn)疥犃袘?yīng)用更加廣泛的原因。

3.線程池資源枯竭是的處理

在資源有限的場景，當(dāng)沒有空閑資源時，基本上都可以通過“隊列”這種數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)請求排隊

3、循環(huán)隊列

1、循環(huán)隊列，原本數(shù)組是有頭有尾的，是一條直線。把首尾相連，扳成了一個環(huán)。

2、在數(shù)組實現(xiàn)隊列的時候，會有數(shù)據(jù)搬移操作，要想解決數(shù)據(jù)搬移的問題，需要像環(huán)一樣的循環(huán)隊列。

3、要想寫出沒有 bug 的循環(huán)隊列的實現(xiàn)代碼，最關(guān)鍵的是，確定好隊空和隊滿的判定條件。

1）隊列為空的判斷條件仍然是 head == tail。

2）當(dāng)隊滿時，(tail+1)%n=head。 tail 指向的位置實際上是沒有存儲數(shù)據(jù)的。所以，循環(huán)隊列會浪費一個數(shù)組的存儲空間。