1.概念

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

2.棧的實現(xiàn)

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

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

2.1初始化，銷毀

1. 這里的關鍵問題點在于，初始化為0(下標位置) 的時候你要不要放入數(shù)據(jù)？，可是初始化本來就不用放數(shù)據(jù)
2. 在top位置放數(shù)據(jù)的時候，需要 top++指向下一個地方，為下一個準備放數(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);//刪除元素不行銷毀，因為數(shù)組的空間是一次性開辟的ps = NULL;
}

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

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

//壓棧
void STPush(ST* ps,STDataType x)
{assert(ps);//為NULL，你插入個屁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，只有一行可不可不調用函數(shù)，刪除數(shù)據(jù)呢？不行；因為沒有斷言檢查了
2. 這里直接有效個數(shù)，top-- 就行
3. 入棧順序不代表出棧順尋，可以邊進變出，或者入3個在途中出兩個
4. 進棧順序只有一種，出棧順序有很多種
5. 

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

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

//有效個數(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];//因為是有效元素的前一個
}

bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;//表達式為真返回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;//有效個數(shù)
}ST;//初始化和銷毀
void STInit(ST* ps);
void STDestroy(ST* ps);//壓棧和出棧
void STPush(ST* ps, STDataType x);
void STPop(ST* ps);//棧頂元素
STDataType STTop(ST* ps);//有效個數(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，你插入個屁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];//因為是有效元素的后一個
}
//銷毀
void STDestroy(ST* ps)
{assert(ps);ps->top = ps->capacity = 0;free(ps);//刪除元素不行銷毀，因為數(shù)組的空間是一次性開辟的ps = NULL;
}
//有效個數(shù)
int STSize(ST* ps)
{assert(ps);return ps->top;
}
//判空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;//表達式為真返回1，假返回0
}

2.4.3test.c

#include "Stack.h"
void STTest()
{ST s;STInit(&s);//壓棧STPush(&s, 1);STPush(&s, 2);STPop(&s);//邊進邊出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),返回的結果為假 就運行{printf("%d ", STTop(&s));STPop(&s);}
}
int main()
{STTest();return 0;
}

總結：

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