順序棧的基本操作（入棧和出棧）

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

如果你仔細(xì)觀察順序表(底層實(shí)現(xiàn)是數(shù)組)和棧結(jié)構(gòu)就會(huì)發(fā)現(xiàn)，它們存儲(chǔ)數(shù)據(jù)的方式高度相似，只不過(guò)棧對(duì)數(shù)據(jù)的存取過(guò)程有特殊的限制，而順序表沒(méi)有。

例如，我們先使用順序表(a 數(shù)組)存儲(chǔ) {1,2,3,4}，存儲(chǔ)狀態(tài)如圖 1 所示：

圖 1 順序表存儲(chǔ) {1,2,3,4}

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

圖 2 棧結(jié)構(gòu)存儲(chǔ) {1,2,3,4}

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

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

了解了順序表模擬棧存儲(chǔ)數(shù)據(jù)后，接下來(lái)看如何模擬棧中元素出棧的操作。由于棧對(duì)存儲(chǔ)元素出棧的次序有"先進(jìn)后出"的要求，如果想將圖 1 中存儲(chǔ)的元素 1 從棧中取出，需先將元素 4、元素 3 和元素 2 依次從棧中取出。

這里給出使用順序表模擬棧存儲(chǔ)結(jié)構(gòu)常用的實(shí)現(xiàn)思路，即在順序表中設(shè)定一個(gè)實(shí)時(shí)指向棧頂元素的變量(一般命名為 top)，top 初始值為 -1，表示棧中沒(méi)有存儲(chǔ)任何數(shù)據(jù)元素，及棧是"空棧"。一旦有數(shù)據(jù)元素進(jìn)棧，則 top 就做 +1 操作;反之，如果數(shù)據(jù)元素出棧，top 就做 -1 操作。

順序棧元素"入棧"

比如，還是模擬棧存儲(chǔ) {1,2,3,4} 的過(guò)程。最初，棧是"空棧"，即數(shù)組是空的，top 值為初始值 -1，如圖 3 所示：

圖 3 空棧示意圖

首先向棧中添加元素 1，我們默認(rèn)數(shù)組下標(biāo)為 0 一端表示棧底，因此，元素 1 被存儲(chǔ)在數(shù)組 a[1] 處，同時(shí) top 值 +1，如圖 4 所示：

圖 4 模擬棧存儲(chǔ)元素 1

采用以上的方式，依次存儲(chǔ)元素 2、3 和 4，最終，top 值變?yōu)?3，如圖 5 所示：

圖 5 模擬棧存儲(chǔ){1,2,3,4}

因此，實(shí)現(xiàn)代碼為：

//元素elem進(jìn)棧，a為數(shù)組，top值為當(dāng)前棧的棧頂位置
int push(int* a,int top,int elem){
    a[++top]=elem;
    return top;
}

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

順序棧元素"出棧"

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

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

圖 6 數(shù)據(jù)元素出棧

注意，圖 6 數(shù)組中元素的消失僅是為了方便初學(xué)者學(xué)習(xí)，其實(shí)，這里只需要對(duì) top 值做 -1 操作即可，因?yàn)?top 值本身就表示棧的棧頂位置，因此 top-1 就等同于棧頂元素出棧。并且后期向棧中添加元素時(shí)，新元素會(huì)存儲(chǔ)在類似元素 4 這樣的舊元素位置上，將舊元素覆蓋。

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

//數(shù)據(jù)元素出棧
int pop(int * a,int top){
    if (top==-1) {
        printf("空棧");
        return -1;
    }
    printf("彈棧元素：%d\n",a[top]);
    top--;
    return top;
}

代碼中的 if 語(yǔ)句是為了防止用戶做 "棧中已無(wú)數(shù)據(jù)卻還要數(shù)據(jù)出棧" 的錯(cuò)誤操作。代碼中，關(guān)于對(duì)棧中元素出棧操作的實(shí)現(xiàn)，只需要 top 值 -1 即可。

總結(jié)

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

#include <stdio.h>
//元素elem進(jìn)棧
int push(int* a,int top,int elem){
    a[++top]=elem;
    return top;
}
//數(shù)據(jù)元素出棧
int pop(int * a,int top){
    if (top==-1) {
        printf("空棧");
        return -1;
    }
    printf("彈棧元素：%d\n",a[top]);
    top--;
    return top;
}
int main() {
    int a[100];
    int top=-1;
    top=push(a, top, 1);
    top=push(a, top, 2);
    top=push(a, top, 3);
    top=push(a, top, 4);
    top=pop(a, top);
    top=pop(a, top);
    top=pop(a, top);
    top=pop(a, top);
    top=pop(a, top);
    return 0;
}

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

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