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