順序棧

順序棧是棧的順序實現。順序棧是指利用順序存儲結構實現的棧。採用地址連續的存儲空間（數組）依次存儲棧中數據元素，由於入棧和出棧運算都是在棧頂進行，而棧底位置是固定不變的，可以將棧底位置設定在數組空間的起始處；棧頂位置是隨入棧和出棧操作而變化的，故需用一個整型變數top來記錄當前棧頂元素在數組中的位置。

基本介紹

• 中文名：順序棧
• 性質：通信信息科學術語

解釋

棧的元素依次存放在一個一維數組中。下標小的一端作為棧底。用一個變數記錄棧頂位置，稱“棧頂指針”。

套用

進棧是把元素存放在棧頂後面一個位置，棧頂往後移；出棧是刪除棧頂元素，棧頂往前移。適合棧元素數量比較確定的情況。

表示和實現

棧的順序存儲結構是利用記憶體中的一片起始位置確定的連續存儲區域來存放棧中的所有元素，另外為了指示棧頂的準確位置，還需要引入一個棧頂指示變數top，採用順序存儲結構的棧稱為順序棧（sequence stack)。設數組data[MAXSIZE]為棧的存儲空間，其中MAX-SIZE是一個預先設定的常數，為允許進棧結點的最大可能數目，即棧的容量。初始時棧空，top等於0。當top不等於0時，data[0]為棧底元素，即為當前停留在棧中時間最長的元素；而data[top-1]為最後入棧的元素，即為棧頂元素。當top==MAXSIZE時，表示棧滿，如果此時再有結點進棧，將發生稱之為“上溢”（語法上表現為“數組越界”）的錯誤，而當top==0時再執行出棧操作，將發生稱之為“下溢”的錯誤。圖3.4給出了棧容量為6時，入棧、出棧操作以及棧空、棧滿等幾種典型的棧狀態。由於順序存儲結構多採用一維數組存放棧，因此必須特別注意“棧上溢”錯誤的發生；在實現入棧操作時，先判斷是否棧滿（stack full)，如果棧滿，及時處理。