0x00 基本概念

和棧一樣览祖，隊(duì)列也是一種受操作限制的線性表孝鹊，和棧相反的是隊(duì)列是先進(jìn)先出，最基本的操作也是兩個(gè)展蒂，入隊(duì)和出隊(duì)又活。

隊(duì)列應(yīng)用非常廣泛，特別是一些具有額外特性的隊(duì)列锰悼，比如：循環(huán)隊(duì)列柳骄、阻塞隊(duì)列、并發(fā)隊(duì)列等箕般。
高性能隊(duì)列Disruptor耐薯、linux環(huán)形緩存都用到了循環(huán)并發(fā)隊(duì)列，java concurrent并發(fā)包利用ArrayBlockingQueue來(lái)實(shí)現(xiàn)公平鎖

0x01 順序隊(duì)列&鏈?zhǔn)疥?duì)列&循環(huán)隊(duì)列

和棧一樣丝里，隊(duì)列也可以使用數(shù)組或鏈表來(lái)實(shí)現(xiàn)可柿，數(shù)組實(shí)現(xiàn)的隊(duì)列叫順序隊(duì)列，鏈表實(shí)現(xiàn)的叫鏈?zhǔn)疥?duì)列

• 順序隊(duì)列

由于數(shù)組長(zhǎng)度不能修改丙者，所以順序隊(duì)列大小也要提前給出，隊(duì)列需要維護(hù)兩個(gè)指針营密，分別指向隊(duì)首和隊(duì)尾械媒，當(dāng)隊(duì)尾到達(dá)數(shù)組最后時(shí)，隊(duì)首由于出隊(duì)操作可能不在數(shù)組頭部，這時(shí)數(shù)組前面有部分空間是沒(méi)有使用的纷捞，這時(shí)需要把所有數(shù)據(jù)前移痢虹，這一步可以放在每次入隊(duì)的時(shí)候判斷，集中搬遷

隊(duì)空判斷：head==tail
隊(duì)滿判斷：tail==n && head==0

GitHub

• 鏈?zhǔn)疥?duì)列

鏈?zhǔn)疥?duì)列使用鏈表實(shí)現(xiàn)主儡，也是兩個(gè)指針head奖唯、tail分別指向隊(duì)首和隊(duì)尾，出隊(duì)時(shí)返回head指向的元素糜值，然后將head指向head的next丰捷，入隊(duì)時(shí)，將元素插入tail的next寂汇，然后將tail指向next病往，注意隊(duì)列為空時(shí)的判斷，還有當(dāng)只剩最后一個(gè)元素時(shí)骄瓣，出隊(duì)停巷，此時(shí)head指向null，要注意修改tail的指向

隊(duì)空判斷：head==null
隊(duì)滿判斷：不用判斷榕栏，注意一下tail==null的情況就行了

GitHub

• 循環(huán)隊(duì)列

循環(huán)隊(duì)列看起來(lái)像一個(gè)環(huán)畔勤，沒(méi)有首尾，和數(shù)組比扒磁，沒(méi)有了首尾庆揪，這樣我們可以避免數(shù)據(jù)的搬遷工作，循環(huán)隊(duì)列的實(shí)現(xiàn)渗磅，最關(guān)鍵的是隊(duì)空和隊(duì)滿時(shí)的判斷嚷硫，以數(shù)組實(shí)現(xiàn)為例：假設(shè)數(shù)組長(zhǎng)度n、隊(duì)首指針head（指向?qū)⒁鲫?duì)的位置）始鱼、隊(duì)尾指針tail（指向?qū)⒁腙?duì)的位置）

順序隊(duì)列中仔掸，tail也是指向?qū)⒁腙?duì)的位置，當(dāng)隊(duì)列滿時(shí)tail索引為n医清，且head索引為0起暮，當(dāng)隊(duì)列空時(shí)head和tail索引相等。

在循環(huán)隊(duì)列中会烙，為空時(shí)负懦，head和tail相等，隊(duì)列滿時(shí)柏腻，tail的下一個(gè)是head纸厉，為了與隊(duì)空時(shí)區(qū)分，這里會(huì)浪費(fèi)一個(gè)位置五嫂。所以當(dāng)tail下一個(gè)位置為head時(shí)颗品，就不在入隊(duì)肯尺，

隊(duì)空判斷：隊(duì)首指針和隊(duì)尾指針相等 head==tail
隊(duì)滿判斷：tail的下一個(gè)位置是head，數(shù)組索引時(shí)0～n-1躯枢，所以tail+1==head则吟，還有一種特殊情況，tail=n-1,head=0锄蹂，所以結(jié)合起來(lái)得到 (tail+1)%n == head

GitHub

0x02 課后思考

1氓仲、除了線程池這種池結(jié)構(gòu)會(huì)用到隊(duì)列排隊(duì)請(qǐng)求，你還知道有哪些類似的池結(jié)構(gòu)或者場(chǎng)景中會(huì)用到隊(duì)列的排隊(duì)請(qǐng)求呢得糜？

實(shí)際上敬扛，對(duì)于大部分資源有限的場(chǎng)景，當(dāng)沒(méi)有空閑資源時(shí)掀亩，基本上都可以通過(guò)隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)舔哪，還有分布式消息隊(duì)列，例如kafka也是一種隊(duì)列

2槽棍、今天講到并發(fā)隊(duì)列捉蚤，關(guān)于如何實(shí)現(xiàn)無(wú)鎖并發(fā)隊(duì)列，網(wǎng)上有非常多的討論炼七。對(duì)這個(gè)問(wèn)題缆巧，你怎么看呢？

無(wú)鎖隊(duì)列可以使用cas（Compare and Swap）原子操作來(lái)實(shí)現(xiàn)豌拙，入隊(duì)前獲取tail位置陕悬，入隊(duì)時(shí)比較tail是否變化，如果沒(méi)變按傅，則允許入隊(duì)捉超，反之入隊(duì)失敗，出隊(duì)則是獲取head位置唯绍，進(jìn)行cas