1.概念

1. 壓棧：棧的插入操作叫做進(jìn)棧/壓棧/入棧，入數(shù)據(jù)在棧頂。
2. 出棧：棧的刪除操作叫做出棧，出數(shù)據(jù)也在棧頂。
3. 棧的元素遵循后進(jìn)先出LIFO(Last In First Out)的原則。后面進(jìn)來的數(shù)據(jù)先出去

2.棧的實(shí)現(xiàn)

1. 三種實(shí)現(xiàn)方法，數(shù)組，單鏈表，雙鏈表
2. 這里我們采用數(shù)組，因?yàn)閿?shù)組的緩存利用率高，而且基于結(jié)構(gòu)更加容易訪問，異地?cái)U(kuò)容的時(shí)候會(huì)消耗時(shí)間，但是這個(gè)開銷對(duì)于棧來說很小。
3. 雙鏈表雖然很方便，有前后指針但是要多維護(hù)一個(gè)指針，同時(shí)也會(huì)增加空間的浪費(fèi)，那還不然單鏈表。
4. 分為三個(gè)部分，Stack.h 和 Stack.c 還有test.c;這里只說Stack.c的核心部分
5. 棧的基本結(jié)構(gòu)

typedef struct Stack
{STDataType* pa;//數(shù)組int top;//棧頂int capacity;//有效個(gè)數(shù)
}ST;

2.1初始化，銷毀

1. 這里的關(guān)鍵問題點(diǎn)在于，初始化為0(下標(biāo)位置) 的時(shí)候你要不要放入數(shù)據(jù)？，可是初始化本來就不用放數(shù)據(jù)
2. 在top位置放數(shù)據(jù)的時(shí)候，需要 top++指向下一個(gè)地方，為下一個(gè)準(zhǔn)備放數(shù)據(jù)

//初始化
void STInit(ST* ps)
{assert(ps);ps->pa = NULL;ps->top = ps->capacity = 0;
}//銷毀
void STDestroy(ST* ps)
{assert(ps);ps->top = ps->capacity = 0;free(ps);//刪除元素不行銷毀，因?yàn)閿?shù)組的空間是一次性開辟的ps = NULL;
}

2.2壓棧(push)，刪除(pop)

1. 壓棧就是插入到數(shù)組后面，再插入之前需要看看有沒有空間，就在結(jié)構(gòu)體里面的ps->size插入就行，假如是2，剛好放到數(shù)組下標(biāo)2位置處
2. 防止數(shù)據(jù)丟失不要直接空間給ps->pa,而是先拿個(gè)tmp的臨時(shí)空間來裝著。
3. 如果還是不太熟悉，看看我的單鏈表這篇文章更加詳細(xì)

//壓棧
void STPush(ST* ps,STDataType x)
{assert(ps);//為NULL，你插入個(gè)屁if (ps->top == ps->capacity)//相等說明沒空間{int new = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->pa,sizeof(STDataType) * new);//假如pa 為NULL則 和malloc一樣if (tmp == NULL){perror("STPush()::realloc()");return;}//不要讓ps->pa 直接去接收新空間的地址ps->pa = tmp;ps->capacity = new;}ps->pa[ps->top] = x;ps->top++;
}

1. pop，只有一行可不可不調(diào)用函數(shù)，刪除數(shù)據(jù)呢？不行；因?yàn)闆]有斷言檢查了
2. 這里直接有效個(gè)數(shù)，top-- 就行
3. 入棧順序不代表出棧順尋，可以邊進(jìn)變出，或者入3個(gè)在途中出兩個(gè)
4. 進(jìn)棧順序只有一種，出棧順序有很多種
5. 

//刪除
void STPop(ST* ps)
{assert(ps);assert(ps->top);//為0 不能刪了ps->top--;
}

2.3有效個(gè)數(shù)(size),棧頂數(shù)據(jù)(top)，棧是否為NULL（empty）

//有效個(gè)數(shù)
int STSize(ST* ps)
{assert(ps);return ps->top;
}

//取棧頂元素
STDataType STTop(ST* ps)
{assert(ps);assert(ps->top > 0);//不大于0，你還怎么取棧頂元素return ps->pa[ps->top - 1];//因?yàn)槭怯行г氐那耙粋€(gè)
}

bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;//表達(dá)式為真返回1，假返回0
}

2.4完整代碼

2.4.1Stack.h

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
//可任意更換類型
typedef int STDataType;
typedef struct Stack
{STDataType* pa;//數(shù)組int top;//棧頂int capacity;//有效個(gè)數(shù)
}ST;//初始化和銷毀
void STInit(ST* ps);
void STDestroy(ST* ps);//壓棧和出棧
void STPush(ST* ps, STDataType x);
void STPop(ST* ps);//棧頂元素
STDataType STTop(ST* ps);//有效個(gè)數(shù)
int STSize(ST* ps);//判斷是否為NULL
bool STEmpty(ST* ps);

2.4.2Stack.c

#include "Stack.h"
//初始化
void STInit(ST* ps)
{assert(ps);ps->pa = NULL;ps->top = ps->capacity = 0;
}//壓棧
void STPush(ST* ps,STDataType x)
{assert(ps);//為NULL，你插入個(gè)屁if (ps->top == ps->capacity)//相等說明沒空間{int new = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->pa,sizeof(STDataType) * new);//假如pa 為NULL則 和malloc一樣if (tmp == NULL){perror("STPush()::realloc()");return;}//不要讓ps->pa 直接去接收新空間的地址ps->pa = tmp;ps->capacity = new;}ps->pa[ps->top] = x;ps->top++;
}
//刪除
void STPop(ST* ps)
{assert(ps);assert(ps->top);//為0 不能刪了ps->top--;
}
//取棧頂元素
STDataType STTop(ST* ps)
{assert(ps);assert(ps->top > 0);//不大于0，你還怎么取棧頂元素return ps->pa[ps->top - 1];//因?yàn)槭怯行г氐暮笠粋€(gè)
}
//銷毀
void STDestroy(ST* ps)
{assert(ps);ps->top = ps->capacity = 0;free(ps);//刪除元素不行銷毀，因?yàn)閿?shù)組的空間是一次性開辟的ps = NULL;
}
//有效個(gè)數(shù)
int STSize(ST* ps)
{assert(ps);return ps->top;
}
//判空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;//表達(dá)式為真返回1，假返回0
}

2.4.3test.c

#include "Stack.h"
void STTest()
{ST s;STInit(&s);//壓棧STPush(&s, 1);STPush(&s, 2);STPop(&s);//邊進(jìn)邊出STPush(&s, 3);STPush(&s, 4);//printf("%d\n", STTop(&s));//STPop(&s);//printf("%d\n", STTop(&s));//STPop(&s); //STPop(&s);//printf("%d\n", STTop(&s));//STPop(&s);//STPop(&s);while (!STEmpty(&s))//返回假(0),返回的結(jié)果為假 就運(yùn)行{printf("%d ", STTop(&s));STPop(&s);}
}
int main()
{STTest();return 0;
}

總結(jié)：

1. 棧的整體不算難，學(xué)會(huì)理解后要獨(dú)立完成聯(lián)系
2. 棧也是有應(yīng)用場(chǎng)景的，至于為什么有這些結(jié)構(gòu)體，都是前人發(fā)明出來的，學(xué)習(xí)知識(shí)有延后性；意思就是說從小到大不是學(xué)習(xí)的所有知識(shí)都是有用的，但是也要學(xué)
3. 這個(gè)時(shí)候就體現(xiàn)了，筆記和博客的重要性；方便后續(xù)復(fù)習(xí)，知識(shí)多了肯定記不住