數(shù)據(jù)結(jié)構(gòu)與算法篇-棧

01

—

順序棧

棧是一種后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，棧的實(shí)現(xiàn)方式主要有2種，順序棧和鏈棧。順序棧則是棧的元素虛擬內(nèi)存地址是連續(xù)的，鏈棧則是棧元素虛擬地址非連續(xù)的。在C語(yǔ)言里數(shù)組的元素虛擬地址是連續(xù)的但是數(shù)組大小必須在編譯的時(shí)候確定，用于實(shí)現(xiàn)棧不夠靈活。而在C語(yǔ)言里調(diào)用malloc申請(qǐng)到的一塊內(nèi)存虛擬地址是連續(xù)的，而且大小在運(yùn)行期間確定，比較符合我們靈活的實(shí)現(xiàn)順序棧的需求。先來(lái)看一下順序棧的定義和函數(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指針指向一塊存儲(chǔ)數(shù)據(jù)的內(nèi)存，我們還通過(guò)宏定義了一個(gè)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;
}

這里我們申請(qǐng)了一塊內(nèi)存用于存儲(chǔ)數(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í)說(shuō)明棧里沒(méi)有數(shù)據(jù)則返回一個(gè)非法值，否則獲取棧頂數(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)存，并初始化成員變量。

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)無(wú)法申請(qǐng)到內(nèi)存。

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

函數(shù)實(shí)現(xiàn)如下：
stack_linked_t?*new_stack_linked_node(int?data){
????return?new_list_node(data);
}

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

• 入棧
  
  

函數(shù)實(shí)現(xiàn)如下：
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è)二級(jí)指針if(s == NULL)和if(*s == NULL)一定要分開處理，不能使用||運(yùn)算進(jìn)行處理，因?yàn)閨|運(yùn)算符會(huì)執(zhí)行第二個(gè)判斷，如果s == NULL成立那么在執(zhí)行第二個(gè)判斷時(shí)由于使用了空指針程序會(huì)奔潰。

• 出棧
  

為了獲取鏈表頭結(jié)點(diǎn)，我們定義了一個(gè)獲取鏈表頭結(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;
????//鏈表只有一個(gè)結(jié)點(diǎn)
????if((*list)->next == NULL){
????????*list?= NULL;
????????return?head;
????}

????//鏈表長(zhǎng)度大于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)存。

• 獲取棧大小
  

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

//獲取鏈表長(zhǎng)度
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;
}

鏈表長(zhǎng)度為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;
}

03

—

驗(yàn)證測(cè)試

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

#include?
#include?"stack.h"

int?main()?{
????_stack_t?my_stack;
????int?i = 0;

????stack_init(