1.3 隊(duì)列

隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)（First-In-First-Out，F(xiàn)IFO），就像大家排隊(duì)買票一樣，先來(lái)的先買，沒(méi)有特殊窗口，也沒(méi)有VIP通道，所有人都一樣。隊(duì)列通常使用鏈表和數(shù)組來(lái)實(shí)現(xiàn)，并且隊(duì)列只允許在尾部（tail）進(jìn)行插入操作，在頭部（head）進(jìn)行刪除操作，如圖1-14所示。

1. 隊(duì)列的實(shí)現(xiàn)方式

隊(duì)列常見有兩種實(shí)現(xiàn)方式，一種是使用鏈表，另一種是使用數(shù)組。使用單向鏈表實(shí)現(xiàn)隊(duì)列不會(huì)出現(xiàn)溢出的問(wèn)題，隊(duì)列長(zhǎng)度也沒(méi)有限制，但刪除的時(shí)間復(fù)雜度較高，當(dāng)然也可以使用雙向鏈表。使用兩個(gè)指針，一個(gè)指向隊(duì)列的頭，一個(gè)指向隊(duì)列的尾，刪除的時(shí)候只能刪除頭（head），添加的時(shí)候只能在尾部（tail）添加，如圖1-15所示。

2. 隊(duì)列的鏈表實(shí)現(xiàn)

先來(lái)看一下隊(duì)列的鏈表實(shí)現(xiàn)，其實(shí)它和我們前面講的雙向鏈表一樣，唯一的區(qū)別就是不能在隊(duì)列的中間進(jìn)行添加和刪除操作，并且在隊(duì)列的兩頭只能一個(gè)添加一個(gè)刪除。先來(lái)看一下隊(duì)列的節(jié)點(diǎn)類。

來(lái)看一下使用鏈表實(shí)現(xiàn)隊(duì)列的完整代碼。

3. 隊(duì)列的數(shù)組實(shí)現(xiàn)

除了使用鏈表實(shí)現(xiàn)隊(duì)列以外，還可以使用數(shù)組來(lái)實(shí)現(xiàn)。使用鏈表是沒(méi)有長(zhǎng)度限制的，但使用數(shù)組需要給一個(gè)固定的大小，如果隊(duì)列滿了還會(huì)涉及隊(duì)列的擴(kuò)容，這里讓tail指向下一個(gè)可以存放數(shù)據(jù)的位置，如圖1-16所示。

使用數(shù)組實(shí)現(xiàn)隊(duì)列的時(shí)候有一個(gè)很明顯的缺點(diǎn)就是數(shù)組不能被重復(fù)使用。如圖1-16所示，如果一個(gè)元素不停地加入隊(duì)列，然后不停地從隊(duì)列中移除，會(huì)導(dǎo)致tail和head越來(lái)越大，最后隊(duì)列中無(wú)法再加入數(shù)據(jù)了，實(shí)際上由于刪除之后，隊(duì)列前面部分有些是空的，這就造成了空間的極大浪費(fèi)。

4. 循環(huán)隊(duì)列

使用數(shù)組實(shí)現(xiàn)隊(duì)列的時(shí)候可能會(huì)造成空間的浪費(fèi)，那么有沒(méi)有什么方式可以優(yōu)化呢？實(shí)際上是有的。它就是循環(huán)隊(duì)列，我們只需要把數(shù)組看作一個(gè)首尾相連的環(huán)即可。在循環(huán)隊(duì)列中，當(dāng)存儲(chǔ)空間的最后一個(gè)位置已被使用，在往隊(duì)列添加數(shù)據(jù)時(shí)，只需要找到存儲(chǔ)空間的第一個(gè)空閑位置，然后將數(shù)據(jù)添加進(jìn)去，讓它的下一個(gè)位置作為隊(duì)尾，如圖1-17所示。

5. 優(yōu)先隊(duì)列和雙端隊(duì)列

除了上面介紹的隊(duì)列以外，大家可能還聽說(shuō)過(guò)優(yōu)先隊(duì)列、雙端隊(duì)列，其實(shí)這兩個(gè)都不屬于隊(duì)列，雖然它們的名字中含有隊(duì)列，但它們不具有隊(duì)列的特性——先進(jìn)先出。優(yōu)先隊(duì)列中的每個(gè)元素都有各自的優(yōu)先級(jí)，優(yōu)先級(jí)最高的元素最先得到服務(wù)；優(yōu)先隊(duì)列一般使用堆來(lái)實(shí)現(xiàn)，這個(gè)會(huì)在1.7節(jié)堆講到。而雙端隊(duì)列和這里講的隊(duì)列類似，只不過(guò)雙端隊(duì)列兩頭都可以進(jìn)行元素的添加和刪除，它是一種同時(shí)具有隊(duì)列和棧的性質(zhì)的數(shù)據(jù)結(jié)構(gòu)，如圖1-18所示。