🚩前言

前面記錄了關于順序表和鏈表的數據結構，這一篇文章就來說一下“棧”這一個數據結構。當然不是什么龍門客棧了哈哈。接下來就來實現一下棧這個結構吧，并用實例來展示棧的應用！?

1、棧的概念

棧 :一種特殊的線性表，在存儲數據的時候和順序表以及單鏈表有所區別。我們通過圖來展示：

2、棧的實現框架

3、棧的代碼實現

該棧的實現是用順序表的結構，模擬實現棧。

3.1、棧的初始化和銷毀

void STInit(ST* pst)
{assert(pst);pst->a = NULL;//此處可以給空間，也可以先不給，//在插入的時候再給。pst->capacity = 0;pst->size = 0;
}void STDestory(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->capacity = 0;pst->size = 0;
}

3.2、入棧\出棧\返回棧頂元素\元素個數\判空

void STPush(ST* pst, STDataType data)
{assert(pst);if (pst->top == pst->capacity){int NewCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;STDataType* tmp = (STDataType*)realloc(pst->a,NewCapacity*sizeof(STDataType));if (tmp == NULL){perror("STPush::realloc fail!");return;}else{pst->a = tmp;pst->capacity = NewCapacity;}}pst->a[pst->top++]=data;
}void STPop(ST* pst)
{assert(pst && pst->top > 0);pst->top--;
}STDataType STTop(ST* pst)
{assert(pst&&pst->top);return pst->a[pst->top - 1];
}int STSize(ST st)
{assert(&st);return st.top;
}bool STEmpty(ST st)
{assert(&st);return st.top == 0;
}

3.3、棧定義注意事項

①對于top初值的大小：

4、棧的應用實例——《括號匹配問題》

oj括號匹配問題

思路：
①首先括號匹配需要考慮兩個點：數量上匹配和方向上匹配（左括號要匹配右括號）。
②利用棧結構實現該題：只要是左括號（全部類型的），就入棧；如果遇到右括號，則出棧頂元素（也就是和棧頂左括號進行匹配）。在這我們直接判斷不匹配是情況，就是只判斷不匹配情況，匹配的情況不用管。
代碼如下：

bool isValid(char* s) {ST st;STInit(&st);while(*s!='\0'){if((*s=='(') || (*s=='{') || (*s=='[')){STPush(&st,*s);}else{if(STEmpty(&st)){return false;STDestory(&st);}DataType ret=GetTopElement(&st);STPop(&st);if((ret == '(' && *s != ')')||(ret == '{' && *s != '}')||(ret == '[' && *s != ']')){return false;}}s++;}return STEmpty(&st);STDestory(&st);
}