順序棧指的是用順序表實現(xiàn)的棧存儲結(jié)構(gòu)，通過前面的學(xué)習(xí)我們知道，棧存儲結(jié)構(gòu)存取數(shù)據(jù)元素必須遵守 "先進(jìn)后出" 的原則。本節(jié)就給大家詳細(xì)講解如何使用順序表模擬棧結(jié)構(gòu)，以及實現(xiàn)元素的入棧和出棧操作。

順序表和棧存儲數(shù)據(jù)的方式高度相似，只不過棧對數(shù)據(jù)的存取過程有特殊的限制，而順序表沒有。例如，我們使用順序表（用 a?數(shù)組表示）存儲?{1,2,3,4}，存儲狀態(tài)如圖?1 所示：

使用棧存儲結(jié)構(gòu)存儲?{1,2,3,4}，存儲狀態(tài)如圖 2 所示：

對比圖 1 和圖 2 不難看出，用順序表模擬棧結(jié)構(gòu)很簡單，只要將數(shù)據(jù)從數(shù)組下標(biāo)為 0 的位置依次存儲即可。

從數(shù)組下標(biāo)為 0 的模擬棧存儲數(shù)據(jù)是常用的方法，從其他數(shù)組下標(biāo)處存儲數(shù)據(jù)也完全可以，這里只是為了方便初學(xué)者理解。

了解了順序表模擬實現(xiàn)棧存儲結(jié)構(gòu)之后，接下來學(xué)習(xí)如何實現(xiàn)元素入棧和出棧的操作。

棧中存取元素，必須遵循“先進(jìn)后出”的原則，因此若想將圖 1 中存儲的元素 1 從棧中取出，需依次先將元素 4、元素 3 和元素 2 從棧中取出，最后才能取出元素 1。

這里給出一種順序表模擬入棧和出棧的實現(xiàn)思路：定義一個實時記錄棧頂位置的變量（假設(shè)命名為 top），初始狀態(tài)下棧內(nèi)無任何元素，整個棧是"空棧"，top 的值為 -1。一旦有數(shù)據(jù)元素進(jìn)棧，則 top 就做 +1 操作；反之，如果數(shù)據(jù)元素出棧，top 就做 -1 操作。

順序棧元素"入棧"

比如，還是模擬棧存儲?{1,2,3,4}?的過程。最初棧是"空棧"，top 的值為 -1，如圖 3 所示：

將元素 1 入棧，默認(rèn)數(shù)組下標(biāo)為 0 一端表示棧底，元素 1 存儲在數(shù)組 a[0] 處，同時 top 值 +1，如圖 4 所示：

采用同樣的方式，依次將元素 2、3 和 4 入棧，最終 top 的值變成 3，如圖 5 所示：

因此，C 語言實現(xiàn)代碼為：

代碼中的 a[++top]=elem，等價于先執(zhí)行 ++top，再執(zhí)行 a[top]=elem。

順序棧元素"出棧"

實際上，top 變量的設(shè)置對模擬數(shù)據(jù)的 "入棧" 操作沒有幫助，它是為實現(xiàn)數(shù)據(jù)的 "出棧" 操作做準(zhǔn)備的。

比如，將圖 5 中的元素 2 出棧，則需要先將元素 4 和元素 3 依次出棧。需要注意的是，當(dāng)有數(shù)據(jù)出棧時，要將 top 做 -1 操作。因此，元素 4 和元素 3 出棧的過程分別如圖 6a) 和 6b) 所示：

元素 4 和元素 3 全部出棧后，元素 2 才能出棧。因此，使用順序表模擬數(shù)據(jù)出棧操作的 C 語言實現(xiàn)代碼為：

代碼中的 if 語句是為了防止用戶做 "棧中已無數(shù)據(jù)卻還要做出棧操作" 的錯誤操作。細(xì)心的讀者還可能發(fā)現(xiàn)，出棧操作只是將 top 的值減 1，并沒有像圖 6 那樣將出棧元素從數(shù)組中手動刪除。這是因為，當(dāng)有新的元素入棧后，新元素會將出棧元素覆蓋掉，所以不刪除出棧元素，也不會影響棧的正常使用，何必多此一舉。

總結(jié)

通過學(xué)習(xí)順序表模擬棧中數(shù)據(jù)入棧和出棧的操作，初學(xué)者完成了對順序棧的學(xué)習(xí)，這里給出順序棧及對數(shù)據(jù)基本操作的 C 語言完整代碼：

程序輸出結(jié)果為：

彈棧元素：4
彈棧元素：3
彈棧元素：2
彈棧元素：1
空棧