棧

1 棧的概念與結構

棧是一種特殊的線性表，特殊在于其規定只允許在棧固定的一端進行數據插入和刪除操作。數據插入和刪除數據元素的一端叫做棧頂，另一端叫做棧底。棧中的元素遵從先進后出的原則。（我們可以把棧看成槍的彈夾，先壓入的子彈后擊發，后壓入的子彈先擊發）
壓棧：棧的插入操作叫做壓棧/進棧/入棧，入數據在棧頂。
出棧：棧的刪除操作叫做出棧，出數據也在棧頂。
本章使用數組來實現棧。

代碼定義如下：

typedef int STDatatype;//對棧中存入的元素類型進行重命名，避免修改時誤操作typedef struct Stack
{STDatatype* c;//所存入棧中的數據int top;//表示指向棧頂元素位置or棧頂數據的下一個位置int capacity;//表示棧的容量
}ST;

在上面代碼中我們對在的每個節點中定義了三個變量，對于top這一項較為特殊，下文2.1中會對兩種情況進行闡述。

2 棧的初始化和銷毀

2.1 棧的初始化

我們應知在創建出一個新的棧后，這個新的棧應是一個空棧，如此也就意味著指向存儲數據的指針STDatatype* c = NULL，表示容量的int capacity = 0。但對于top我們不能輕率的認為top == 0表示空棧時top所指向的是棧頂數據，如果這么認為的話會對后面的操作造成誤導（比如對棧判空）。因為top既然在等于0時表示棧為空棧，而且top還指向著棧頂數據，那么此時在索引為0處（即top == 0處 ）就應當存放有具體數據，然而此時棧卻是空的，所以當top == 0表示空棧時top就不能指向著棧頂數據，而是指向棧頂數據的下一個位置。 反之同理，若想讓top指向棧頂數據，則top == -1時才可表示空棧。（魚和熊掌不可兼得，表示空棧為魚，指向棧頂數據為熊掌）
如圖所示：

//棧的初始化
void STInit(ST* pst)
{assert(pst);pst->c = NULL;//top指向棧頂數據的下一個位置pst->top = 0;//top指向棧頂數據//pst->top = -1;pst->capacity = 0;
}

我們之所以選擇top指向棧頂元素的下一個位置這種定義，一是因為在諸多程序中變量為零都是判空的條件，如此設置有助于代碼的一致性與可讀性。二是因為top如此一來就可以等同于capacity的作用，直接反映棧中元素數量。三是因為簡化了棧的判空并且減少了對棧邊界的檢查，top == 0時棧為空；最大容量為n時，top == n表示棧滿。無需額外檢查。

2.2 棧的銷毀

由于本文中的棧是使用數組完成實現，故棧的銷毀與順序表的銷毀一致。首先使用assert對數組斷言（確定傳參有效），然后釋放掉動態內存，最后將top與capacity均置為0。
代碼如下：

void STDestroy(ST* pst)
{assert(pst);free(pst->c);//釋放動態內存pst->c = NULL;//首地址置為空pst->top = pst->capacity = 0;
}

3 入棧函數與出棧函數

3.1 入棧函數

經過初始化函數對棧進行操作后，數組為空，容量為零。所以在將數據壓入棧中之前，我們要先對數組的容量進行檢測，檢查容量是否已滿。如果滿了，我們就進行擴容操作；反之，我們就直接插入即可。
對于內存函數的選擇方面，由于擴容時會存在原本棧容量已經滿的情況，此時不僅要擴大內存塊，還要保留棧中原本的數據，所以應當選擇realloc。

void STPush(ST* pst, STDatatype x)
{assert(pst);//擴容if (pst->c == pst->capacity){int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;STDatatype* tmp = (STDatatype*)realloc(pst->c, newcapacity * sizeof(STDatatype));if (tmp == NULL){perror("realloc fail !");return;}pst->c = tmp;pst->capacity = newcapacity;}//擴容完畢后插入數據pst->c[pst->top] = x;//將數據插入到棧頂//注意這里要做出區分//此時top == 0 這個位置就是棧頂//但是top的指向是棧頂數據的下一個位置pst->top++;
}

3.2 出棧函數

出棧的操作只要在邏輯結構上將出棧數據移除即可，也就是通過索引top的加減完成出棧操作。此時有人可能會有疑問，既然其在物理結構上還存在于數組的內存塊中，那么不會對棧滿的判斷造成影響嗎？
因為我們在對top定義時，將其定義為指向棧頂數據的下一個位置，如此top==0就表示了空棧，top就表示棧中有幾個數據，所以不會對棧滿的判斷造成影響。此外，當我們進行一次出棧后，出棧的數據雖然仍存在于數組的物理結構中，但是在下一次進行壓棧操作后，剛才出棧數據的位置就會分配給新壓入棧的數據，出棧的數據被新壓入棧的數據覆蓋掉。

void STPop(ST* pst)
{assert(pst);assert(pst->top > 0);//top表示棧中數據個數//當top==0時，棧已經成空棧，不能再進行出棧操作pst->top--;
}

4 取棧頂數據，獲取數據個數 和 判空函數

4.1 取棧頂數據與獲取數據個數

4.1.1 取棧頂數據

因為top是指向棧頂數據的下一個位置，所以要想獲得棧頂數據，索引應當等于top - 1。

代碼如下：

STDatatype STTop(ST* pst)
{assert(pst);//確保傳參有效assert(pst->top > 0);//確保棧不為空return pst->c[pst->top - 1];//top - 1為棧頂數據
}

4.1.2 獲取數據個數

top就代表著棧中的數據個數，所以直接返回top即可。
代碼如下：

int STsize(ST* pst)
{assert(pst);return pst->top;
}

4.2 判空函數

根據我們前面的定義，top == 0時為空棧。所以判空過程中如果top等于零就是真（true），top不等于0就是假（false）。故我們將返回值類型設置為布爾類型，便于直觀表現判空結果。
代碼如下：

bool STEmpty(ST* pst)
{assert(pst);return pst->top == 0;
}

5 真題實戰（有效的括號）

輸出樣例：

這個題當中我們之所以選擇用棧來解答就是因為棧獨特的后進先出的特性，根據題目要求我們可以得出每個右括號都要與最近的未閉合的左括號匹配，那么每當識別到左括號就將其壓入棧中，當識別到右括號時就將剛壓入棧的左括號出棧頂與之匹配，如果不匹配也就意味著字符串非有效。
按照上述思路我們來完成實現（前提是上文中棧的基本結構已經編寫完畢）：
初階版：

//因輸出結果為true與false，故返回值類型定位布爾類型
bool isValid(char* s) {ST st;STInit(&st);while(*s){//識別括號，是左括號入棧if(*s == '(' || *s == '[' || *s == '{'){STPush(&st , *s);}//不是左括號是右括號，剛進棧的左括號出棧頂與右括號匹配else{//取棧頂元素char top = STTop(&st);//出棧頂STPop(&st);//匹不匹配只需看不匹配情況即可，如果匹配就繼續執行循環，不匹配直接結束函數if(top == '(' && *s != ')'|| top == '[' && *s != ']'|| top == '{' && *s != '}'){STDestroy(&st);//即使不匹配也要及時銷毀棧，避免內存泄漏return false;}}//每完成一次壓棧或出棧操作字符串數組索引向后移一位++s;}return true;
}

提交后發現給出的四個樣例均可通過，但當字符串中只有一個"["時，運行結果錯誤。
這是因為左括號數量比右括號多，當最后一個左括號被壓入棧中之后，沒有右括號與其匹配，左括號依然存在于棧中。而程序運行完并沒有對棧中進行判空，所以結果出錯。
修改后：

//因輸出結果為true與false，故返回值類型定位布爾類型
bool isValid(char* s) {ST st;STInit(&st);while(*s){//識別括號，是左括號入棧if(*s == '(' || *s == '[' || *s == '{'){STPush(&st , *s);}//不是左括號是右括號，剛進棧的左括號出棧頂與右括號匹配else{//取棧頂元素char top = STTop(&st);//出棧頂STPop(&st);//匹不匹配只需看不匹配情況即可，如果匹配就繼續執行循環，不匹配直接結束函數if(top == '(' && *s != ')'|| top == '[' && *s != ']'|| top == '{' && *s != '}'){STDestroy(&st);return false;}}//每完成一次壓棧或出棧操作字符串數組索引向后移一位++s;}//匹配完如果棧不為空，說明左括號比右括號多，數量不匹配bool ret = STEmpty(&st);STDestroy(&st);return ret;
}

再次提交發現仍然存在報錯，當字符串中只有一個"]"時，運行結果錯誤。

由于沒有左括號壓入棧中，所以在取棧頂元素時就觸發了assert斷言的報錯。
故在取棧頂元素之前，也應對棧進行判空操作。
最終修改后：

//因輸出結果為true與false，故返回值類型定位布爾類型
bool isValid(char* s) {ST st;STInit(&st);while(*s){//識別括號，是左括號入棧if(*s == '(' || *s == '[' || *s == '{'){STPush(&st , *s);}//不是左括號是右括號，剛進棧的左括號出棧頂與右括號匹配else{//如果棧為空，字符串只有一個右括號if( STEmpty(&st) ){STDestroy(&st);return false;}//如果棧不為空，進行匹配//取棧頂元素char top = STTop(&st);//出棧頂STPop(&st);//匹不匹配只需看不匹配情況即可，如果匹配就繼續執行循環，不匹配直接結束函數if(top == '(' && *s != ')'|| top == '[' && *s != ']'|| top == '{' && *s != '}'){STDestroy(&st);return false;}}//每完成一次壓棧或出棧操作字符串數組索引向后移一位++s;}//匹配完如果棧不為空，說明左括號比右括號多，數量不匹配bool ret = STEmpty(&st);STDestroy(&st);return ret;
}

提交通過，題目解答完畢。

全文至此結束！！！
寫作不易，不知各位老板能否給個一鍵三連或是一個免費的贊呢(▽)(▽)，這將是對我最大的肯定與支持！！！謝謝！！！(▽)(▽)