數(shù)組棧

其實(shí)際就是用一段連續(xù)的存儲(chǔ)空間來(lái)存儲(chǔ)棧中的數(shù)據(jù)元素，有以下特點(diǎn)：

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

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

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

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

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

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

棧的定義如下

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

• base 表示棧底指針

• top 表示棧頂指針

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

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

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

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

鏈表?xiàng)?span style="display: none;">

我們以鏈表?xiàng)５膭?dòng)態(tài)鏈表?xiàng)槔?，進(jìn)行棧的設(shè)計(jì)。

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

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

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

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

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

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

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

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

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

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

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

其代碼可以表示為：

//入棧?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ù)說(shuō)一次，一定要進(jìn)行判空操作，將棧頂?shù)脑貏h除，同時(shí)top指針，next向下進(jìn)行移動(dòng)即可的操作。

其代碼可以表示為：

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

棧的基本操作—遍歷

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

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

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

其代碼可以表示為：

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

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

最后呢，我們使用代碼來(lái)幫助我們了解一下：

棧數(shù)組

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

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

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

其代碼如下:

#include
#include
#include
#define?maxn?10000
?
//結(jié)點(diǎn)設(shè)計(jì)
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操作來(lái)自于庫(kù)文件string.h，其表示將整個(gè)空間進(jìn)行初始化
????//不理解可以查閱百度百科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};??//模擬五個(gè)輸入數(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é)點(diǎn)設(shè)計(jì)
//單個(gè)結(jié)點(diǎn)設(shè)計(jì)，數(shù)據(jù)和下一個(gè)指針
typedef?struct?node?????
{
????int?data;?
????struct?node?*next;
}?Node;
//利用上面的結(jié)點(diǎn)創(chuàng)建棧，分為指向頭結(jié)點(diǎn)的top指針和計(jì)數(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("錯(cuò)誤：棧為空");
????????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("錯(cuò)誤：棧為空");
????????return?0;
????}
????while?(temp?!=?NULL)
????{
????????printf("%d\t",?temp->data);
????????temp?=?temp->next;
????}
????printf("\n");
????return?0;
}
?
int?main()
{?//用主函數(shù)測(cè)試一下功能
?int?i;
????Link_Stack?*p;
????p?=?Creat_stack();
????int?n?=?5;
????int?input[6]?=?{10,20,30,40,50,60};
????/////////////以依次入棧的方式創(chuàng)建整個(gè)棧//////////////
????for(i=0;i????????Push_stack(p,?input[i]);
????}
????show_stack(p);
????////////////////////出棧///////////////////////
????Pop_stack(p);
????show_stack(p);
????return?0;
}

編譯結(jié)果如下：

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

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

今天?；A(chǔ)就講到這里，下一期，我們?cè)僖?jiàn)！