我們知道隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)的物理實(shí)現(xiàn)方式主要還是兩種，一種是鏈隊(duì)列（自定義節(jié)點(diǎn)類），另一種則是使用數(shù)組實(shí)現(xiàn)，兩者各有優(yōu)勢(shì)。此處我們將要介紹的循環(huán)隊(duì)列其實(shí)是隊(duì)列的一種具體實(shí)現(xiàn)，由于一般的數(shù)組實(shí)現(xiàn)的隊(duì)列結(jié)構(gòu)在頻繁出隊(duì)的情況下，會(huì)產(chǎn)生假溢出現(xiàn)象，導(dǎo)致數(shù)組使用效率降低，所以引入循環(huán)隊(duì)列這種結(jié)構(gòu)。本文將從以下兩個(gè)大角度介紹循環(huán)隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)：
循環(huán)數(shù)組實(shí)現(xiàn)循環(huán)隊(duì)列
Java中具體實(shí)現(xiàn)容器類ArrayDeque
一、循環(huán)隊(duì)列
為了深刻體會(huì)到循環(huán)隊(duì)列這個(gè)結(jié)構(gòu)優(yōu)于非循環(huán)隊(duì)列的地方，我們將首先介紹數(shù)組實(shí)現(xiàn)的非循環(huán)隊(duì)列結(jié)構(gòu)。隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)，無(wú)論你是用鏈表實(shí)現(xiàn)，還是用數(shù)組實(shí)現(xiàn)，它都是要有兩個(gè)指針分別指向隊(duì)頭和隊(duì)尾。在我們數(shù)組的實(shí)現(xiàn)方式中，用兩個(gè)int型變量用于記錄隊(duì)頭和隊(duì)尾的索引。
一個(gè)隊(duì)列的初始狀態(tài)，head和tail都指向初始位置（索引為0處）。head永遠(yuǎn)指向該隊(duì)列的隊(duì)頭元素，tail則指向該隊(duì)列最后一個(gè)元素的下一位置，當(dāng)有入隊(duì)操作時(shí)：
