面試官問我什么是「棧」，我隨手畫了10張圖來解釋

棧的概念

棧（stack）是限定僅在表的一端進行操作的數(shù)據(jù)結(jié)構(gòu)，且棧是一種先進后出的數(shù)據(jù)結(jié)構(gòu)，允許操作的一端稱為棧頂，不允許操作的稱為棧底，如下圖所示：

之前我們講到了鏈表，我們只能夠?qū)ζ滏湵淼谋砦步Y(jié)點進行操作，并且只能進行插入一個新的結(jié)點與刪除最末尾的這個結(jié)點兩個操作，而這樣強限制性的‘鏈表’，就是我們所說的棧。

就像是一個死胡同一樣，只有一個出口，如圖所示，有個概念：

棧的結(jié)點設(shè)計

棧分為數(shù)組棧和鏈表棧，其區(qū)別如下：

• 數(shù)組棧使用數(shù)組進行功能的模擬，實現(xiàn)較為快速和便利；

• 鏈表棧使用鏈表的思路去設(shè)計，實現(xiàn)相比較說較為麻煩，但是其穩(wěn)定，且不易出錯；

在鏈表棧中又分為靜態(tài)鏈表棧和動態(tài)鏈表棧，其區(qū)別如下：

• 靜態(tài)鏈表棧給定棧的空間大小，不允許超過存儲超過給定數(shù)據(jù)大小的元素；

• 動態(tài)棧使用的是自動創(chuàng)建空間的方法進行創(chuàng)建，只要符合機器的硬件要求以及編譯器的控制，其理論上是極大的。

數(shù)組棧

其實際就是用一段連續(xù)的存儲空間來存儲棧中的數(shù)據(jù)元素，有以下特點：

1. 元素所占的存儲空間必須連續(xù)，這里的連續(xù)是指的邏輯連續(xù)，而不是物理連續(xù)。

2. 元素在存儲空間的位置是按邏輯順序存放的

我們來舉例說明，鑒于C語言數(shù)組下標都是0開始，并且棧的使用需要的空間大小難以估計，所以初始化空棧的時候，不應(yīng)該設(shè)定棧的最大容量。

我們先為棧設(shè)定一個基本容量，在應(yīng)用過STACK_程當(dāng)中，當(dāng)棧的空間不夠用時，再逐漸擴大。

設(shè)定2個常量，STACK_INIT_SIZE(存儲空間初始化分配量)和STACK_INCREMENT(存儲空間分配增量),宏定義如下

#define?STACK_INIT_SIZE?1000?//數(shù)值可以根據(jù)實際情況確定
#define?STACK_INCREMENT?10???//數(shù)值可以根據(jù)實際情況確定

棧的定義如下

typedef?struct??????
{
????void?*base;?
????void?*top;
????int?stackSize;
}?SqSTACK;

• base 表示棧底指針

• top 表示棧頂指針

• stackSize 表示棧當(dāng)前可以使用的最大容量

若base的值是NULL，表示棧結(jié)構(gòu)不存在;top初始值指向棧底，即top = base;

每當(dāng)插入新的元素時，指針top就增1，反之刪除就減1，非空棧中的棧頂指針始終在棧頂元素的下一個指針上面。

數(shù)據(jù)元素和棧頂指針的關(guān)系如下圖所示：

鏈表棧

我們以鏈表棧的動態(tài)鏈表棧為例子，進行棧的設(shè)計。

首先是棧的結(jié)點，設(shè)計出兩個結(jié)構(gòu)體，一個結(jié)構(gòu)體Node表示結(jié)點，其中包含有一個data域和next指針，如圖所示：

其中data表示數(shù)據(jù)，next指針表示下一個的指針，其指向下一個結(jié)點，通過next指針將各個結(jié)點鏈接。

接下來是我們設(shè)計的重點，為這個進行限制性的設(shè)計，我們需要額外添加一個結(jié)構(gòu)體，其包括了一個永遠指向棧頭的指針top和一個計數(shù)器count記錄元素個數(shù)。

其主要功效就是設(shè)定允許操作元素的指針以及確定棧何時為空，如圖所示：

這里我采用的是top和count組合的方法。其代碼可以表示為：

//棧的結(jié)點設(shè)計
//單個結(jié)點設(shè)計，數(shù)據(jù)和下一個指針
typedef?struct?node?????
{
????int?data;?
????struct?node?*next;
}?Node;

利用上面的結(jié)點創(chuàng)建棧，分為指向頭結(jié)點的top指針和計數(shù)用的count

typedef?struct?stack????
{
????Node?*top;
????int?count;
}?Link_Stack;

棧的基本操作—入棧（壓棧）

入棧的基本順序可以用以下圖所示：

入棧(push)操作時，我們只需要找到top所指向的空間，創(chuàng)建一個新的結(jié)點，將新的結(jié)點的next指針指向top指針指向的空間，再將top指針轉(zhuǎn)移，并且指向新的結(jié)點，這就是是入棧操作。

其代碼可以表示為：

//入棧?push
Link_Stack?*Push_stack(Link_Stack?*p,?int?elem)
{
????if?(p?==?NULL)
????????return?NULL;
????Node?*temp;
????temp=(Node*)malloc(sizeof(Node));
????//temp?=?new?Node;
????temp->data?=?elem;
????temp->next?=?p->top;
????p->top?=?temp;
????p->count++;
????return?p;
}

棧的基本操作—出棧

出棧（pop）操作，是在棧不為空的情況下，重復(fù)說一次，一定要進行判空操作，將棧頂?shù)脑貏h除，同時top指針，next向下進行移動即可的操作。

其代碼可以表示為：

//出棧?pop
Link_Stack?*Pop_stack(Link_Stack?*p)
{
????Node?*temp;
????temp?=?p->top;
????if?(p->top?==?NULL)
????{
????????printf("錯誤：棧為空");
????????return?p;
????}
????else
????{
????????p->top?=?p->top->next;
????????free(temp);
????????//delete?temp;
????????p->count--;
????????return?p;
????}
}

棧的基本操作—遍歷

這個就很常見了，也是我們調(diào)試必須的手段。

棧的遍歷相對而言比較復(fù)雜，由于棧的特殊性質(zhì)，其只允許在一端進行操作，所以遍歷操作操作永遠都是逆序的。

簡單一點描述，其過程為，在棧不為空的情況下，一次從棧頂元素向下訪問，直到指針指向空（即到棧尾）為結(jié)束。

其代碼可以表示為：

//遍歷棧：輸出棧中所有元素
int?show_stack(Link_Stack?*p)
{
????Node?*temp;
????temp?=?p->top;
????if?(p->top?==?NULL)
????{
????????printf("");
????????printf("錯誤：棧為空");
????????return?0;
????}
????while?(temp?!=?NULL)
????{
????????printf("%d\t",?temp->data);
????????temp?=?temp->next;
????}
????printf("\n");
????return?0;
}

棧數(shù)組與棧鏈表的代碼實現(xiàn)

最后呢，我們使用代碼來幫助我們了解一下：

棧數(shù)組

數(shù)組棧是一種更為快速的模擬實現(xiàn)棧的方法，這里我們不多說。

模擬，就是不采用真實的鏈表設(shè)計，轉(zhuǎn)而采用數(shù)組的方式進行模擬操作。

也就是說這是一種仿真類型的操作，其可以快速的幫助我們構(gòu)建代碼，分析過程，相應(yīng)的實現(xiàn)起來也更加的便捷。

其代碼如下:

#include
#include
#include
#define?maxn?10000
?
//結(jié)點設(shè)計
typedef?struct?stack{
????int?data[maxn];
????int?top;
}stack;
?
//創(chuàng)建
stack?*init(){
????stack?*s=(stack?*)malloc(sizeof(stack));
????if(s==NULL){
????????printf("分配內(nèi)存空間失敗");
????????exit(0);
????}
????memset(s->data,0,sizeof(s->data));
????//memset操作來自于庫文件string.h，其表示將整個空間進行初始化
????//不理解可以查閱百度百科https://baike.baidu.com/item/memset/4747579?fr=aladdin
????s->top=0;?????//棧的top和bottom均為0（表示為空）
????return?s;
}
?
//入棧push
void?push(stack?*s,int?data){
????s->data[s->top]=data;
????s->top++;
}
?
//出棧pop
void?pop(stack?*s){
????if(s->top!=0){
????????s->data[s->top]=0;??//讓其回歸0模擬表示未初始化即可
????????s->top--;
????}
}
?
//模擬打印棧中元素
void?print_stack(stack?*s){
????for(int?n=s->top-1;n>=0;n--){
????????printf("%d\t",s->data[n]);
????}
????printf("\n");???//習(xí)慣性換行
}
?
int?main(){
????stack?*s=init();
????int?input[5]={11,22,33,44,55};??//模擬五個輸入數(shù)據(jù)
????for(int?i=0;i<5;i++){
????????push(s,input[i]);
????}
????print_stack(s);
????/////////////
????pop(s);
????print_stack(s);
????return?0;
}

其編譯結(jié)果如下：

棧鏈表

#include?
#include?
//棧的結(jié)點設(shè)計
//單個結(jié)點設(shè)計，數(shù)據(jù)和下一個指針
typedef?struct?node?????
{
????int?data;?
????struct?node?*next;
}?Node;
//利用上面的結(jié)點創(chuàng)建棧，分為指向頭結(jié)點的top指針和計數(shù)用的count
typedef?struct?stack????
{
????Node?*top;
????int?count;
}?Link_Stack;
?
//創(chuàng)建棧
Link_Stack?*Creat_stack()
{
????Link_Stack?*p;
????//p?=?new?Link_Stack;
????p=(Link_Stack*)malloc(sizeof(Link_Stack));
????if(p==NULL){
????????printf("創(chuàng)建失敗，即將退出程序");
????????exit(0);
????}
?else
?{printf("創(chuàng)建成功\n");
?}
????p->count?=?0;
????p->top?=?NULL;
????return?p;
}
?
//入棧?push
Link_Stack?*Push_stack(Link_Stack?*p,?int?elem)
{
????if?(p?==?NULL)
????????return?NULL;
????Node?*temp;
????temp=(Node*)malloc(sizeof(Node));
????//temp?=?new?Node;
????temp->data?=?elem;
????temp->next?=?p->top;
????p->top?=?temp;
????p->count++;
????return?p;
}
?
//出棧?pop
Link_Stack?*Pop_stack(Link_Stack?*p)
{
????Node?*temp;
????temp?=?p->top;
????if?(p->top?==?NULL)
????{
????????printf("錯誤：棧為空");
????????return?p;
????}
????else
????{
???printf("\npop?success");
????????p->top?=?p->top->next;
????????free(temp);
????????//delete?temp;
????????p->count--;
????????return?p;
????}
}
?
//遍歷棧：輸出棧中所有元素
int?show_stack(Link_Stack?*p)
{
????Node?*temp;
????temp?=?p->top;
????if?(p->top?==?NULL)
????{
????????printf("");
????????printf("錯誤：棧為空");
????????return?0;
????}
????while?(temp?!=?NULL)
????{
????????printf("%d\t",?temp->data);
????????temp?=?temp->next;
????}
????printf("\n");
????return?0;
}
?
int?main()
{?//用主函數(shù)測試一下功能
?int?i;
????Link_Stack?*p;
????p?=?Creat_stack();
????int?n?=?5;
????int?input[6]?=?{10,20,30,40,50,60};
????/////////////以依次入棧的方式創(chuàng)建整個棧//////////////
????for(i=0;i????????Push_stack(p,?input[i]);
????}
????show_stack(p);
????////////////////////出棧///////////////////////
????Pop_stack(p);
????show_stack(p);
????return?0;
}

編譯結(jié)果如下：

關(guān)于棧的總結(jié)

棧-它是一種運算受限的線性表，在數(shù)制轉(zhuǎn)換，括號匹配的檢驗，表達式求值等方面都可以使用，并且較為簡便的解決問題。

今天?；A(chǔ)就講到這里，下一期，我們再見！