4 Queue隊(duì)列
前面幾篇担忧，我們介紹了Java集合中常用到的對(duì)象芹缔。本篇中，我們?cè)賮?lái)說(shuō)說(shuō)Queue隊(duì)列的故事瓶盛。
對(duì)于Queue最欠，或許你跟我一樣，并不會(huì)將其與集合框架聯(lián)系到一起惩猫，更多時(shí)候是將其歸屬到數(shù)據(jù)結(jié)構(gòu)中芝硬。
尤其是查找集合相關(guān)的教程時(shí)，大多都是List轧房、Set拌阴、Map，講解Queue隊(duì)列的很少出現(xiàn)奶镶。
但皮官，當(dāng)你真正去了解脯倒、看源碼時(shí)，會(huì)發(fā)現(xiàn)Queue是Collection的一個(gè)子接口捺氢，與List藻丢、Set同一級(jí)別；
題外話(huà)說(shuō)多了摄乒，到底什么是Queue悠反，讓我們來(lái)看！
1. Queue
Queue是Java集合框架中的一員馍佑，繼承于Collection接口斋否。
與List、Set相同的是拭荤，Queue也實(shí)現(xiàn)了一種數(shù)據(jù)結(jié)構(gòu)茵臭，這就是隊(duì)列（這也是Queue經(jīng)常出現(xiàn)在數(shù)據(jù)結(jié)構(gòu)相關(guān)文章中的主要原因）在跳。
所以煮岁，要想明白Queue集合，首先得知道隊(duì)列是什么尉间！
隊(duì)列是計(jì)算機(jī)中的一種數(shù)據(jù)結(jié)構(gòu)雏亚，保存在其中的數(shù)據(jù)具有“先進(jìn)先出（FIFO,First In First Out）”的特性缨硝。
如果，你不明白“先進(jìn)先出”是什么罢低，試想下排隊(duì)的場(chǎng)景查辩，最先進(jìn)來(lái)的人解決完問(wèn)題后，最早離開(kāi)---這就叫“先進(jìn)先出”网持；
當(dāng)隊(duì)伍中有新來(lái)的人時(shí)宜岛，需要排在隊(duì)伍的末端；而當(dāng)隊(duì)伍中有人解決完問(wèn)題時(shí)功舀，會(huì)從隊(duì)伍的前端離開(kāi)谬返。
在隊(duì)列中，我們管隊(duì)伍的末端叫做“隊(duì)尾”日杈，管隊(duì)伍的前端叫“隊(duì)頭”；新來(lái)的人佑刷，稱(chēng)之為“入隊(duì)”莉擒。而離開(kāi)的人，稱(chēng)之為“出隊(duì)”瘫絮；
稍有不同的是涨冀，在數(shù)據(jù)結(jié)構(gòu)中，隊(duì)列不支持從隊(duì)伍的中間插入和離開(kāi)麦萤，只能從頭尾進(jìn)行鹿鳖。而真實(shí)生活中扁眯，我們的隊(duì)伍可沒(méi)有這么和諧！３嶂摹Ｒ鎏础！
還有一點(diǎn)是涝滴，當(dāng)沒(méi)有人在排隊(duì)時(shí)绣版，我們稱(chēng)之為“空隊(duì)”，也就是隊(duì)列為空的情況歼疮。
通過(guò)介紹排隊(duì)的場(chǎng)景杂抽，讓我們對(duì)隊(duì)列有了一個(gè)初步的概念。那么韩脏，在Java中的隊(duì)列究竟如何實(shí)現(xiàn)呢缩麸？
1.1 隊(duì)列的兩種形式
在Java中，隊(duì)列分為2種形式赡矢，一種是單隊(duì)列杭朱，一種是循環(huán)隊(duì)列；
通常济竹，都是使用數(shù)組來(lái)實(shí)現(xiàn)隊(duì)列痕檬，假定數(shù)組的長(zhǎng)度為6，也就是隊(duì)列的長(zhǎng)度為6送浊；
- 來(lái)看單隊(duì)列情況：
第一步梦谜，創(chuàng)建一個(gè)空數(shù)組，有兩個(gè)變量袭景，分別為front唁桩、rear，代表著頭指針耸棒、尾指針荒澡；
第二步，向隊(duì)列中插入數(shù)據(jù)与殃；
第三步单山，移除隊(duì)頭中的數(shù)據(jù)；
第四步幅疼，再次向隊(duì)列中插數(shù)據(jù)（此時(shí)rear指針指向了一個(gè)不存在的角標(biāo)）米奸；
此時(shí)，單隊(duì)列發(fā)生了“假溢出”情況爽篷，尾指針指向了一個(gè)不存在的數(shù)組角標(biāo)悴晰。
如果，要解決該情況的發(fā)生，有兩種方式-----一铡溪，無(wú)限擴(kuò)充數(shù)組大衅；二棕硫，引入循環(huán)隊(duì)列髓涯；
- 來(lái)看循環(huán)隊(duì)列情況：
當(dāng)尾指針超過(guò)了數(shù)組角標(biāo)大小，此時(shí)我們會(huì)判斷隊(duì)列的頭部是否有剩余的空間饲帅，如果有就把尾指針指向隊(duì)列的頭部复凳；
此時(shí)，循環(huán)隊(duì)列就產(chǎn)生了灶泵。
其實(shí)育八，循環(huán)隊(duì)列就是將單隊(duì)列的首位進(jìn)行相連，形成了一個(gè)圓圈赦邻，這樣就不會(huì)發(fā)生角標(biāo)越界的情況了（distruptor實(shí)現(xiàn)）髓棋；
