對于邏輯關系為“一對一”的數據，除了用順序表和鏈表存儲外，還可以用棧結構存儲。

棧是一種“特殊”的線性存儲結構，它的特殊之處體現在以下兩個地方：
1、元素進棧和出棧的操作只能從一端完成，另一端是封閉的，如下圖所示：

圖 1 棧存儲結構示意圖

通常，我們將元素進棧的過程簡稱為“入棧”、“進棧”或者“壓棧”；將元素出棧的過程簡稱為“出棧”或者“彈棧”。

2、棧中無論存數據還是取數據，都必須遵循“先進后出”的原則，即最先入棧的元素最先出棧。以圖 1 的棧為例，很容易可以看出是元素 1 最先入棧，然后依次是元素 2、3、4 入棧。在此基礎上，如果想取出元素 1，根據“先進后出”的原則，必須先依次將元素 4、3、2 出棧，最后才能輪到元素 1 出棧。

我們習慣將棧的開口端稱為棧頂，封口端稱為棧底。例如在圖 1 中，元素 4 一側為棧頂，元素 1 一側為棧底，如圖 2 所示。

圖 2 棧頂和棧底

由此我們可以對棧存儲結構下一個定義：棧一種“只能從一端存取元素，且存取過程必須遵循‘先進后出’原則”的線性存儲結構。

棧的具體實現

和線性表類似，棧存儲結構也有兩種具體的實現方案：

• 順序棧：用順序表存儲數據，數據存取的過程嚴格遵循棧結構的規定；
• 鏈棧：用鏈表存儲數據，數據存儲的過程嚴格遵循棧結構的規定。

顯然，順序棧和鏈棧兩種實現方案，本質的區別仍然是順序表和鏈表之間的區別，即順序棧是將所有數據集中存儲，而鏈棧是將數據分散存放，元素之間的邏輯關系靠指針維系。

順序棧的具體實現

順序棧指的是用順序表實現的棧存儲結構，通過前面的學習我們知道，棧存儲結構存取數據元素必須遵守 "先進后出" 的原則。本節就給大家詳細講解如何使用順序表模擬棧結構，以及實現元素的入棧和出棧操作。

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

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

使用棧存儲結構存儲?{1,2,3,4}，存儲狀態如圖 2 所示：

圖 2 棧結構存儲 {1,2,3,4}

對比圖 1 和圖 2 不難看出，用順序表模擬棧結構很簡單，只要將數據從數組下標為 0 的位置依次存儲即可。

從數組下標為 0 的模擬棧存儲數據是常用的方法，從其他數組下標處存儲數據也完全可以，這里只是為了方便初學者理解。

了解了順序表模擬實現棧存儲結構之后，接下來學習如何實現元素入棧和出棧的操作。

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

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

順序棧元素"入棧"

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

圖 3 空棧示意圖

將元素 1 入棧，默認數組下標為 0 一端表示棧底，元素 1 存儲在數組 a[0] 處，同時 top 值 +1，如圖 4 所示：

圖 4 模擬棧存儲元素 1

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

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

因此，C 語言實現代碼為：

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

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

順序棧元素"出棧"

實際上，top 變量的設置對模擬數據的 "入棧" 操作沒有幫助，它是為實現數據的 "出棧" 操作做準備的。

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

圖 6 數據元素出棧

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

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

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

總結

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

/*
* 源自 https://xiecoding.cn/ds/
*/
#include <stdio.h>
//元素elem進棧
int push(int* a, int top, int elem) {a[++top] = elem;return top;
}
//數據元素出棧
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;
}

程序輸出結果為：

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

鏈棧的具體實現

鏈棧是棧的一種實現方法，特指用鏈表實現棧存儲結構。

鏈棧的實現思路和順序棧類似，順序棧是將順序表（數組）的一端做棧底，另一端做棧頂；鏈棧也是如此，我們通常將鏈表的頭部做棧頂，尾部做棧底，如圖 1 所示：

圖 1 鏈棧示意圖

以鏈表的頭部做棧頂，最大的好處是：可以避免在實現元素 "入棧" 和 "出棧" 時做大量遍歷鏈表的耗時操作。有元素入棧時，只需要將其插入到鏈表的頭部；有元素出棧時，只需要從鏈表的頭部依次摘取結點。

因此，鏈棧實際上是一個采用頭插法插入或刪除數據的鏈表。

鏈棧元素入棧

例如，依次將 1、2、3、4 存儲到棧中，每個元素的入棧過程如圖 2 所示：

圖 2 鏈棧元素依次入棧過程示意圖

C語言實現代碼為：

鏈棧元素出棧

在圖 2e) 所示鏈表的基礎上，假設將元素 3 從棧中取出，根據"先進后出"的原則，要先將元素 4 出棧，然后元素 3 才能出棧，整個操作過程如圖 3 所示：

圖 3 鏈棧元素出棧示意圖

實現棧頂元素出棧的 C 語言代碼為：

//棧頂元素出鏈棧的實現函數
LineStack* pop(LineStack* stack) {if (stack) {//聲明一個新指針指向棧頂節點LineStack* p = stack;//更新頭指針stack = stack->next;printf("出棧元素：%d ", p->data);if (stack) {printf("新棧頂元素：%d\n", stack->data);}else {printf("棧已空\n");}free(p);}else {printf("棧內沒有元素");return stack;}return stack;
}

代碼中通過使用 if 判斷語句，避免了用戶執行"棧已空卻還要數據出棧"錯誤操作。

總結

本節，通過采用頭插法操作數據的單鏈表實現了鏈棧結構，這里給出鏈棧及基本操作的C語言完整代碼：

/*
* 源自 https://xiecoding.cn/ds/
*/
#include <stdio.h>
#include <stdlib.h>
//鏈表中的節點結構
typedef struct lineStack {int data;struct lineStack* next;
}LineStack;
//stack為當前的鏈棧，a表示入棧元素
LineStack* push(LineStack* stack, int a) {//創建存儲新元素的節點LineStack* line = (LineStack*)malloc(sizeof(LineStack));line->data = a;//新節點與頭節點建立邏輯關系line->next = stack;//更新頭指針的指向stack = line;return stack;
}//棧頂元素出鏈棧的實現函數
LineStack* pop(LineStack* stack) {if (stack) {//聲明一個新指針指向棧頂節點LineStack* p = stack;//更新頭指針stack = stack->next;printf("出棧元素：%d ", p->data);if (stack) {printf("新棧頂元素：%d\n", stack->data);}else {printf("棧已空\n");}free(p);}else {printf("棧內沒有元素");return stack;}return stack;
}int main() {LineStack* stack = NULL;stack = push(stack, 1);stack = push(stack, 2);stack = push(stack, 3);stack = push(stack, 4);stack = pop(stack);stack = pop(stack);stack = pop(stack);stack = pop(stack);stack = pop(stack);return 0;
}

程序運行結果為：

彈棧元素：4 棧頂元素：3
彈棧元素：3 棧頂元素：2
彈棧元素：2 棧頂元素：1
彈棧元素：1 棧已空
棧內沒有元素