零、前言

??「 資料結構 」 和 「 演算法 」 是密不可分的，兩者往往是「 相輔相成 」的存在，所以，在學習 「 資料結構 」 的程序中，不免會遇到各種「 演算法 」，
??到底是先學 資料結構 ，還是先學 演算法，我認為不必糾結這個問題，一定是一起學的，
??資料結構 常用的操作一般為：「 增 」「 刪 」「 改 」「 查 」，基本上所有的資料結構都是圍繞這幾個操作進行展開的，
??那么這篇文章，作者將用 「 九張動圖 」 來闡述一種 「 后進先出 」 的資料結構

「 堆疊 」


🙉飯不食，水不飲，題必須刷🙉

C語言免費動漫教程，和我一起打卡！ 🌞《光天化日學C語言》🌞
LeetCode 太難？先看簡單題！ 🧡《C語言入門100例》🧡
資料結構難？不存在的！ 🌳《畫解資料結構》🌳
LeetCode 太簡單？演算法學起來！ 🌌《夜深人靜寫演算法》🌌
?? 堆疊可以用 順序表 實作，也可以用 鏈表 實作，濃縮為以下兩張圖：

??看不懂沒有關系，我會把它拆開來一個一個講，首先來看一下今天要學習的內容目錄，

一、概念

1、堆疊的定義

??堆疊 是僅限在 表尾 進行 插入 和 洗掉 的 線性表，
??堆疊 又被稱為 后進先出 （Last In First Out） 的線性表，簡稱 LIFO ，

2、堆疊頂

??堆疊 是一個線性表，我們把允許 插入 和 洗掉 的一端稱為 堆疊頂，

3、堆疊底

??和 堆疊頂 相對，另一端稱為 堆疊底，實際上，堆疊底的元素我們不需要關心，

二、介面

1、可寫介面

1）資料入堆疊

??堆疊的插入操作，叫做 入堆疊，也可稱為 進堆疊、壓堆疊，如下圖所示，代表了三次入堆疊操作：

2）資料出堆疊

??堆疊的洗掉操作，叫做 出堆疊，也可稱為 彈堆疊，如下圖所示，代表了兩次出堆疊操作：

3）清空堆疊

??一直 出堆疊，直到堆疊為空，如下圖所示：

2、只讀介面

1）獲取堆疊頂資料

??對于一個堆疊來說只能獲取 堆疊頂 資料，一般不支持獲取 其它資料，

2）獲取堆疊元素個數

??堆疊元素個數一般用一個額外變數存盤，入堆疊 時加一，出堆疊 時減一，這樣獲取堆疊元素的時候就不需要遍歷整個堆疊，通過 O ( 1 ) O(1) O(1) 的時間復雜度獲取堆疊元素個數，

3）堆疊的判空

??當堆疊元素個數為零時，就是一個空堆疊，空堆疊不允許 出堆疊 操作，

三、堆疊的順序表實作

1、資料結構定義

對于順序表，在 C語言 中表現為 陣列，在進行 堆疊的定義 之前，我們需要考慮以下幾個點：
??1）堆疊資料的存盤方式，以及堆疊資料的資料型別；
??2）堆疊的大小；
??3）堆疊頂指標；

• 我們可以定義一個 堆疊 的 結構體，C語言實作如下所示：

#define DataType int        // (1)
#define maxn 100005         // (2)

struct Stack {              // (3)
    DataType data[maxn];    // (4)
    int top;                // (5)
};

• ( 1 ) (1) (1) 用DataType這個宏定義來統一代表堆疊中資料的型別，這里將它定義為整型，根據需要可以定義成其它型別，例如浮點型、字符型、結構體 等等；
• ( 2 ) (2) (2) maxn代表我們定義的堆疊的最大元素個數；
• ( 3 ) (3) (3) Stack就是我們接下來會用到的 堆疊結構體；
• ( 4 ) (4) (4) DataType data[maxn]作為堆疊元素的存盤方式，資料型別為DataType，可以自行定制；
• ( 5 ) (5) (5) top即堆疊頂指標，data[top-1]表示堆疊頂元素，top == 0代表空堆疊；

2、入堆疊

1、影片演示

??如圖所示，藍色元素 為原本在堆疊中的元素，紅色元素 為當前需要 入堆疊 的元素，執行完畢以后，堆疊頂指標加一，具體來看下代碼實作，

2、原始碼詳解

• 入堆疊 操作，算上函式引數串列，總共也才幾句話，代碼實作如下：

void StackPushStack(struct Stack *stk, DataType dt) { // (1)
    stk->data[ stk->top ] = dt;                       // (2)
    stk->top = stk->top + 1;                          // (3)
}

• ( 1 ) (1) (1) stk是一個指向堆疊物件的指標，由于這個介面會修改堆疊物件的成員變數，所以這里必須傳指標，否則，就會導致函式執行完畢，傳參物件沒有任何改變；
• ( 2 ) (2) (2) 將傳參的元素放入堆疊中；
• ( 3 ) (3) (3) 將堆疊頂指標自增 1；
• 注意，這個介面在呼叫前，需要保證 堆疊頂指標 小于 堆疊元素最大個數，即stk->top < maxn，
• 如果 C語言 寫的熟練，我們可以把 ( 2 ) (2) (2) 和 ( 3 ) (3) (3) 合成一句話，如下：

void StackPushStack(struct Stack *stk, DataType dt) {
    stk->data[ stk->top++ ] = dt;                    
}

• stk->top++運算式的值是自增前的值，并且自身進行了一次自增，

3、出堆疊

1、影片演示

??如圖所示，藍色元素 為原本在堆疊中的元素，紅色元素 為當前需要 出堆疊 的元素，執行完畢以后，堆疊頂的指標減一，具體來看下代碼實作，

2、原始碼詳解

• 出堆疊 操作，只需要簡單改變將 堆疊頂 減一 即可，代碼實作如下：

void StackPopStack(struct Stack* stk) {
    --stk->top;
}

4、清空堆疊

1、影片演示

??如圖所示，對于陣列來說，清空堆疊的操作只需要將 堆疊頂指標 置為堆疊底，也就是陣列下標 0 即可，下次繼續 入堆疊 的時候會將之前的記憶體重復利用，

2、原始碼詳解

• 清空堆疊的操作只需要將 堆疊頂 指標直接指向 堆疊底 即可，對于順序表，也就是 C語言 中的陣列來說，堆疊底 就是下標 0 的位置了，代碼實作如下：

void StackClear(struct Stack* stk) {
    stk->top = 0;
}

5、只讀介面

• 只讀介面包含：獲取堆疊頂元素、獲取堆疊大小、堆疊的判空，實作如下：

DataType StackGetTop(struct Stack* stk) {
    return stk->data[ stk->top - 1 ];      // (1)
}
int StackGetSize(struct Stack* stk) {
    return stk->top;                       // (2)
}
bool StackIsEmpty(struct Stack* stk) {
    return !StackGetSize(stk);             // (3)
}

• ( 1 ) (1) (1) 陣列中堆疊元素從 0 開始計數，所以實際獲取元素時，下標為 堆疊頂元素下標 減一；
• ( 2 ) (2) (2) 因為只有在入堆疊的時候，堆疊頂指標才會加一，所以它 正好代表了 堆疊元素個數；
• ( 3 ) (3) (3) 當 堆疊元素 個數為 零 時，堆疊為空，

6、堆疊的順序表實作原始碼

• 堆疊的順序表實作的原始碼如下：

/************************************* 堆疊的順序表實作 *************************************/
#define DataType int
#define bool int
#define maxn 100010

struct Stack {
    DataType data[maxn];
    int top;
};

void StackClear(struct Stack* stk) {
    stk->top = 0;
}
void StackPushStack(struct Stack *stk, DataType dt) {
    stk->data[ stk->top++ ] = dt;
}
void StackPopStack(struct Stack* stk) {
    --stk->top;
}
DataType StackGetTop(struct Stack* stk) {
    return stk->data[ stk->top - 1 ];
}
int StackGetSize(struct Stack* stk) {
    return stk->top;
}
bool StackIsEmpty(struct Stack* stk) {
    return !StackGetSize(stk);
}
/************************************* 堆疊的順序表實作 *************************************/

四、堆疊的鏈表實作

1、資料結構定義

對于鏈表，在進行 堆疊的定義 之前，我們需要考慮以下幾個點：
??1）堆疊資料的存盤方式，以及堆疊資料的資料型別；
??2）堆疊的大小；
??3）堆疊頂指標；

• 我們可以定義一個 堆疊 的 結構體，C語言實作如下所示：

typedef int DataType;             // (1)
struct StackNode;                 // (2)
struct StackNode {                // (3)
    DataType data;
    struct StackNode *next;
};
struct Stack {                    
    struct StackNode *top;        // (4)
    int size;                     // (5)
};

• ( 1 ) (1) (1) 堆疊結點元素的 資料域，這里定義為整型；
• ( 2 ) (2) (2) struct StackNode;是對鏈表結點的宣告；
• ( 3 ) (3) (3) 定義鏈表結點，其中DataType data代表 資料域；struct StackNode *next代表 指標域；
• ( 4 ) (4) (4) top作為 堆疊頂指標，當堆疊為空的時候，top == NULL；否則，永遠指向堆疊頂；
• ( 5 ) (5) (5) 由于 求鏈表長度 的演算法時間復雜度是 O ( n ) O(n) O(n) 的， 所以我們需要記錄一個size來代表現在堆疊中有多少元素，每次 入堆疊時size自增，出堆疊時size自減，這樣在詢問堆疊的大小的時候，就可以通過 O ( 1 ) O(1) O(1) 的時間復雜度，

2、入堆疊

1、影片演示

??如圖所示，head 為堆疊頂，tail 為堆疊底，vtx 為當前需要 入堆疊 的元素，即圖中的 橙色結點，入堆疊 操作完成后，堆疊頂 元素變為 vtx，即圖中 綠色結點，

2、原始碼詳解

• 入堆疊 操作，其實就是類似 頭插法，往鏈表頭部插入一個新的結點，代碼實作如下：

void StackPushStack(struct Stack *stk, DataType dt) {
    struct StackNode *insertNode = (struct StackNode *) malloc( sizeof(struct StackNode) ); // (1)
    insertNode->next = stk->top;     // (2)
    insertNode->data = dt;           // (3)
    stk->top = insertNode;           // (4)
    ++ stk->size;                    // (5)
}

• ( 1 ) (1) (1) 利用malloc生成一個鏈表結點insertNode；
• ( 2 ) (2) (2) 將 當前堆疊頂 作為insertNode的 后繼結點；
• ( 3 ) (3) (3) 將 insertNode的 資料域 設定為傳參 dt；
• ( 4 ) (4) (4) 將insertNode作為 新的堆疊頂；
• ( 5 ) (5) (5) 堆疊元素 加一；

3、出堆疊

1、影片演示

??如圖所示，head 為堆疊頂，tail 為堆疊底，temp 為當前需要 出堆疊 的元素，即圖中的 橙色結點，出堆疊 操作完成后，堆疊頂 元素變為之前 head 的 后繼結點，即圖中 綠色結點，

2、原始碼詳解

• 出堆疊 操作，由于鏈表頭結點就是堆疊頂，其實就是洗掉這個鏈表的頭結點的程序，代碼實作如下：

void StackPopStack(struct Stack* stk) {
    struct StackNode *temp = stk->top;  // (1)
    stk->top = temp->next;              // (2)
    free(temp);                         // (3)
    --stk->size;                        // (4)    
}

• ( 1 ) (1) (1) 將 堆疊頂指標 保存到temp中；
• ( 2 ) (2) (2) 將 堆疊頂指標 的 后繼結點 作為新的 堆疊頂；
• ( 3 ) (3) (3) 釋放之前 堆疊頂指標 對應的記憶體；
• ( 4 ) (4) (4) 堆疊元素減一；

4、清空堆疊

1、影片演示

??清空堆疊 可以理解為，不斷的出堆疊，直到堆疊元素個數為零，

2、原始碼詳解

• 對于鏈表而言，清空堆疊 的操作需要洗掉每個鏈表結點，代碼實作如下：

void StackClear(struct Stack* stk) {
    while(!StackIsEmpty(stk)) {       // (1)
        StackPopStack(stk);           // (2)
    }
    stk->top = NULL;                  // (3)
}

• ( 1 ) (1) (1) - ( 2 ) (2) (2) 的每次操作其實就是一個 出堆疊 的程序，如果 堆疊 不為空；則進行 出堆疊 操作，直到 堆疊 為空；
• ( 2 ) (2) (2) 然后將 堆疊頂指標 置為空，代表這是一個空堆疊了；

5、只讀介面

• 只讀介面包含：獲取堆疊頂元素、獲取堆疊大小、堆疊的判空，實作如下：

DataType StackGetTop(struct Stack* stk) {
    return stk->top->data;                 // (1)
}
int StackGetSize(struct Stack* stk) {
    return stk->size;                      // (2)
}

int StackIsEmpty(struct Stack* stk) {
    return !StackGetSize(stk);
}

• ( 1 ) (1) (1) stk->top作為 堆疊頂指標，它的 資料域 data就是 堆疊頂元素的值，回傳即可；
• ( 2 ) (2) (2) size記錄的是 堆疊元素個數；
• ( 3 ) (3) (3) 當 堆疊元素 個數為 零 時，堆疊為空，

6、堆疊的鏈表實作原始碼

• 堆疊的鏈表實作原始碼如下：

/************************************* 堆疊的鏈表實作 *************************************/
typedef int DataType;

struct StackNode;
 
struct StackNode {
    DataType data;
    struct StackNode *next;
};

struct Stack {
    struct StackNode *top;
    int size;
};

void StackPushStack(struct Stack *stk, DataType dt) {
    struct StackNode *insertNode = (struct StackNode *) malloc( sizeof(struct StackNode) );
    insertNode->next = stk->top;
    insertNode->data = dt;
    stk->top = insertNode;
    ++ stk->size;
}
void StackPopStack(struct Stack* stk) {
    struct StackNode *temp = stk->top;
    stk->top = temp->next;
    --stk->size; 
    free(temp);
}

DataType StackGetTop(struct Stack* stk) {
    return stk->top->data;
}
int StackGetSize(struct Stack* stk) {
    return stk->size;
}

int StackIsEmpty(struct Stack* stk) {
    return !StackGetSize(stk);
}

void StackClear(struct Stack* stk) {
    while(!StackIsEmpty(stk)) {
        StackPopStack(stk);
    }
    stk->top = NULL; 
    stk->size = 0;
}
/************************************* 堆疊的鏈表實作 *************************************/

五、兩種實作的優缺點

1、順序表實作

??在利用順序表實作堆疊時，入堆疊 和 出堆疊 的常數時間復雜度低，且 清空堆疊 操作相比 鏈表實作 能做到 O ( 1 ) O(1) O(1)，唯一的不足之處是：需要預先申請好空間，而且當空間不夠時，需要進行擴容，擴容方式本文未提及，可以參考以下文章：《C/C++ 面試 100 例》（四）vector 擴容策略，

2、鏈表實作

??在利用鏈表實作堆疊時，入堆疊 和 出堆疊 的常數時間復雜度略高，主要是每插入一個堆疊元素都需要申請空間，每洗掉一個堆疊元素都需要釋放空間，且 清空堆疊 操作是 O ( n ) O(n) O(n) 的，直接將 堆疊頂指標 置慷訓導致記憶體泄漏，好處就是：不需要預先分配空間，且在記憶體允許范圍內，可以一直 入堆疊，沒有順序表的限制，

六、堆疊的入門

??好啦，接下來，讓我們做幾個堆疊的題目練習一下吧，

1、逆序鏈表

《LeetCode 206. 反轉鏈表》解題報告

2、括號匹配

《LeetCode 20. 有效的括號》解題報告
《LeetCode 32. 最長有效括號》解題報告

3、回文鏈表

《LeetCode 234. 回文鏈表》解題報告

4、運算式求值

《LeetCode 682. 棒球比賽》解題報告

5、雙堆疊判等

《LeetCode 844. 比較含退格的字串》解題報告

七、堆疊的進階

??堆疊的進階主要是單調堆疊相關的內容，可以參考我的另一篇文章：夜深人靜寫演算法（十一）- 單調堆疊，看完以后，別忘了進行相關題目的練習，

1、最小堆疊

《LeetCode 155. 最小堆疊》解題報告

2、化堆疊為隊

《LeetCode 232. 用堆疊實作佇列》解題報告

3、直方圖最大矩形

《LeetCode 84. 柱狀圖中最大的矩形》解題報告

• 關于 「 堆疊 」 的內容到這里就結束了，
• 如果還有不懂的問題，可以 「 想方設法 」找到作者的「 聯系方式 」 ，線上溝通交流，

• 有關🌳《畫解資料結構》🌳 的原始碼均開源，鏈接如下：《畫解資料結構》

🙉飯不食，水不飲，題必須刷🙉
C語言免費動漫教程，和我一起打卡！ 🌞《光天化日學C語言》🌞
LeetCode 太難？先看簡單題！ 🧡《C語言入門100例》🧡
資料結構難？不存在的！ 🌳《畫解資料結構》🌳
LeetCode 太簡單？演算法學起來！ 🌌《夜深人靜寫演算法》🌌