前言

本屆開始我們將對數據結構中棧的內容進行講解,那么廢話不多說,我們正式進入今天的學習

棧

棧是一種很特殊的線性表，它只能在固定的一端進行插入和刪除操作，進行數據的插入和刪除的一端叫做棧頂，另外一端叫做棧底，棧中的元素遵守后進先出的原則。

壓棧：即數據的插入操作，在棧頂進行

出棧：即數據的刪除操作，在棧頂進行

棧在內存中普遍采用順序的存儲結構，但是鏈式的存儲結構也同樣可行。因為在鏈式結構中尋找尾節點的時間較長，所以一般采取反向+頭插入的操作來完成鏈式的存儲，或者采用雙向鏈表，但是不推薦，因為多一個向前的指針，會更加麻煩。本節僅對順序存儲結構進行講解。兩種存儲方式各有優缺點(鏈式：沒有擴容的消耗，更加節省空間? ? ? ? 順序：CPU高速緩存，效率更高)

「順序表數據存儲在連續的物理空間中，當CPU訪問數據時，整個數據塊可一次性加載到高速緩存中」

棧的基本存儲結構

棧的基本存儲結構如下所示（動態）：

其中的top（棧頂）也可以稱作size，a是棧的指針，capacity是棧的容量

棧的初始化和銷毀

通過在C語言時期我們對指針的學習，我們可以知道：在初始化的函數之中，如果僅僅采取傳值操作，形式參數的改變不會影響到實際參數，所以我們在初始化和銷毀棧的過程之中要采取傳地址的操作

在初始化棧的開頭，我們需要加入assert進行斷言，若為空則不采取操作

在數組開空間這一個步驟上，我們可以采取兩種措施：第一種是開幾個小的空間，后續再擴容；第二種是在初始化階段先不進行空間的開辟，后續在處理的時候在開辟空間

（這里的代碼采取的是不開辟空間，采用兩種方法都是可以的）

棧的銷毀代碼非常簡單，這里就不做過多的解釋：

??

棧的入棧和出棧

棧的數據插入不像順序表和鏈表一樣，有頭插入和尾插入。因為棧只能夠在一端進行插入和刪除，所以棧的操作只有壓棧操作。

對于入棧的函數，我們需要用到的參數有：一個結構體指針pst、待插入的數據x

在開始書寫棧的入棧代碼之前，我們需要先明確一下top初始化時的指向。top的指向有兩種：一種是指向棧頂元素，另外一種是指向棧頂數據下一個數據。(模擬實現的演示代碼采取的是指向下一位)

當top指向當前元素的時候，如果棧中沒有任何元素的時候，top的值應該要賦值為-1

這兩種指向的方式都是可以的，采取不同的指向方式時初始化top對應的賦值情況也不同：

假設我們采用的是第二種方法,那么我們在進行入棧時的操作就是:

pst->a[pst->top] = x;
pst->top++;

而如果我們采取的是第一種方法,我們就需要讓top先++再放入數據x?

接下來就是判斷空間是否滿了，滿了的話就執行擴容操作。同樣的，top在初始化時的指向不同時，判滿的條件也不同。演示代碼采取的是指向下一個元素的指向方法，所以判滿的條件就是top等于capacity時:

void STPush(ST* pst, STDataType x)
{assert(pst);//擴容if(pst->top == pst->capacity){int newcapacity = 2 * pst->capacity;STDataType* tmp = realloc(pst->a, newcapacity * sizeof(STDataType));if(tmp == NULL){perror("realloc fail");}pst->a = tmp;pst->capacity = newcapacity;}pst->a[pst->top++] = x;
}

這里我故意提供了一個錯誤的代碼,看看能不能發現問題

這里的代碼存在的問題是:我們在初始化棧的時候采取了兩種方式,第一種就是先給棧開辟一點小空間,此時采用這樣的代碼是不存在問題的,因為此時的capacity有數值;但是當我們采取第二種方法時,即不給棧開辟空間時,此時的capacity大小就是0,此時我們在newcapacity中的*2操作就會無效,所以我們在對new capacity進行操作的時候先需要判斷一下capacity當前的大小:

int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;

那么假設棧一開始為空,此時的a也指向的是NULL,這樣使用realloc會不會出現問題呢?答案是不會的,我們來查看一下realloc的使用說明:

從文檔中我們可以清晰的看出,當指向的指針是空的時候,realloc函數相當于malloc函數

那么到此為止,入棧的代碼就已經全部實現完成了,接下來我們來完成一下出棧的代碼:

void STPop(ST* pst)
{assert(pst);pst->top--;
}

?到這里我們可能會有疑問,為什么STPop這短短的幾行代碼還需要封裝成一個函數,為什么不能在使用的時候直接將代碼寫出來呢?就如同下面的代碼一樣:

    ST st;STInit(&st);STPush(&st, 1);STPush(&st, 2);STPush(&st, 3);STPush(&st, 4);STPop(&st);STPop(&st);STPop(&st);STPop(&st);//st.top--;

采取這樣的方法其實也是可以的,但是這樣會影響程序的可讀性,所以這里不建議采取這樣的形式.包括訪問棧頂元素STTop中也建議采取封裝的形式,不要直接訪問:

STDataType STTop(ST* pst)
{assert(pst);assert(pst->top > 0);return pst->a[pst->top - 1];
}

我們自己直接去訪問棧頂元素可能會出現錯誤,我們可能會忘記一開始設置top指針設置初始化的指向,導致不知道到底top是棧頂元素還是top-1是棧頂元素,如果直接將它封裝成一個函數,就不會存在這樣的問題

棧的其他接口實現

接下來我們來實現一下棧的判空操作,由于實現的邏輯非常簡單,這里就不做過多地講解了:

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

接下來是返回棧的元素個數的接口:

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

因為棧的邏輯結構非常特殊,是采取的先進先出的結構,我們就不能采用類似于順序表和鏈表那樣的訪問方式來訪問棧.要想訪問棧中的所有元素,我們就需要先用STTop來訪問棧頂元素,然后執行STPop來刪除棧頂元素,接著繼續訪問棧頂元素,一直循環到棧的元素為空為止

    while(!STEmpty(&st)){printf("%d ", STTop(&st));STPop(&st);}

但是采取這樣的訪問方式仍然存在一個問題:當我們訪問完一次棧以后,棧里面所有的元素都被清空了,不便于我們后續的操作

其實這樣的操作是合理的,我們期望的就是訪問完棧中的某一個元素以后,后續就不能訪問到這個元素了,這一點我們在后續的習題中會體現出來

練習題:有效的括號

我們來看一下這個練習題的題目:

剛看到這個題目的時候,我們最直接的思路就是數不同括號的數量,但其實這么做是沒有用的,我們來舉一個反例:"[([)]]",這組反例的數量是匹配的,但是它并不有效.所以這樣的思路顯然是不行的,在滿足數量匹配的同時我們也要滿足順序的匹配

我們先來考慮一下什么時候需要考慮到括號匹配的問題:當我們取到右括號的時候我們才會需要考慮到括號匹配的問題,我們取到左括號的時候只需讓他存入即可

結合這樣的特征我們就可以考慮用棧來解決這個問題,當讀取到左括號的時候只需要將其存入棧中即可.當讀取到右括號的時候,因為最近的左括號在棧頂,我們就要它和最近的左括號匹配一下,如果匹配成功就讓左括號也出棧

在寫代碼的時候我們需要注意,我們在確定是否匹配的時候判斷的條件是不匹配就跳出,而不是判斷匹配,因為就算是匹配了也需要進入下一次的檢查:

            if((top == '(' && *s != ')') || (top == '[' && *s != ']') || (top == '{' && *s != '}'))return 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 != '}'))return false;}++s;}STDestory(&st);return true;
}

當我們在提交代碼的時候可以發現在某些情況下代碼還是存在一定的問題:

?在這樣的情況之下,確實是不存在不匹配的問題,但是棧里面還有數據沒有處理完,此時就意味著棧中還有左括號沒有任何右括號供它匹配,說明左右括號的數量是不相等的,所以我們此時還需要加上判空的操作:

    //棧不為空bool ret = STEmpty(&st);STDestory(&st);return ret;

我們再運行一下代碼,發現還是存在問題,這里出現了一個斷言錯誤:

這里的意思是棧為空了以后我們還在調用棧,我們結合這里的測試用例來看一下:

這里給的用例是單獨的一個右括號,所以會直接在棧中向前查找,尋找最近的左括號與之匹配,但由于棧中只有一個元素,所以此時再去向前查找就會導致越界,所以這里發生了斷言錯誤.所以我們在判斷右括號的時候還要加入一個判空的條件:

bool isValid(char* s)
{ST st;STInit(&st);while(*s){if(*s == '(' || *s == '[' || *s == '{') STPush(&st, *s);else{if(STEmpty(&st)) return false;char top = STTop(&st);STPop(&st);if((top == '(' && *s != ')') || (top == '[' && *s != ']') || (top == '{' && *s != '}'))return false;}++s;}//棧不為空bool ret = STEmpty(&st);STDestory(&st);return ret;
}

修改完以后程序就沒有問題了,但是如果我們仔細觀察還是可以發現一些小的問題:可能會存在內存泄漏

假設棧中左括號的數量多于右括號的數量,在程序結束的時候就走不到后面的STDestory就已經直接返回了,此時就會存在內存泄漏.雖然這個并不會有太大的影響,但是我們還是要養成良好的習慣.

所以在這里,只要提前就false返回了,我們就對其執行STDestory:

            if(STEmpty(&st)){STDestory(&st);return false;}

            if((top == '(' && *s != ')') || (top == '[' && *s != ']') || (top == '{' && *s != '}')){STDestory(&st);return false;}

結尾

那么到此為止有關棧的內容就已經結束了,希望該文章可以給你帶來幫助,下一節將對隊列的內容進行梳理,謝謝你的瀏覽!!!!