順序隊(duì)列詳解（C語言實(shí)現(xiàn)）
順序隊(duì)列指的是用順序表模擬實(shí)現(xiàn)的隊(duì)列存儲(chǔ)結(jié)構(gòu)。
我們知道，隊(duì)列具有以下兩個(gè)特點(diǎn)：
數(shù)據(jù)從隊(duì)列的一端進(jìn)，從另一端出；
數(shù)據(jù)的入隊(duì)和出隊(duì)遵循"先進(jìn)先出"的原則；
在順序表的基礎(chǔ)上，只要元素進(jìn)出的過程遵循以上兩個(gè)規(guī)則，就能實(shí)現(xiàn)隊(duì)列結(jié)構(gòu)。
順序隊(duì)列的具體實(shí)現(xiàn)
通常情況下，我們采用 C 語言中的數(shù)組實(shí)現(xiàn)順序表。既然用順序表模擬實(shí)現(xiàn)隊(duì)列，必然要先定義一個(gè)足夠大的數(shù)組。不僅如此，為了遵守隊(duì)列中數(shù)據(jù)從 "隊(duì)尾進(jìn)，隊(duì)頭出" 且 "先進(jìn)先出" 的規(guī)則，還需要定義兩個(gè)變量（top 和 rear）分別記錄隊(duì)頭和隊(duì)尾的具體位置，如圖?1 所示：
初始狀態(tài)下，順序隊(duì)列中沒有任何元素，因此 top 和 rear 重合，都位于 a[0] 處。
實(shí)現(xiàn)入隊(duì)
在圖 1 的基礎(chǔ)上，當(dāng)有新元素入隊(duì)時(shí)，依次執(zhí)行以下兩步操作：
將新元素存儲(chǔ)在 rear 記錄的位置；
更新 rear 的值（rear+1），記錄下一個(gè)空閑空間的位置，為下一個(gè)新元素入隊(duì)做好準(zhǔn)備。
例如，在圖 1 基礎(chǔ)上將?{1,2,3,4}?用順序隊(duì)列存儲(chǔ)的實(shí)現(xiàn)操作如圖 2 所示：
入隊(duì)操作的 C 語言實(shí)現(xiàn)代碼如下：
實(shí)現(xiàn)出隊(duì)
當(dāng)有元素出隊(duì)時(shí)，根據(jù)“先進(jìn)先出”的原則，目標(biāo)元素以及在它之前入隊(duì)的元素要依次從隊(duì)頭出隊(duì)。
出隊(duì)操作的實(shí)現(xiàn)方法很簡單，就是更新 top 的值（top+1）。例如，在圖 2 基礎(chǔ)上，順序隊(duì)列中元素逐個(gè)隊(duì)列的過程如圖 3 所示：
注意，雖然數(shù)組中仍保存著 1、2、3、4 這些元素，但隊(duì)列中的元素是依靠 top 和 rear 來判別的，因此圖 3b) 顯示的隊(duì)列中確實(shí)不存在任何元素。
出隊(duì)操作的 C 語言實(shí)現(xiàn)代碼為：
順序隊(duì)列的完整實(shí)現(xiàn)代碼
使用順序表模擬實(shí)現(xiàn)順序隊(duì)列的 C 語言代碼為：
程序輸出結(jié)果：
出隊(duì)元素：1
出隊(duì)元素：2
出隊(duì)元素：3
出隊(duì)元素：4
隊(duì)列已空，出隊(duì)執(zhí)行失敗
順序隊(duì)列的缺陷
圖 2b) 是所有數(shù)據(jù)入隊(duì)成功的示意圖，圖 3b) 是所有數(shù)據(jù)出隊(duì)后的示意圖，對(duì)比兩張圖會(huì)發(fā)現(xiàn)，top 和 rear 重合位置變成了? a[4] 而不再是 a[0]。
也就是說，在元素不斷入隊(duì)、出隊(duì)的過程中，順序隊(duì)列會(huì)整體向順序表的尾部移動(dòng)。整個(gè)實(shí)現(xiàn)方案存在的缺陷是：
順序隊(duì)列前面的空閑空間無法再被使用，會(huì)造成空間浪費(fèi)；
當(dāng)順序隊(duì)列移動(dòng)至順序表尾部時(shí)，即便順序表中有空閑空間，新元素也無法成功入隊(duì)，我們習(xí)慣將這種現(xiàn)象稱為“假溢出”。
下篇文章，我會(huì)教大家順序隊(duì)列的另一種實(shí)現(xiàn)方案，可以徹底彌補(bǔ)以上兩個(gè)缺陷。
