個人主頁，點這里~
數據結構專欄，點這里~

一、棧

1、棧的概念及結構

棧：?種特殊的線性表，其只允許在固定的?端進行元素的插入和刪除元素操作。進行數據插入和刪除操作的?端稱為棧頂，另?端稱為棧底。棧中的數據元素遵守后進先出LIFO（Last In First Out）的原則。
壓棧：棧的插入操作叫做進棧/壓棧/入棧，入數據在棧頂。
出棧：棧的刪除操作叫做出棧。出數據也在棧頂。

以上這張圖片很好的反映了棧的結構，及出入棧的順序。

2、棧的實現

棧的實現?般可以使用數組或者鏈表實現，相對而言數組的結構實現更優?些。因為數組在尾上插入，數據的代價比較小。數組在尾上插入整型數據只需要增加4個字節，但鏈表增加的字節就大的多了。

typedef int STDataType;
typedef struct Stack
{STDataType* arr;int top;     //指向棧頂位置int capacity;//數據容量
}ST;

3、初始化棧和銷毀棧

我們已經知道用什么方法實現棧，并且已經將棧的結構寫出來了，接下來就該初始化了。
初始化：

void StackInit(ST* ps)
{ps->arr = NULL;ps->top = 0;ps->capacity = 0;
}

初始化棧十分簡單，只需把arr數組置為空，棧頂top和容量capacity置為0即可。

銷毀：

void StackDestroy(ST* ps)
{if (ps->arr)//如果不為NULL{ps->arr = NULL;}ps->top = ps->capacity = 0;
}

以上就是棧的初始化以及銷毀的代碼了，和我們講順序表的時候差不多。

4、打印棧的數據

void SPrint(ST* ps)
{assert(ps);for (int i = 0;i < ps->top;i++){printf("%d", ps->arr[i]);if (i < ps->top - 1){printf("->");}}
}

5、入棧操作—棧頂

我們知道棧只能從棧頂入數據和出數據，所以我們就大概知道如何入棧了。

//入棧---棧頂
void StackPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity)//如果棧空間滿了就增容{int newcapacity = ps->capacity == 0 ? 4 : 2 * ps -> capacity;STDataType* set = (STDataType*)realloc(ps->arr,sizeof(STDataType) * newcapacity);if (set == NULL){perror("realloc fail!");return 1;}ps->arr = set;ps->capacity = newcapacity;}ps->arr[ps->top++] = x;
}

以上是入棧的代碼，但在入棧之前呢，我們要考慮棧空間是不是滿了，也就是棧頂是不是和容量一樣大，如果滿了，我們需要增容，在進行增容之前，我們還要考慮top和capacity是不是都為0，如果為0的話，我們要把容量大小置為4，否則的話容量擴大為二倍。

測試代碼：

#include "Stack.h"void test()
{ST plist;StackInit(&plist);StackPush(&plist, 1);StackPush(&plist, 2);StackPush(&plist, 3);SPrint(&plist);
}int main()
{test();return 0;
}

測試結果：

6、出棧—棧頂

在實現出棧之前我們要考慮棧里面的元素是否為空，如果為空就終止操作，所以我們先寫一個判空函數，這樣我們就可以在出棧之前知道棧是否為空了。

6.1棧是否為空

bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}

這里用到了bool類型記得要加上#include<stdbool.h>頭文件。

6.2出棧—棧頂

void StackPop(ST* ps)
{assert(!StackEmpty(ps));ps->top--;
}

這里實現出棧是只需要實現top減一即可，因為我們不會訪問top之后的元素。

7、取棧頂元素

STDataType StackTop(ST* ps)
{assert(!StackEmpty(ps));return ps->arr[ps->top - 1];
}

這里取棧頂元素時，我們只需要判斷一下棧是否為空，再將棧頂元素返回即可。

8、獲取棧中有效的元素個數

int StackSize(ST* ps)
{return ps->top;
}

以上就是棧的常見操作，接下來讓我們做一道練習題試一下吧！

二、棧的相關練習

1、練習

題目描述：

題目鏈接，點擊這里~

沒有做過的，可以先看題目思考一下，下面會給出題解。

我們根據題目描述可以知道題目讓我們判斷括號匹配是否正確，如果正確返回true，如果錯誤返回false。
我們在利用棧思想(先進后出)進行求解的時候，可以當遇到左括號讓它入棧，然后再遇到右括號的時候讓棧頂的和它匹配(在括號匹配的情況下，最后出現的左括號總與最先出現的右括號匹配)，如果不匹配就一定是非法的，返回false，如果都匹配的話就是合法的，返回true。這里可以用數組模擬棧。我們在遇到左括號例如'('時我們可以在棧中保存')'，這樣在比較的時候容易比較。

• 特殊情況一：
  字符數目是奇數，只要是奇數就一定不匹配，直接返回false。

    int len=strlen(s);if(len%2==1){return false;}

• 特殊情況二：
  如果全是左括號，那么最后棧頂top一定大于0，而如果是正確匹配的情況下，到最后top肯定是0。因為我們初始化top為0。所以遇到top大于0的情況直接返回false。

    //到最后top大于0的情況if(top>0){return false;}

• 如果全是右括號，那么在比較的時候，top一定為0，此時棧中沒有元素，也就無法比較，所以遇到比較時top為0的情況也直接返回false。

            if(top==0||s[i]!=stack[--top]){return false;}

2、AC代碼

AC代碼：

bool isValid(char* s) 
{int len=strlen(s);if(len%2==1){return false;}char stack[10005];int top=0;int i;for(i=0;i<len;i++){if(s[i]=='('){stack[top++]=')';}else if(s[i]=='['){stack[top++]=']';}else if(s[i]=='{'){stack[top++]='}';}else{if(top==0||s[i]!=stack[--top]){return false;}}}if(top>0){return false;}return true;
}

總結：
以上就是本期博客分享的全部內容啦！如果覺得文章還不錯的話可以三連支持一下，你的支持就是我前進最大的動力！
技術的探索永無止境! 道阻且長，行則將至！后續我會給大家帶來更多優質博客內容，歡迎關注我的CSDN賬號，我們一同成長！
(～￣▽￣)～