1、順序棧

棧是一種后進先出的數據結構，棧的實現方式主要有2種，順序棧和鏈棧。順序棧則是棧的元素虛擬內存地址是連續的，鏈棧則是棧元素虛擬地址非連續的。在C語言里數組的元素虛擬地址是連續的但是數組大小必須在編譯的時候確定，用于實現棧不夠靈活。而在C語言里調用malloc申請到的一塊內存虛擬地址是連續的，而且大小在運行期間確定，比較符合我們靈活的實現順序棧的需求。先來看一下順序棧的定義和函數聲明。

#define NAN （0xFFFFFFFE） typedef struct stack{ int size; int cap; int front; int *arr; }_stack_t; extern void stack_init（_stack_t *s， int capacity）; //初始化棧 extern void stack_push（_stack_t *s， int data）; //入棧 extern int stack_pop（_stack_t *s）; //出棧 extern int stack_size（_stack_t *s）; //獲取棧大小 extern bool stack_is_empty（_stack_t *s）; //判斷棧是否為空 extern bool stack_is_full（_stack_t *s）; //判斷棧是否滿 extern void stack_destroy（_stack_t *s）; //銷毀棧

這里我們自定義了一個_stack_t類型，size是棧大小，cap是棧容量，front是棧頂，arr指針指向一塊存儲數據的內存，我們還通過宏定義了一個NAN值表示非法值。

棧初始化

函數實現如下：

void stack_init（_stack_t *s， int capacity）{ if（s == NULL || capacity 《= 0）{ return; } s-》arr = （int *）malloc（capacity * sizeof（int））; s-》front = 0; s-》size = 0; s-》cap = capacity; }

這里我們申請了一塊內存用于存儲數據，并保存棧容量大小。

入棧

函數實現如下：

void stack_push（_stack_t *s， int data）{ if（s == NULL）{ return; } if（stack_is_full（s））{ return; } s-》size++; //棧使用大小增1 s-》arr［s-》front++］ = data; //保存數據后棧頂指針往后移 }

由于棧容量有限，每次將數據壓入棧之前先判斷一下棧是否滿，棧未滿才能繼續往里壓入數據。

出棧

每次出棧是后面入棧的數據先出，前面入棧的數據后出。函數實現如下：

int stack_pop（_stack_t *s）{ if（s == NULL）{ return NAN; } //判斷棧是否空 if（stack_is_empty（s））{ return NAN; } s-》size--; //棧使用量減1 return s-》arr［--s-》front］; //先遞減棧頂指針，獲取棧頂數據 }

棧為空時說明棧里沒有數據則返回一個非法值，否則獲取棧頂數據并返回。

獲取棧大小

函數實現如下：

int stack_size（_stack_t *s）{ if（s == NULL）{ return 0; } return s-》size; }

判斷棧是否為空

函數實現如下：

bool stack_is_empty（_stack_t *s）{ if（s == NULL）{ return true; } return s-》size 》 0 ？ false ： true; }

判斷棧是否滿

函數實現如下：

bool stack_is_full（_stack_t *s）{ if（s == NULL）{ return false; } return s-》size == s-》cap ？ true ： false; }

銷毀棧

函數實現如下：

void stack_destroy（_stack_t *s）{ if（s == NULL）{ return; } if（s-》arr）{ free（s-》arr）; } s-》arr = NULL; s-》cap = 0; s-》size = 0; s-》front = 0; }

銷毀棧操作主要是釋放內存，并初始化成員變量。

2、鏈棧

在前面的文章中我們講解了單鏈表，在文中我們采用頭插法插入結點到鏈表，由于頭插法每次將最新的數據插入到鏈表頭，如果依次遍歷鏈表獲取鏈表結點的數據，就是標準的棧彈出數據的操作。現在我們用前面文章實現的單鏈表實現一個鏈棧，顧名思義鏈棧就是用鏈式數據結構實現棧。我們自定義一個棧數據類型并聲明一些操作函數。

typedef list_t stack_linked_t; //自定義棧數據類型 extern stack_linked_t *new_stack_linked_node（int data）; //新建一個棧結點 extern void stack_linked_push（stack_linked_t **s， int data）; //入棧 extern int stack_linked_pop（stack_linked_t **s）; //出棧 extern int stack_linked_size（stack_linked_t *s）; //獲取棧大小 extern bool stack_linked_is_empty（stack_linked_t *s）; //判斷棧是否為空 extern void stack_linked_destroy（stack_linked_t **s）; //銷毀棧

這里我們將list_t自定義成stack_linked_t，看似多此一舉，實際上更直觀了，我們雖然使用鏈表實現棧，但是如果將數據類型聲明為list_t反而更迷惑。由于鏈棧是鏈式結構不存在棧是否滿的情況，除非已經無法申請到內存。

新建棧結點

函數實現如下：

stack_linked_t *new_stack_linked_node（int data）{ return new_list_node（data）; }

這里我們直接對新建鏈表結點函數進行封裝，后面我們也會大量用到鏈表操作函數，差不多都是類似的封裝。

入棧

函數實現如下：

void stack_linked_push（stack_linked_t **s， int data）{ //這里一定要注意分開兩個if，因為或運算符的特性 if（s == NULL）{ return; } if（*s == NULL）{ return; } //采用頭插法插入鏈表 *s = list_add（*s， data）; }

這里重點注意由于我們傳入的是一個二級指針if（s == NULL）和if（*s == NULL）一定要分開處理，不能使用||運算進行處理，因為||運算符會執行第二個判斷，如果s == NULL成立那么在執行第二個判斷時由于使用了空指針程序會奔潰。

出棧

為了獲取鏈表頭結點，我們定義了一個獲取鏈表頭結點函數，函數實現如下：

list_t *get_list_head（list_t **list）{ if（list == NULL）{ return NULL; } if（*list == NULL）{ return NULL; } list_t *head = *list; //鏈表只有一個結點 if（（*list）-》next == NULL）{ *list = NULL; return head; } //鏈表長度大于1則保存頭結點，新頭結點是原頭結點的下一個結點 *list = （*list）-》next; head-》next = NULL; //原頭結點一定要將next指針置為NULL return head; }

出棧函數實現如下：

int stack_linked_pop（stack_linked_t **s）{ //這里一定要注意分開兩個if，因為或運算符的特性 if（s == NULL）{ return NAN; } if（*s == NULL）{ return NAN; } stack_linked_t *stack_node = get_list_head（s）; int data = stack_node-》data; free（stack_node）; return data; }

獲取鏈表頭結點數據并釋放內存。

獲取棧大小

獲取棧大小其實就是獲取鏈表長度，因此我們定義了一個獲取鏈表長度函數，函數實現如下：

//獲取鏈表長度 int list_length（list_t *list）{ if（list == NULL）{ return 0; } int length = 0; while（list ！= NULL）{ length++; list = list-》next; } return length; }

獲取棧大小實現函數如下：

int stack_linked_size（stack_linked_t *s）{ if（s == NULL）{ return 0; } return list_length（s）; }

判斷棧是否為空

函數實現如下：

bool stack_linked_is_empty（stack_linked_t *s）{ if（s == NULL）{ return true; } return list_length（s） 》 0 ？ false ： true; }

鏈表長度為0則鏈表為空，非0則有數據。

銷毀棧

函數實現如下：

void stack_linked_destroy（stack_linked_t **s）{ if（s == NULL）{ return; } if（*s == NULL）{ return; } list_destroy（*s）; *s = NULL; }

3、驗證測試

最后我們寫一個小程序驗證一下我們實現的棧是否正確，代碼如下：

#include 《stdio.h》 #include “stack.h” int main（） { _stack_t my_stack; int i = 0; stack_init（&my_stack， 5）; //初始化棧 printf（“進棧順序 ”）; for（i = 0; i 《 5; i++）{ printf（“%d， ”， i）; stack_push（&my_stack， i）; //將數據壓入棧 } printf（“ ”）; if（stack_is_full（&my_stack））{ printf（“棧已滿 ”）; }else{ printf（“棧未滿 ”）; } printf（“棧的大小是：%d ”， stack_size（&my_stack））; printf（“出棧順序是 ”）; for（i = 0; i 《 5; i++）{ printf（“%d ，”， stack_pop（&my_stack））; } printf（“ ”）; if（stack_is_empty（&my_stack））{ printf（“棧為空 ”）; }else{ printf（“棧未空 ”）; } stack_destroy（&my_stack）; //銷毀棧 printf（“ ”）; printf（“用鏈表實現棧 ”）; printf（“入棧順序 ”）; printf（“%d ，”， 0）; stack_linked_t *my_stack2 = new_stack_linked_node（0）; for（i = 0; i 《 5; i++）{ printf（“%d ，”， i + 1）; stack_linked_push（&my_stack2， i + 1）; } printf（“ ”）; printf（“棧大小是： %d ”， stack_linked_size（my_stack2））; printf（“出棧順序是 ”）; for（i = 0; i 《 6; i++）{ printf（“%d ，”， stack_linked_pop（&my_stack2））; } printf（“ ”）; if（stack_linked_is_empty（my_stack2））{ printf（“鏈棧為空 ”）; }else{ printf（“鏈棧非空 ”）; } stack_linked_destroy（&my_stack2）; return 0; }

編譯運行輸出：

進棧順序 0， 1， 2， 3， 4， 棧已滿 棧的大小是：5 出棧順序是 4 ，3 ，2 ，1 ，0 ， 棧為空 用鏈表實現棧 入棧順序 0 ，1 ，2 ，3 ，4 ，5 ， 棧大小是： 6 出棧順序是 5 ，4 ，3 ，2 ，1 ，0 ， 鏈棧為空

輸出完全正確。