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

英雄哪裏出來 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 ) 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 太簡單?算法學起來!
夜深人靜寫算法
本文已收錄於專欄
畫解數據結構

版权声明:本文为[英雄哪裏出來]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/08/20210815165054775X.html