數據結構與算法篇-棧
[導讀]01—順序棧棧是一種后進先出的數據結構，棧的實現(xiàn)方式主要有2種，順序棧和鏈棧。順序棧則是棧的元素虛擬內存地址是連續(xù)的，鏈棧則是棧元素虛擬地址非連續(xù)的。在C語言里數組的元素虛擬地址是連續(xù)的但是數組大小必須在編譯的時候確定，用于實現(xiàn)棧不夠靈活。而在C語言里調用malloc申請到的一塊...
01—順序棧
棧是一種后進先出的數據結構，棧的實現(xiàn)方式主要有2種，順序棧和鏈棧。順序棧則是棧的元素虛擬內存地址是連續(xù)的，鏈棧則是棧元素虛擬地址非連續(xù)的。在C語言里數組的元素虛擬地址是連續(xù)的但是數組大小必須在編譯的時候確定，用于實現(xiàn)棧不夠靈活。而在C語言里調用malloc申請到的一塊內存虛擬地址是連續(xù)的，而且大小在運行期間確定，比較符合我們靈活的實現(xiàn)順序棧的需求。先來看一下順序棧的定義和函數聲明。
#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; //保存數據后棧頂指針往后移
}由于棧容量有限，每次將數據壓入棧之前先判斷一下棧是否滿，棧未滿才能繼續(xù)往里壓入數據。
- 出棧
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;
}銷毀棧操作主要是釋放內存，并初始化成員變量。02—鏈棧
在前面的文章中我們講解了單鏈表，在文中我們采用頭插法插入結點到鏈表，由于頭插法每次將最新的數據插入到鏈表頭，如果依次遍歷鏈表獲取鏈表結點的數據，就是標準的棧彈出數據的操作。現(xiàn)在我們用前面文章實現(xiàn)的單鏈表實現(xiàn)一個鏈棧，顧名思義鏈棧就是用鏈式數據結構實現(xiàn)棧。我們自定義一個棧數據類型并聲明一些操作函數。
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，看似多此一舉，實際上更直觀了，我們雖然使用鏈表實現(xiàn)棧，但是如果將數據類型聲明為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)一定要分開處理，不能使用||運算進行處理，因為||運算符會執(zhí)行第二個判斷，如果s == NULL成立那么在執(zhí)行第二個判斷時由于使用了空指針程序會奔潰。
- 出棧
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;
}出棧函數實現(xiàn)如下：
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;
}獲取棧大小實現(xiàn)函數如下：
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;
}03—驗證測試
最后我們寫一個小程序驗證一下我們實現(xiàn)的棧是否正確，代碼如下：
#include?
#include?"stack.h"
int?main()?{
????_stack_t?my_stack;
????int?i = 0;
????stack_init( 
下載文檔
