️《畫解數據結構》九個動圖全網最全棧的解讀️（建議收藏）

英雄哪裏出來 2021-08-15 16:51:09 阅读数:863

本文一共[544]字，预计阅读时长:1分钟~

最全收藏

零、前言

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

「棧」

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

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

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

一、概念

1、棧的定義

棧是僅限在錶尾進行插入和删除的 線性錶。
棧又被稱為後進先出（Last In First Out）的線性錶，簡稱 LIFO 。

2、棧頂

棧是一個線性錶，我們把允許插入和删除的一端稱為棧頂。

3、棧底

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

二、接口

1、可寫接口

1）數據入棧

棧的插入操作，叫做入棧，也可稱為進棧、壓棧。如下圖所示，代錶了三次入棧操作：

2）數據出棧

棧的删除操作，叫做出棧，也可稱為彈棧。如下圖所示，代錶了兩次出棧操作：
在這裏插入圖片描述

3）清空棧

一直出棧，直到棧為空，如下圖所示：

2、只讀接口

1）獲取棧頂數據

對於一個棧來說只能獲取棧頂數據，一般不支持獲取其它數據。

2）獲取棧元素個數

棧元素個數一般用一個額外變量存儲，入棧時加一，出棧時减一。這樣獲取棧元素的時候就不需要遍曆整個棧。通過 $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)$ 用DataType這個宏定義來統一代錶棧中數據的類型，這裏將它定義為整型，根據需要可以定義成其它類型，例如浮點型、字符型、結構體等等；
$(2)$ maxn代錶我們定義的棧的最大元素個數；
$(3)$ Stack就是我們接下來會用到的 棧結構體；
$(4)$ DataType data[maxn]作為棧元素的存儲方式，數據類型為DataType，可以自行定制；
$(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)$ stk是一個指向棧對象的指針，由於這個接口會修改棧對象的成員變量，所以這裏必須傳指針，否則，就會導致函數執行完畢，傳參對象沒有任何改變；
$(2)$ 將傳參的元素放入棧中；
$(3)$ 將棧頂指針自增 1；
注意，這個接口在調用前，需要保證 棧頂指針 小於 棧元素最大個數，即stk->top < maxn，
如果 C語言寫的熟練，我們可以把 $(2)$ 和 $(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)$ 數組中棧元素從 0 開始計數，所以實際獲取元素時，下標為棧頂元素下標减一；
$(2)$ 因為只有在入棧的時候，棧頂指針才會加一，所以它正好代錶了棧元素個數；
$(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)$ 棧結點元素的 數據域，這裏定義為整型；
$(2)$ struct StackNode;是對鏈錶結點的聲明；
$(3)$ 定義鏈錶結點，其中DataType data代錶 數據域；struct StackNode *next代錶 指針域；
$(4)$ top作為 棧頂指針，當棧為空的時候，top == NULL；否則，永遠指向棧頂；
$(5)$ 由於 求鏈錶長度 的算法時間複雜度是 $O (n)$ 的，所以我們需要記錄一個size來代錶現在棧中有多少元素。每次入棧時size自增，出棧時size自减。這樣在詢問棧的大小的時候，就可以通過 $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)$ 利用malloc生成一個鏈錶結點insertNode；
$(2)$ 將 當前棧頂 作為insertNode的 後繼結點；
$(3)$ 將 insertNode的 數據域 設置為傳參 dt；
$(4)$ 將insertNode作為 新的棧頂；
$(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)$ 將 棧頂指針 保存到temp中；
$(2)$ 將 棧頂指針 的 後繼結點 作為新的棧頂；
$(3)$ 釋放之前 棧頂指針 對應的內存；
$(4)$ 棧元素减一；

4、清空棧

1、動畫演示

清空棧 可以理解為，不斷的出棧，直到棧元素個數為零。

2、源碼詳解

對於鏈錶而言，清空棧 的操作需要删除每個鏈錶結點，代碼實現如下：

void StackClear(struct Stack* stk) {

while(!StackIsEmpty(stk)) {
 // (1)
StackPopStack(stk); // (2)
}
stk->top = NULL; // (3)
}

$(1)$ - $(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)$ stk->top作為 棧頂指針，它的 數據域 data就是 棧頂元素的值，返回即可；
$(2)$ size記錄的是棧元素個數；
$(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;
}
/************************************* 棧的鏈錶實現 *************************************/