2.2 如何實(shí)現(xiàn)隊(duì)列

【出自XL面試題】

難度系數(shù)：★★★☆☆

被考察系數(shù)：★★★★☆

題目描述：

實(shí)現(xiàn)一個(gè)隊(duì)列的數(shù)據(jù)結(jié)構(gòu)，使其具有入隊(duì)列、出隊(duì)列、查看隊(duì)列首尾元素、查看隊(duì)列大小等功能。

分析與解答：

與實(shí)現(xiàn)棧的方法類似，隊(duì)列的實(shí)現(xiàn)也有兩種方法，分別為采用數(shù)組來實(shí)現(xiàn)和采用鏈表來實(shí)現(xiàn)。下面分別詳細(xì)介紹這兩種方法。

方法一：數(shù)組實(shí)現(xiàn)

下圖給出了一種最簡單的實(shí)現(xiàn)方式，用front來記錄隊(duì)列首元素的位置，用rear來記錄隊(duì)列尾元素往后一個(gè)位置。入隊(duì)列的時(shí)候只需要將待入隊(duì)列的元素放到數(shù)組下標(biāo)為rear的位置，同時(shí)執(zhí)行rear++，出隊(duì)列的時(shí)候只需要執(zhí)行front++即可。

實(shí)現(xiàn)代碼如下：

程序的運(yùn)行結(jié)果為

以上這種實(shí)現(xiàn)方法最大的缺點(diǎn)：出隊(duì)列后數(shù)組前半部分的空間不能夠充分地利用，解決這個(gè)問題的方法為把數(shù)組看成一個(gè)環(huán)狀的空間（循環(huán)隊(duì)列）。當(dāng)數(shù)組最后一個(gè)位置被占用后，可以從數(shù)組首位置開始循環(huán)利用，具體實(shí)現(xiàn)方法可以參考數(shù)據(jù)結(jié)構(gòu)的課本。

方法二：鏈表實(shí)現(xiàn)

采用鏈表實(shí)現(xiàn)隊(duì)列的方法與實(shí)現(xiàn)棧的方法類似，分別用兩個(gè)指針指向隊(duì)列的首元素與尾元素，如下圖所示。用pHead來指向隊(duì)列的首元素，用pEnd來指向隊(duì)列的尾元素。

在上圖中，剛開始隊(duì)列中只有元素1、2和3，當(dāng)新元素4要進(jìn)隊(duì)列的時(shí)候，只需要上圖中（1）和（2）兩步，就可以把新結(jié)點(diǎn)連接到鏈表的尾部，同時(shí)修改pEnd指針指向新增加的結(jié)點(diǎn)。出隊(duì)列的時(shí)候只需要（3）這一步，改變pHead指針使其指向pHead→next，此外也需要考慮結(jié)點(diǎn)所占空間釋放的問題。在入隊(duì)列與出隊(duì)列的操作中也需要考慮隊(duì)列尾空的時(shí)候的特殊操作，實(shí)現(xiàn)代碼如下：

程序的運(yùn)行結(jié)果為

顯然用鏈表來實(shí)現(xiàn)隊(duì)列有更好的靈活性，與數(shù)組的實(shí)現(xiàn)方法相比，它多了用來存儲(chǔ)結(jié)點(diǎn)關(guān)系的指針空間。此外，也可以用循環(huán)鏈表來實(shí)現(xiàn)隊(duì)列，這樣只需要一個(gè)指向鏈表最后一個(gè)元素的指針即可，因?yàn)橥ㄟ^指向鏈表尾元素可以非常容易地找到鏈表的首結(jié)點(diǎn)。