英雄哪裏出來 2021-08-15 16:51:09 阅读数:863
「 數據結構 」 和 「 算法 」 是密不可分的,兩者往往是「 相輔相成 」的存在,所以,在學習 「 數據結構 」 的過程中,不免會遇到各種「 算法 」。
到底是先學 數據結構 ,還是先學 算法,我認為不必糾結這個問題,一定是一起學的。
數據結構 常用的操作一般為:「 增 」「 删 」「 改 」「 查 」。基本上所有的數據結構都是圍繞這幾個操作進行展開的。
那麼這篇文章,作者將用 「 九張動圖 」 來闡述一種 「 後進先出 」 的數據結構
「 棧 」
![]()
飯不食,水不飲,題必須刷
C語言免費動漫教程,和我一起打卡! 《光天化日學C語言》
LeetCode 太難?先看簡單題! 🧡《C語言入門100例》🧡
數據結構難?不存在的! 《畫解數據結構》
LeetCode 太簡單?算法學起來! 《夜深人靜寫算法》
棧可以用 順序錶 實現,也可以用 鏈錶 實現,濃縮為以下兩張圖:
看不懂沒有關系,我會把它拆開來一個一個講,首先來看一下今天要學習的內容目錄。
棧 是僅限在 錶尾 進行 插入 和 删除 的 線性錶。
棧 又被稱為 後進先出 (Last In First Out) 的線性錶,簡稱 LIFO 。
棧 是一個線性錶,我們把允許 插入 和 删除 的一端稱為 棧頂。
和 棧頂 相對,另一端稱為 棧底,實際上,棧底的元素我們不需要關心。
棧的插入操作,叫做 入棧,也可稱為 進棧、壓棧。如下圖所示,代錶了三次入棧操作:
棧的删除操作,叫做 出棧,也可稱為 彈棧。如下圖所示,代錶了兩次出棧操作:
一直 出棧,直到棧為空,如下圖所示:
對於一個棧來說只能獲取 棧頂 數據,一般不支持獲取 其它數據。
棧元素個數一般用一個額外變量存儲,入棧 時加一,出棧 時减一。這樣獲取棧元素的時候就不需要遍曆整個棧。通過 O ( 1 ) O(1) O(1) 的時間複雜度獲取棧元素個數。
當棧元素個數為零時,就是一個空棧,空棧不允許 出棧 操作。
對於順序錶,在 C語言 中錶現為 數組,在進行 棧的定義 之前,我們需要考慮以下幾個點:
1)棧數據的存儲方式,以及棧數據的數據類型;
2)棧的大小;
3)棧頂指針;
#define DataType int // (1)
#define maxn 100005 // (2)
struct Stack {
// (3)
DataType data[maxn]; // (4)
int top; // (5)
};
DataType
這個宏定義來統一代錶棧中數據的類型,這裏將它定義為整型,根據需要可以定義成其它類型,例如浮點型、字符型、結構體 等等;maxn
代錶我們定義的棧的最大元素個數;Stack
就是我們接下來會用到的 棧結構體;DataType data[maxn]
作為棧元素的存儲方式,數據類型為DataType
,可以自行定制;top
即棧頂指針,data[top-1]
錶示棧頂元素,top == 0
代錶空棧;如圖所示,藍色元素 為原本在棧中的元素,紅色元素 為當前需要 入棧 的元素,執行完畢以後,棧頂指針加一。具體來看下代碼實現。
void StackPushStack(struct Stack *stk, DataType dt) {
// (1)
stk->data[ stk->top ] = dt; // (2)
stk->top = stk->top + 1; // (3)
}
stk
是一個指向棧對象的指針,由於這個接口會修改棧對象的成員變量,所以這裏必須傳指針,否則,就會導致函數執行完畢,傳參對象沒有任何改變;stk->top < maxn
,void StackPushStack(struct Stack *stk, DataType dt) {
stk->data[ stk->top++ ] = dt;
}
stk->top++
錶達式的值是自增前的值,並且自身進行了一次自增。如圖所示,藍色元素 為原本在棧中的元素,紅色元素 為當前需要 出棧 的元素,執行完畢以後,棧頂的指針减一。具體來看下代碼實現。
void StackPopStack(struct Stack* stk) {
--stk->top;
}
如圖所示,對於數組來說,清空棧的操作只需要將 棧頂指針 置為棧底,也就是數組下標 0 即可,下次繼續 入棧 的時候會將之前的內存重複利用。
void StackClear(struct Stack* stk) {
stk->top = 0;
}
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)
}
/************************************* 棧的順序錶實現 *************************************/
#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)棧數據的存儲方式,以及棧數據的數據類型;
2)棧的大小;
3)棧頂指針;
typedef int DataType; // (1)
struct StackNode; // (2)
struct StackNode {
// (3)
DataType data;
struct StackNode *next;
};
struct Stack {
struct StackNode *top; // (4)
int size; // (5)
};
struct StackNode;
是對鏈錶結點的聲明;DataType data
代錶 數據域;struct StackNode *next
代錶 指針域;top
作為 棧頂指針,當棧為空的時候,top == NULL
;否則,永遠指向棧頂;size
來代錶現在棧中有多少元素。每次 入棧時size
自增,出棧時size
自减。這樣在詢問棧的大小的時候,就可以通過 O ( 1 ) O(1) O(1) 的時間複雜度。如圖所示,head 為棧頂,tail 為棧底,vtx 為當前需要 入棧 的元素,即圖中的 柳丁色結點。入棧 操作完成後,棧頂 元素變為 vtx,即圖中 綠色結點。
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)
}
malloc
生成一個鏈錶結點insertNode
;insertNode
的 後繼結點;insertNode
的 數據域 設置為傳參 dt
;insertNode
作為 新的棧頂;如圖所示,head 為棧頂,tail 為棧底,temp 為當前需要 出棧 的元素,即圖中的 柳丁色結點。出棧 操作完成後,棧頂 元素變為之前 head 的 後繼結點,即圖中 綠色結點。
void StackPopStack(struct Stack* stk) {
struct StackNode *temp = stk->top; // (1)
stk->top = temp->next; // (2)
free(temp); // (3)
--stk->size; // (4)
}
temp
中;清空棧 可以理解為,不斷的出棧,直到棧元素個數為零。
void StackClear(struct Stack* stk) {
while(!StackIsEmpty(stk)) {
// (1)
StackPopStack(stk); // (2)
}
stk->top = NULL; // (3)
}
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);
}
stk->top
作為 棧頂指針,它的 數據域 data
就是 棧頂元素的值,返回即可;size
記錄的是 棧元素個數;/************************************* 棧的鏈錶實現 *************************************/
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;
}
/************************************* 棧的鏈錶實現 *************************************/
在利用順序錶實現棧時,入棧 和 出棧 的常數時間複雜度低,且 清空棧 操作相比 鏈錶實現 能做到 O ( 1 ) O(1) O(1),唯一的不足之處是:需要預先申請好空間,而且當空間不够時,需要進行擴容,擴容方式本文未提及,可以參考以下文章:《C/C++ 面試 100 例》(四)vector 擴容策略。
在利用鏈錶實現棧時,入棧 和 出棧 的常數時間複雜度略高,主要是每插入一個棧元素都需要申請空間,每删除一個棧元素都需要釋放空間,且 清空棧 操作是 O ( n ) O(n) O(n) 的,直接將 棧頂指針 置空會導致內存泄漏。好處就是:不需要預先分配空間,且在內存允許範圍內,可以一直 入棧,沒有順序錶的限制。
好啦,接下來,讓我們做幾個棧的題目練習一下吧。
《LeetCode 20. 有效的括號》解題報告
《LeetCode 32. 最長有效括號》解題報告
棧的進階主要是單調棧相關的內容,可以參考我的另一篇文章:夜深人靜寫算法(十一)- 單調棧。看完以後,別忘了進行相關題目的練習。
飯不食,水不飲,題必須刷
C語言免費動漫教程,和我一起打卡! 《光天化日學C語言》
LeetCode 太難?先看簡單題! 🧡《C語言入門100例》🧡
數據結構難?不存在的! 《畫解數據結構》
LeetCode 太簡單?算法學起來! 《夜深人靜寫算法》
版权声明:本文为[英雄哪裏出來]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/08/20210815165054775X.html