棧的基本概念

????????棧是一種特殊的線性存儲結構，是一種操作受到限制的線性表，特殊體現在兩個地方：

? ? ? ? 1、元素進棧出棧的操作只能從同一端完成，另一端是封閉的，通常將數據進棧叫做入棧，壓棧等，出棧叫做彈棧、出棧等。

? ? ? ? 2、棧中無論存數據還是取數據，都必須遵循“先進后出”的原則，即最先入棧的元素最先出棧。以上圖為例，很容易可以看出是元素 1 最先入棧，然后依次是元素 2、3、4 入棧。在此基礎上，如果想取出元素 1，根據“先進后出”的原則，必須先依次將元素 4、3、2 出棧，最后才能輪到元素 1 出棧。?

?????????

????????由此我們可以對棧存儲結構下一個定義：棧是一種“只能從一端存取元素，且存取過程必須遵循‘先進后出’原則”的線性存儲結構。

????????棧就類似于彈夾，只能從一端壓入子彈，要取出子彈也只能對最上方的子彈進行操作，對應了棧先進后出，只能操作棧頂元素。

? ? ? ? 上述提到，棧本質上是操作受到限制的線性表，線性表主要有兩種：分別是數組和鏈表，所以棧有數組和鏈表兩種實現方式。

????????1.順序存儲的數組，優點: 節省空間，操作簡單，學習成本較低，易于理解。缺點: 棧的大小從一開始就固定了，不利于動態擴容。

????????2.非順序存儲的鏈表，優缺點：與數組棧正好相反。

? ? ? ? 棧的核心操作包括出棧，入棧，判空，訪問棧頂等，數組棧要比鏈表棧多一個判滿操作。

數組棧

? ? ? ? 下述代碼實現了棧的基本操作，包括出棧、入棧、判空、判滿、訪問棧頂。

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <stdbool.h>
//數組棧要提前設置最大容量
#define max 20typedef struct
{//以int類型數據為例int data[max];int index;//棧頂地址
}stack;
//壓棧
bool stack_push(stack *sk,int data)
{//檢測空指針if(sk == NULL)return false;//檢測棧是否已滿if(sk->index == max - 1)return false;//更新棧頂地址sk->index++;//數據入棧sk->data[sk->index] = data;return true;
}
//彈棧
bool stack_pop(stack *sk)
{//檢測空指針if(sk == NULL)return false;//檢測棧是否已空if(sk->index < 0)return false;//更新棧頂地址，無需將后面的數據置0，因為操作受限制，無法訪問到后邊的下標。sk->index--;return true;
}
//返回棧頂元素
int stack_top(stack *sk)
{//檢測空指針if(sk == NULL)return false;//檢測棧是否已空if(sk->index < 0)return false;return sk->data[sk->index];
}
bool stack_full(stack *sk)
{if(sk == NULL)return false;return sk->index == max - 1 ? true : false;
}
//查看棧是否已空
bool stack_empty(stack *sk)
{//檢測空指針if(sk == NULL)return false;return sk->index < 0 ? true : false;
}int main(int argc, char const *argv[])
{//初始化棧，設置棧頂為-1stack sk;sk.index = -1;//逐個壓棧，查看棧頂元素for (int i = 0; i < 20; i++){stack_push(&sk,i + 1);printf("%d ",stack_top(&sk));}printf("\n");stack_full(&sk) ? printf("已滿\n") : printf("未滿\n");stack_empty(&sk) ? printf("空\n") : printf("非空\n");stack_pop(&sk) ? printf("彈棧成功\n") : printf("彈棧失敗\n");printf("此時棧頂元素為%d\n",stack_top(&sk));for (int i = 0; i < 20; i++){stack_pop(&sk) ? printf("彈棧成功\n") : printf("彈棧失敗\n");}stack_empty(&sk) ? printf("空\n") : printf("非空\n");return 0;
}

?運行結果如下

????????因為在中間進行了一次出棧，所以在循環中的最后一次彈棧時，棧已經空，進而彈棧失敗。??

鏈表棧

? ? ? ? 鏈表棧的存儲方式是鏈表，所以在實現棧之前需要先定義鏈表的基本操作，再實現棧。

? ? ? ? 下述代碼實現了棧的基本操作包括判空、出棧、入棧、訪問棧頂，鏈表棧不存在判滿操作，只有數組棧需要，因為鏈表并不存在滿的情況。

#include <stdio.h>
#include <malloc.h>
#include <stdbool.h>typedef struct node
{__uint32_t data;struct node *next;
}Node;typedef struct 
{struct node *top;
}stack;
//定義鏈表的頭插法，首元結點就是棧頂，對應了入棧操作
void head_insert(Node *list,__uint32_t data)
{Node *new_node = (Node *)malloc(sizeof(Node));new_node->data = data;new_node->next = list->next;list->next = new_node;
}
//定義鏈表的頭刪法，首元結點就是棧頂，對應了出棧操作
void head_delete(Node *list)
{Node *tmp = list->next;list->next = list->next->next;free(tmp);
}
//入棧，調用頭插法
bool stack_push(stack *sk,__uint32_t data)
{if(sk->top == NULL)return false;head_insert(sk->top,data);return true;
}
//出棧，調用頭刪法
bool stack_pop(stack *sk)
{//判斷是否為空棧if(sk->top->next == NULL)return false;head_delete(sk->top);return true;
}
//訪問棧頂元素
int stack_top(stack *sk)
{//判斷是否為空棧if(sk->top->next == NULL)return -1;return sk->top->next->data;
}
//棧判空，也就是鏈表判空
bool stack_empty(stack *sk)
{return sk->top->next == NULL ? true : false;
}
//摧毀整個鏈表
void list_destroy(Node *list)
{Node *current = list;while (current){Node *tmp = current;current = current->next;free(tmp);}}int main(int argc, char const *argv[])
{//定義一個鏈表Node *list = (Node *)malloc(sizeof(Node));list->data = 0;list->next = NULL;//定義棧頂指針stack *sk = (stack *)malloc(sizeof(stack));sk->top = list;stack_empty(sk) ? printf("空\n") : printf("非空\n");for (int i = 0; i < 10; i++){stack_push(sk,i + 1);printf("%d ",stack_top(sk));}printf("\n");printf("棧頂元素為%d\n",stack_top(sk));stack_empty(sk) ? printf("空\n") : printf("非空\n");stack_pop(sk);printf("棧頂元素為%d\n",stack_top(sk));for (int i = 0; i < 10; i++)stack_pop(sk) ? printf("彈棧成功\n") : printf("彈棧失敗\n");stack_empty(sk) ? printf("空\n") : printf("非空\n");list_destroy(list);free(sk);return 0;
}

運行結果如下

? ? ? ? 因為在中間進行了一次出棧，所以在循環中的最后一次彈棧時，棧已經空，進而彈棧失敗。?