?本節(jié)講完棧下次再講一下隊列，最后補(bǔ)充一個串，我們的線性結(jié)構(gòu)基本就完事了。下圖中黃色框框圈中的是我們今日份內(nèi)容(分為兩篇博客)：

知識體系圖

棧(Stack-LIFO)結(jié)構(gòu)

棧的基礎(chǔ)概念

棧(Stack)是一個后進(jìn)先出(Last-In-First-Out)的一個特殊數(shù)據(jù)結(jié)構(gòu)，只有一端可以操作，三面環(huán)墻。按照存儲方式可以分為順序存儲的棧和鏈?zhǔn)酱鎯Φ臈?即順序棧和鏈棧)，另外還有一些特殊的棧需要我們了解：單調(diào)棧、共享棧。

不管什么棧，它的基本API接口(基本操作)都是：入棧(Push)，出棧(Pop)，查看棧頂元素(Top/Peek)，判斷棧是否為空(isEmpty)。

棧頂（top）：處于可以插入或刪除元素的一端，棧頂指針指向非空元素的下一個位置

棧底（base）：處于不能插入或刪除元素的另一端，棧底指針固定指向。

空棧（empty）：棧內(nèi)不包含任意元素，棧頂指針與棧底指針指向同一位置。

順序棧

采用順序結(jié)構(gòu)存儲的棧稱為順序棧，它的底層是數(shù)組，使用的是一段地址連續(xù)的空間。另外找一個尾指針充當(dāng)棧頂指針，指向棧頂元素的位置的下一個地址。判斷棧為空的條件就是棧頂指針指向棧底。

1.棧的順序存儲

站的順序存儲結(jié)構(gòu)可以定義為：一個棧底指針，一個棧頂指針

#define INIT_MAX_SIZE 20 //初始化棧時給的最大容量
typedef int DataType;//DataType的類型不確定，根據(jù)習(xí)慣初始假定為int
typedef struct{DataType* base;DataType* top;
}SqStack;

?2.棧的基本操作

初始化

初始化時，使用預(yù)先設(shè)置好的初值來開辟大小，并且初始一定是空棧，所以讓棧頂指針指向棧底即可。

void initStack(SqStack* s)
{s->base = (DataType*)malloc(sizeof(DataType)*INIT_MAX_SIZE);s->top = s->base;
}

判空

如果棧頂指針與棧底指針指向同一塊空間，那么棧就是空的，直接返回。這里傳不傳指針都可以，不需要進(jìn)行修改的操作，只進(jìn)行判斷，所以利用值傳遞也能實(shí)現(xiàn)目的

#include <stdbool.h>
bool isEmpty(SqStack s){return s.base == s.top;
}
bool isEmpty(SqStack* s){return s->base == s->top;
}

進(jìn)棧?

進(jìn)棧之前，我們先判斷棧是否為滿，如果滿棧，我們不能隨便加入，需要擴(kuò)容，我們選擇二倍擴(kuò)容的方式，如果擴(kuò)容失敗，結(jié)束程序，一旦我們擴(kuò)容成功，我們原來的棧頂指針也會失效，使用棧底指針加上原來的滿棧數(shù)，跨越總步長回到棧頂?shù)南鄬ξ恢?。然后將棧頂設(shè)置為元素e，并自動跨越一個步長(++)。

/*插入元素e為新的棧頂元素*/
void Push(SqStack *s, DataType e){//滿棧if(s->top == s->base + INIT_MAX_SIZE){int size = INIT_MAX_SIZE*2;s->base = (DataType*)realloc(s->base,sizeof(DataType)*size);assert(s->base);s->top = s->base + size/2;}*(s->top) = e;    //將新插入元素賦值給棧頂空間s->top++; //更改棧頂指針//可以合并為*(s->top++)=e;
}

出棧

出棧就是要后面的元素?zé)o法訪問，那么只需要將棧頂指針縮減一個步長(--)即可，但在此之前，我們需要判斷是不是空棧，如果是空棧，我們就沒必要去進(jìn)行出棧的操作了。

/*若棧不空，則刪除S的棧頂元素*/
void Pop(SqStack *s){if(s->top == s->base){return;}S->top--;   //棧頂指針減1
}

?獲取棧頂元素

獲取棧頂元素，我們需要獲取的棧頂指針上一個位置內(nèi)存儲的內(nèi)容，所以我們進(jìn)行完判空操作后，我們需要對s->top-1進(jìn)行解引用(即取*)的操作。

/*讀棧頂元素*/
DataType Top(SqStack s){if(s->top == s->base){   //?？誶eturn -1;}return *(s->top-1);   //返回棧頂元素
}

銷毀棧?

void destory(SqStack* s){if(s->base){free(s->base);s->top=s->base=NULL;}
}

3.單調(diào)棧專題

從名字上我們就可以看出來，單調(diào)棧中存放的數(shù)據(jù)應(yīng)該是有序的，所以單調(diào)棧本身也應(yīng)該分為單調(diào)遞增棧和單調(diào)遞減棧。單調(diào)的方向是從棧底到棧頂。

在進(jìn)行單調(diào)棧的講解時，我們會使用到上述的一些基本操作。我們來看一下單調(diào)棧的入棧過程：

typedef int DataType;//此處選取int作為示例for (遍歷這個數(shù)組)
{if (?？?|| 棧頂元素大于等于當(dāng)前比較元素){入棧;}else{while (棧不為空 && 棧頂元素小于當(dāng)前元素){棧頂元素出棧;更新結(jié)果;}當(dāng)前數(shù)據(jù)入棧;}
}

真題演練

?柱狀圖中的最大矩形

思路：當(dāng)前的數(shù)字可以向兩邊拓展，遇到比自己大的就接著拓展，小的就停止，然后用自己的高度乘以拓展的寬度，每次都更新最大面積，時間復(fù)雜度同樣為O(N^2)，所以我們接著借助單調(diào)棧

這里我們通過這道例題來使用一下單調(diào)遞減棧

1.設(shè)置一個單調(diào)遞減的棧（棧內(nèi)0~n為單調(diào)遞增）
2.當(dāng)遇到小于棧頂元素的值，我們開始更新數(shù)據(jù)，因?yàn)橛锌赡茏畲竺娣e就會出現(xiàn)在棧中的序列里
3.牢記棧中數(shù)據(jù)永遠(yuǎn)是有序的，這個問題比較復(fù)雜，所以讀者不妨對照著代碼來理解問題

int largestRectangleArea(vector<int>& heights) {heights.push_back(-1);/同理，我們希望棧中所有數(shù)據(jù)出棧，所以給數(shù)組最后添加一個負(fù)數(shù)SqStack st; initStack(&st);int ret = 0, top;for (int i = 0; i < heights.size(); i++){if (isEmpty(st) || heights[Top(st)] <= heights[i]){Push(&st,i);}else{while (!isEmpty(st) && heights[Top(st)] > heights[i]){top = Top(st);Pop(&st);//i-top指的是當(dāng)前矩形的寬度，heights[top]就是當(dāng)前的高度//再次強(qiáng)調(diào)棧中現(xiàn)在為單調(diào)遞增int tmp = (i - top)*heights[top];if (tmp > ret)ret = tmp;}Push(top);heights[top] = heights[i];}}return ret;
}

?4.共享棧專題

?利用棧底位置相對不變的特征，可讓兩個順序棧共享一個一維數(shù)組空間，將兩個棧的棧底分別設(shè)置在共享空間的兩端，兩個棧頂向共享空間的中間延伸，如下圖所示：

兩個棧共享同一片存儲空間，這片存儲空間不單獨(dú)屬于任何一個棧，某個棧需要的多一點(diǎn)，它就可能得到更多的存儲空間；兩個棧的棧底在這片存儲空間的兩端，當(dāng)元素入棧時，兩個棧的棧頂指針相向而行。此時我們采取另外一種實(shí)現(xiàn)棧的方法，不使用真正的指針，使用下標(biāo)索引模擬兩個棧頂指針。定義方法如下：

 #define SharedStackMax 100typedef char SharedStackType;typedef struct{SharedStackType data[SharedStackMax];size_t top1;size_t top2;}SharedStack;

共享棧的基本操作方法：?

 void SharedStackInit(SharedStack*stack){if(stack==NULL){return;}stack->top1=0;stack->top2=SharedStackMax;}void SharedStackPush1(SharedStack*stack,SharedStackType value){if(stack->top1==stack->top2||stack==NULL){return;}stack->data[stack->top1++]=value;return;}void SharedStackPush2(SharedStack*stack,SharedStackType value){if(stack->top2==stack->top1||stack==NULL){return;}                                                                       stack->data[--stack->top2]=value;}int  SharedStackTop1(SharedStack*stack,SharedStackType*value){if(stack==NULL||value==NULL){return 0;}if(stack->top1==0){return 0;}*value=stack->data[top1-1];return 1;}int SharedStackTop2(SharedStack*stack,SharedStackType*value){if(stack==NULL||value==NULL){return 0;}if(stack->top2==SharedStackMax){return 0;}*value=stack->data[stack->top2];return 1;
}void SharedStackPop1(SharedStack*stack){if(stack==NULL || stack->top1==0){return;}stack->top1--;}void SharedStackPop2(SharedStack*stack){if(stack->top2==SharedStackMax || stack==NULL){return;}stack->top2++;}     

鏈棧?

1.棧的鏈?zhǔn)酱鎯?/h4>

采用鏈?zhǔn)酱鎯Φ臈７Q為鏈棧，鏈棧的優(yōu)點(diǎn)是便于多個棧共享存儲空間和提高其效率，且不存在棧滿上溢的情況，我們就省去了不斷擴(kuò)容的麻煩。通常采用不帶頭結(jié)點(diǎn)的單鏈表實(shí)現(xiàn)，而且為了方便，使用頭插法頭刪法更簡單，所以我們的入棧和出棧就是單鏈表的頭插和頭刪的操作。Lhead指向棧頂元素，鏈棧的結(jié)構(gòu)圖如下所示：

對于鏈棧來說，空棧的概念即是Lhead指向NULL的時候。?

/*構(gòu)造節(jié)點(diǎn)*/
typedef struct StackNode{ElemType data;struct StackNode *next;
}StackNode, *LinkStackPrt;
//將StackNode* 重命名為LinkStackPrt的好處是避免下面操作出現(xiàn)二級指針的形式。(實(shí)質(zhì)還是二級指針)/*構(gòu)造鏈棧*/
typedef struct LinkStack{LinkStackPrt top;int count;
}LinkStack;

2.鏈棧的基本操作

鏈棧的進(jìn)棧

對于鏈棧的進(jìn)棧push操作，我們會創(chuàng)建一個棧節(jié)點(diǎn)，然后進(jìn)行鏈表的頭插操作。

void Push(LinkStack *S, ElemType e){LinkStackPrt p = (LinkStackPrt)malloc(sizeof(StackNode));p->data = e;p->next = S->top;    //把當(dāng)前的棧頂元素賦值給新節(jié)點(diǎn)的直接后繼S->top = p; //將新的結(jié)點(diǎn)S賦值給棧頂指針S->count++;
}

鏈棧的出棧

無需多說，頭刪即可

Element Pop(LinkStack *S){if(StackEmpty(*S)){return -1;}Element e = S->top->data;//臨時存儲棧頂元素LinkStackPtr p;p = S->top; //將棧頂結(jié)點(diǎn)賦值給pS->top = S->top->next;  //使得棧頂指針下移一位，指向后一結(jié)點(diǎn)free(p);    //釋放結(jié)點(diǎn)pS->count--;return e;
}

棧的算法應(yīng)用

遞歸專題

我們將遞歸時就提到過，遞歸是函數(shù)的遞進(jìn)調(diào)用與返回，而函數(shù)的調(diào)用與銷毀又是以棧的形式進(jìn)行的。所以能用棧解決的問題一定可以用遞歸解決。而能用遞歸的方式解決的問題，棧不一定能解決，但一定依托于棧的形式結(jié)構(gòu)。因?yàn)閷τ跅＝Y(jié)構(gòu)本身來講是作為一個容器來用的，遞歸才是存儲一系列操作這種非數(shù)據(jù)類型的特殊棧結(jié)構(gòu)。

基礎(chǔ)算法--遞歸算法【難點(diǎn)、重點(diǎn)】-CSDN博客

調(diào)用堆棧：每次遞歸調(diào)用時，棧上會創(chuàng)建一個新的堆棧幀，用于存儲該調(diào)用的上下文。

空間復(fù)雜度：遞歸的深度可能導(dǎo)致棧溢出，尤其在遞歸深度較大而沒有適當(dāng)?shù)幕厩闆r時。

迭代替代：有些遞歸算法可以用顯式?；蜓h(huán)來實(shí)現(xiàn)，從而避免遞歸帶來的棧溢出問題。

四則運(yùn)算表達(dá)式專題

四則運(yùn)算在這里的應(yīng)用其實(shí)包括后綴表達(dá)式和前綴表達(dá)式，以及我們平常熟悉的中綴表達(dá)式。

綴所處的位置不同代表的含義是四則運(yùn)算符所處的位置不同。例如：

a+b*(c/d+2)：中綴表達(dá)式

* + a b c：前綴表達(dá)式（ ==(a+b)*c ）

a b c d - * + e f / -：后綴表達(dá)式（ ==a+b*(c-d)-e/f ）

四則運(yùn)算表達(dá)式的專題我們以一道例題作為訓(xùn)練：逆波蘭表達(dá)式(前綴表達(dá)式)。

逆波蘭表達(dá)式是一種把運(yùn)算符前置的算術(shù)表達(dá)式，例如普通的表達(dá)式2 + 3的逆波蘭表示法為+ 2 3。逆波蘭表達(dá)式的優(yōu)點(diǎn)是運(yùn)算符之間不必有優(yōu)先級關(guān)系，也不必用括號改變運(yùn)算次序，例如(2 + 3) * 4的逆波蘭表示法為* + 2 3 4。本題求解逆波蘭表達(dá)式的值，其中運(yùn)算符包括+ - * /四個。

對于原逆波蘭表達(dá)式：- + * - c d b a? / e f

當(dāng)我們遇到符號時，將其入棧，等到下面兩個是數(shù)字時再出棧，如果遇到數(shù)字，直接讓其入棧，然后出棧。我們對下面的圖進(jìn)行詳細(xì)的步驟分析：

?

文字配合圖片食用效果更甚哦：

下面給出代碼：?

#include <bits/stdc++.h>
using namespace std;/*逆波蘭表達(dá)式*/
string st = "+-*/";
double calc() {string str; cin >> str;switch (str[0]) {case '+':return calc() + calc();case '-':return calc() - calc();case '*':return calc() * calc();case '/':return calc() / calc();default:return stod(str);}
}
signed main() {printf("%f\n", calc());return 0;
}

---

感謝大家觀看！多多支持哦！