數(shù)據(jù)結(jié)構(gòu)與算法篇-棧
[導(dǎo)讀]01—順序棧棧是一種后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，棧的實(shí)現(xiàn)方式主要有2種，順序棧和鏈棧。順序棧則是棧的元素虛擬內(nèi)存地址是連續(xù)的，鏈棧則是棧元素虛擬地址非連續(xù)的。在C語言里數(shù)組的元素虛擬地址是連續(xù)的但是數(shù)組大小必須在編譯的時(shí)候確定，用于實(shí)現(xiàn)棧不夠靈活。而在C語言里調(diào)用malloc申請到的一塊...
01—順序棧
棧是一種后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，棧的實(shí)現(xiàn)方式主要有2種，順序棧和鏈棧。順序棧則是棧的元素虛擬內(nèi)存地址是連續(xù)的，鏈棧則是棧元素虛擬地址非連續(xù)的。在C語言里數(shù)組的元素虛擬地址是連續(xù)的但是數(shù)組大小必須在編譯的時(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); //銷毀棧這里我們自定義了一個(gè)_stack_t類型，size是棧大小，cap是棧容量，front是棧頂，arr指針指向一塊存儲數(shù)據(jù)的內(nèi)存，我們還通過宏定義了一個(gè)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;
}這里我們申請了一塊內(nèi)存用于存儲數(shù)據(jù)，并保存棧容量大小。
- 入棧
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ù)。
- 出棧
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í)說明棧里沒有數(shù)據(jù)則返回一個(gè)非法值，否則獲取棧頂數(shù)據(jù)并返回。
- 獲取棧大小
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;
}銷毀棧操作主要是釋放內(nèi)存，并初始化成員變量。02—鏈棧
在前面的文章中我們講解了單鏈表，在文中我們采用頭插法插入結(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)一個(gè)鏈棧，顧名思義鏈棧就是用鏈?zhǔn)?a href="/tags/數(shù)據(jù)結(jié)構(gòu)" target="_blank">數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)棧。我們自定義一個(gè)棧數(shù)據(jù)類型并聲明一些操作函數(shù)。
typedef?list_t?stack_linked_t; //自定義棧數(shù)據(jù)類型
extern?stack_linked_t *new_stack_linked_node(int?data); //新建一個(gè)棧結(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)
stack_linked_t?*new_stack_linked_node(int?data){
????return?new_list_node(data);
}這里我們直接對新建鏈表結(jié)點(diǎn)函數(shù)進(jìn)行封裝，后面我們也會大量用到鏈表操作函數(shù)，差不多都是類似的封裝。
- 入棧
void?stack_linked_push(stack_linked_t?**s, int?data){
????//這里一定要注意分開兩個(gè)if，因?yàn)榛蜻\(yùn)算符的特性
????if(s == NULL){
????????return;
????}
????if(*s == NULL){
????????return;
????}
????//采用頭插法插入鏈表
????*s = list_add(*s, data);
}這里重點(diǎn)注意由于我們傳入的是一個(gè)二級指針if(s == NULL)和if(*s == NULL)一定要分開處理，不能使用||運(yùn)算進(jìn)行處理，因?yàn)閨|運(yùn)算符會執(zhí)行第二個(gè)判斷，如果s == NULL成立那么在執(zhí)行第二個(gè)判斷時(shí)由于使用了空指針程序會奔潰。
- 出棧
list_t *get_list_head(list_t **list){
????if(list?== NULL){
????????return?NULL;
????}
????if(*list?== NULL){
????????return?NULL;
????}
????list_t *head = *list;
????//鏈表只有一個(gè)結(jié)點(diǎn)
????if((*list)->next == NULL){
????????*list?= NULL;
????????return?head;
????}
????//鏈表長度大于1則保存頭結(jié)點(diǎn)，新頭結(jié)點(diǎn)是原頭結(jié)點(diǎn)的下一個(gè)結(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){
????//這里一定要注意分開兩個(gè)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)存。
- 獲取棧大小
//獲取鏈表長度
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);
}- 判斷棧是否為空
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ù)。
- 銷毀棧
void?stack_linked_destroy(stack_linked_t?**s){
????if(s == NULL){
????????return;
????}
????if(*s == NULL){
????????return;
????}
????list_destroy(*s);
????*s = NULL;
}03—驗(yàn)證測試
最后我們寫一個(gè)小程序驗(yàn)證一下我們實(shí)現(xiàn)的棧是否正確，代碼如下：
#include?
#include?"stack.h"
int?main()?{
????_stack_t?my_stack;
????int?i = 0;
????stack_init( 
下載文檔
