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

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

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

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

圖 1 順序表存儲 {1,2,3,4}

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

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

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

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

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

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

順序棧元素"入棧"

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

圖 3 空棧示意圖

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

圖 4 模擬棧存儲元素 1

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

圖 5 模擬棧存儲{1,2,3,4}

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

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

代碼中的 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) 所示：

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

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

元素 4 和元素 3 全部出棧后，元素 2 才能出棧。因此，使用順序表模擬數(shù)據(jù)出棧操作的實現(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 語句是為了防止用戶做 "棧中已無數(shù)據(jù)卻還要數(shù)據(jù)出棧" 的錯誤操作。代碼中，關(guān)于對棧中元素出棧操作的實現(xiàn)，只需要 top 值 -1 即可。

總結(jié)

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

#include <stdio.h>
//元素elem進棧
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
空棧