什么是順序棧？什么又是鏈棧？

1、順序棧

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

#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指針指向一塊存儲數(shù)據(jù)的內(nèi)存，我們還通過宏定義了一個NAN值表示非法值。

棧初始化

函數(shù)實(shí)現(xiàn)如下：

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; }

這里我們申請了一塊內(nèi)存用于存儲數(shù)據(jù)，并保存棧容量大小。

入棧

函數(shù)實(shí)現(xiàn)如下：

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; //保存數(shù)據(jù)后棧頂指針往后移 }

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

出棧

每次出棧是后面入棧的數(shù)據(jù)先出，前面入棧的數(shù)據(jù)后出。函數(shù)實(shí)現(xiàn)如下：

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］; //先遞減棧頂指針，獲取棧頂數(shù)據(jù) }

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

獲取棧大小

函數(shù)實(shí)現(xiàn)如下：

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

判斷棧是否為空

函數(shù)實(shí)現(xiàn)如下：

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

判斷棧是否滿

函數(shù)實(shí)現(xiàn)如下：

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

銷毀棧

函數(shù)實(shí)現(xiàn)如下：

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; }

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

2、鏈棧

在前面的文章中我們講解了單鏈表，在文中我們采用頭插法插入結(jié)點(diǎn)到鏈表，由于頭插法每次將最新的數(shù)據(jù)插入到鏈表頭，如果依次遍歷鏈表獲取鏈表結(jié)點(diǎn)的數(shù)據(jù)，就是標(biāo)準(zhǔn)的棧彈出數(shù)據(jù)的操作?，F(xiàn)在我們用前面文章實(shí)現(xiàn)的單鏈表實(shí)現(xiàn)一個鏈棧，顧名思義鏈棧就是用鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)棧。我們自定義一個棧數(shù)據(jù)類型并聲明一些操作函數(shù)。

typedef list_t stack_linked_t; //自定義棧數(shù)據(jù)類型 extern stack_linked_t *new_stack_linked_node（int data）; //新建一個棧結(jié)點(diǎn) 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，看似多此一舉，實(shí)際上更直觀了，我們雖然使用鏈表實(shí)現(xiàn)棧，但是如果將數(shù)據(jù)類型聲明為list_t反而更迷惑。由于鏈棧是鏈?zhǔn)浇Y(jié)構(gòu)不存在棧是否滿的情況，除非已經(jīng)無法申請到內(nèi)存。

新建棧結(jié)點(diǎn)

函數(shù)實(shí)現(xiàn)如下：

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

這里我們直接對新建鏈表結(jié)點(diǎn)函數(shù)進(jìn)行封裝，后面我們也會大量用到鏈表操作函數(shù)，差不多都是類似的封裝。

入棧

函數(shù)實(shí)現(xiàn)如下：

void stack_linked_push（stack_linked_t **s， int data）{ //這里一定要注意分開兩個if，因?yàn)榛蜻\(yùn)算符的特性 if（s == NULL）{ return; } if（*s == NULL）{ return; } //采用頭插法插入鏈表 *s = list_add（*s， data）; }

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

出棧

為了獲取鏈表頭結(jié)點(diǎn)，我們定義了一個獲取鏈表頭結(jié)點(diǎn)函數(shù)，函數(shù)實(shí)現(xiàn)如下：

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

出棧函數(shù)實(shí)現(xiàn)如下：

int stack_linked_pop（stack_linked_t **s）{ //這里一定要注意分開兩個if，因?yàn)榛蜻\(yùn)算符的特性 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; }

獲取鏈表頭結(jié)點(diǎn)數(shù)據(jù)并釋放內(nèi)存。

獲取棧大小

獲取棧大小其實(shí)就是獲取鏈表長度，因此我們定義了一個獲取鏈表長度函數(shù)，函數(shù)實(shí)現(xiàn)如下：

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

獲取棧大小實(shí)現(xiàn)函數(shù)如下：

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

判斷棧是否為空

函數(shù)實(shí)現(xiàn)如下：

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

鏈表長度為0則鏈表為空，非0則有數(shù)據(jù)。

銷毀棧

函數(shù)實(shí)現(xiàn)如下：

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

3、驗(yàn)證測試

最后我們寫一個小程序驗(yàn)證一下我們實(shí)現(xiàn)的棧是否正確，代碼如下：

#include 《stdio.h》 #include “stack.h” int main（） { _stack_t my_stack; int i = 0; stack_init（&my_stack， 5）; //初始化棧 printf（“進(jìn)棧順序 ”）; for（i = 0; i 《 5; i++）{ printf（“%d， ”， i）; stack_push（&my_stack， i）; //將數(shù)據(jù)壓入棧 } 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（“用鏈表實(shí)現(xiàn)棧 ”）; 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; }

編譯運(yùn)行輸出：

進(jìn)棧順序 0， 1， 2， 3， 4， 棧已滿 棧的大小是：5 出棧順序是 4 ，3 ，2 ，1 ，0 ， 棧為空 用鏈表實(shí)現(xiàn)棧 入棧順序 0 ，1 ，2 ，3 ，4 ，5 ， 棧大小是： 6 出棧順序是 5 ，4 ，3 ，2 ，1 ，0 ， 鏈棧為空

輸出完全正確。