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ù)組前面有部分空間是沒有使用的，這時(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)，沒有首尾，和數(shù)組比，沒有了首尾，這樣我們可以避免數(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)沒有空閑資源時(shí)，基本上都可以通過隊(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ú)鎖隊(duì)列可以使用cas（Compare and Swap）原子操作來(lái)實(shí)現(xiàn)，入隊(duì)前獲取tail位置，入隊(duì)時(shí)比較tail是否變化，如果沒變，則允許入隊(duì)，反之入隊(duì)失敗，出隊(duì)則是獲取head位置，進(jìn)行cas