一芦缰、什么是隊(duì)列企巢？
1.先進(jìn)先出，后進(jìn)后出让蕾，這就是典型的“隊(duì)列”結(jié)構(gòu)浪规。
2.支持兩個(gè)操作：入隊(duì)enqueue()，放一個(gè)數(shù)據(jù)到隊(duì)尾探孝；出隊(duì)dequeue()笋婿，從隊(duì)頭取一個(gè)元素。
3.所以再姑，和棧一樣萌抵，隊(duì)列也是一種操作受限的線性表找御。
二元镀、隊(duì)列有哪些常見的應(yīng)用？
1.阻塞隊(duì)列
1）在隊(duì)列的基礎(chǔ)上增加阻塞操作霎桅，就成了阻塞隊(duì)列栖疑。
2）阻塞隊(duì)列就是在隊(duì)列為空的時(shí)候，從隊(duì)頭取數(shù)據(jù)會(huì)被阻塞滔驶，因?yàn)榇藭r(shí)還沒有數(shù)據(jù)可取遇革，直到隊(duì)列中有了數(shù)據(jù)才能返回；如果隊(duì)列已經(jīng)滿了，那么插入數(shù)據(jù)的操作就會(huì)被阻塞萝快，直到隊(duì)列中有空閑位置后再插入數(shù)據(jù)锻霎，然后在返回。
3）從上面的定義可以看出這就是一個(gè)“生產(chǎn)者-消費(fèi)者模型”揪漩。這種基于阻塞隊(duì)列實(shí)現(xiàn)的“生產(chǎn)者-消費(fèi)者模型”可以有效地協(xié)調(diào)生產(chǎn)和消費(fèi)的速度旋恼。當(dāng)“生產(chǎn)者”生產(chǎn)數(shù)據(jù)的速度過快，“消費(fèi)者”來不及消費(fèi)時(shí)奄容，存儲(chǔ)數(shù)據(jù)的隊(duì)列很快就會(huì)滿了冰更，這時(shí)生產(chǎn)者就阻塞等待，直到“消費(fèi)者”消費(fèi)了數(shù)據(jù)昂勒，“生產(chǎn)者”才會(huì)被喚醒繼續(xù)生產(chǎn)蜀细。不僅如此，基于阻塞隊(duì)列戈盈，我們還可以通過協(xié)調(diào)“生產(chǎn)者”和“消費(fèi)者”的個(gè)數(shù)奠衔，來提高數(shù)據(jù)處理效率，比如配置幾個(gè)消費(fèi)者塘娶，來應(yīng)對一個(gè)生產(chǎn)者涣觉。
2.并發(fā)隊(duì)列
1）在多線程的情況下，會(huì)有多個(gè)線程同時(shí)操作隊(duì)列血柳，這時(shí)就會(huì)存在線程安全問題官册。能夠有效解決線程安全問題的隊(duì)列就稱為并發(fā)隊(duì)列。
2）并發(fā)隊(duì)列簡單的實(shí)現(xiàn)就是在enqueue()难捌、dequeue()方法上加鎖膝宁，但是鎖粒度大并發(fā)度會(huì)比較低，同一時(shí)刻僅允許一個(gè)存或取操作根吁。
3）實(shí)際上员淫，基于數(shù)組的循環(huán)隊(duì)列利用CAS原子操作，可以實(shí)現(xiàn)非常高效的并發(fā)隊(duì)列击敌。這也是循環(huán)隊(duì)列比鏈?zhǔn)疥?duì)列應(yīng)用更加廣泛的原因介返。
3.線程池資源枯竭是的處理
在資源有限的場景，當(dāng)沒有空閑資源時(shí)沃斤，基本上都可以通過“隊(duì)列”這種數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)請求排隊(duì)
3圣蝎、循環(huán)隊(duì)列
1、循環(huán)隊(duì)列衡瓶，原本數(shù)組是有頭有尾的徘公，是一條直線。把首尾相連哮针，扳成了一個(gè)環(huán)关面。
2坦袍、在數(shù)組實(shí)現(xiàn)隊(duì)列的時(shí)候，會(huì)有數(shù)據(jù)搬移操作等太，要想解決數(shù)據(jù)搬移的問題捂齐，需要像環(huán)一樣的循環(huán)隊(duì)列。
3缩抡、要想寫出沒有 bug 的循環(huán)隊(duì)列的實(shí)現(xiàn)代碼辛燥，最關(guān)鍵的是，確定好隊(duì)空和隊(duì)滿的判定條件缝其。
1）隊(duì)列為空的判斷條件仍然是 head == tail挎塌。
2）當(dāng)隊(duì)滿時(shí)，(tail+1)%n=head内边。 tail 指向的位置實(shí)際上是沒有存儲(chǔ)數(shù)據(jù)的榴都。所以，循環(huán)隊(duì)列會(huì)浪費(fèi)一個(gè)數(shù)組的存儲(chǔ)空間漠其。
