正常操作，正常分析，大家好我是D1N910。

下面是我學(xué)郝斌老師的數(shù)據(jù)結(jié)構(gòu)入門的學(xué)習(xí)筆記。

那么開卷。

鏈表的我已經(jīng)學(xué)完了，后面可能會補。

線性結(jié)構(gòu)的兩種常見應(yīng)用 棧/隊列，本文講的是棧。

本文學(xué)習(xí)自：

棧的定義/分類/算法/應(yīng)用

0、前言

首先要說一下計算機的內(nèi)存。什么是計算機的內(nèi)存呢？

內(nèi)存(Memory)是計算機的重要部件，也稱內(nèi)存儲器和主存儲器，它用于暫時存放CPU中的運算數(shù)據(jù)，以及與硬盤等外部存儲器交換的數(shù)據(jù)。

內(nèi)存分為靜態(tài)內(nèi)存（棧）/動態(tài)內(nèi)存（堆）

靜態(tài)內(nèi)存是在棧里分配的，操作系統(tǒng)自動分配的。

動態(tài)內(nèi)存是在堆里分配的，堆是要程序員主動建立起來的。

舉個實際的例子，比如說下面的 1.c 文件有變量 m、p、i、p，同樣也有 200、100 這兩個變量，前者存在棧里，后者存在堆里。棧是計算機進行分配分配的。堆是程序員進行分配的。

為什么說是程序員分配的堆呢？因為后面200等可能會做修改，所以是程序員進行分配的。

棧、堆表示分配數(shù)據(jù)的一種方式，靜態(tài)/局部變量一樣以出棧的方式分配內(nèi)存；堆是以堆排序的方式分配內(nèi)存。

1、棧定義

棧就是一種可以實現(xiàn)“先進后出”的存儲結(jié)構(gòu)（存儲方式）。只要我們搞出一個東西能夠先進后出存儲數(shù)據(jù)，那么就是棧 —— 這像是鴨式辨型的概念，鴨式辨型的通俗說法是:“如果它走起路來像鴨子,叫起來也是鴨子,那么它就是鴨子。

棧類似于箱子裝書，先進后出。先放進去的最后取出來。

x 不是這種橫著裝書??！

2、棧分類（靜態(tài)棧、動態(tài)棧）

2.1、靜態(tài)棧

以數(shù)組為內(nèi)核，想要刪掉其中一個，要把想要刪最后的全部拿出來 ——

因為是以數(shù)組為內(nèi)核，所以棧具有數(shù)組的特性，長度是固定的、每個數(shù)據(jù)之間的地址是連續(xù)的，會先占一定的內(nèi)存，所以是靜態(tài)棧。

2.2、動態(tài)棧

棧的特性和鏈表相似，每個棧元素之間的地址不相連。和鏈表比砍了一些功能，只能從頭部加和刪，不能夠在尾部進行加和刪。也叫鏈式棧。

4->3->2->1->0

2.3、隊列定義

先進先出。類似排隊買東西，只有兩個口，一個入口，一個出口，只能夠從一端添加元素，只能夠從另一端減少元素。

3、棧的算法

一般就是 出棧/壓棧 兩個算法

類似生產(chǎn)者-消費者模式，先把生產(chǎn)好的東西直接壓進去，消費的時候直接從里面拿東西進行消費。

4、棧程序演示（33_棧程序演示 55:24）

一般的動態(tài)棧程序如上演示，棧的每個元素都是有意義的，PTop永遠指向棧的頂部，PButtom永遠指向棧的底部。所以PTop會瘋狂動和修改。但是這里有一個問題就是棧的每一個元素都是有意義的，特別是PButtom指向的也是有意義的元素，不太方便處理。

那么就參考鏈表中頭結(jié)點的設(shè)計。PButtom指向沒有意義的頭節(jié)點。

【入?！咳绻霔５脑挘拖壬a(chǎn)一個節(jié)點，然后往棧中接入，把PTop往上移一位；

【判空】判斷棧是否為空，只要PTop和PButton相等就行

【判滿】動態(tài)棧是鏈表，不存在滿不滿的問題~

下面就演示這個程序。

4.1、棧程序演示-頭文件的引入

#include <stdio.h>

#include <stdlib.h>

4.2、棧程序演示-定義棧和棧對應(yīng)鏈表結(jié)構(gòu)體

typedef struct Node // 箱子里的書

{

? ?int data;

? ?struct Node * pNext;

} NODE, * PNODE;

typedef struct Stack // 棧 ?- 箱子

{

? ?PNODE pTop; // 指向棧的頂部

? ?PNODE pBottom; // 指向棧的底部

} STACK, * PSTACK;

4.3、棧程序演示-定義棧的基本算法（初始化/壓棧/遍歷/判斷棧是否為空/出棧/清空棧內(nèi)容）

int main(void)

{

? ?STACK S; // STACK 等價于 struct Stack

上面可以在main中聲明棧變量 S，現(xiàn)在 S 有PTop 和 PButtom，PTop 和 PButtom還沒指向任何東西。我們要初始化棧，初始化方法名可自定義，一般叫init，對應(yīng)的還有其他基本算法，push: 壓棧，往棧中添加元素；traverse：遍歷輸出棧的元素

init 初始化棧

給棧的pTop分配一個節(jié)點內(nèi)存地址；

如果分配的地址為NULL，說明分配失敗：

-打印報錯信息，并退出程序。

如果分配的地址不為NULL，說明分配成功：

-棧的pBottom也指向棧的pTop指向的節(jié)點；

-棧的pTop指向的節(jié)點存儲的下一節(jié)點的地址賦為NULL，以此保證是空節(jié)點。

結(jié)束。

void init (PSTACK pS)

{

pS->pTop = (PNODE)malloc(sizeof(NODE));

if (NULL == pS->pTop) {

printf("分配內(nèi)存失??！\n");

exit(-1);

}

else

{

pS->pBottom = pS->pTop;

pS->pTop->pNext = NULL;

}

}

現(xiàn)在初始化以后，S的PTop和PBottom都指向同一個空結(jié)點。

push 壓棧

創(chuàng)建一個新的結(jié)點；

新的節(jié)點data存儲值；

新的節(jié)點的pNext指向棧的pTop；

棧的pTop指向新的節(jié)點。

結(jié)束。

traverse 遍歷

創(chuàng)建一個p節(jié)點指針指向棧的最頂部元素；

循環(huán)執(zhí)行：當(dāng)p節(jié)點指針和棧的最底部元素指向地址不同時，打印p節(jié)點指針的值，改變p節(jié)點指針的指向為下一個節(jié)點地址；

結(jié)束循環(huán)，打印個回車；

結(jié)束。

執(zhí)行一波看看結(jié)果。

調(diào)用函數(shù)。

結(jié)果

empty 判斷棧是否為空

接受棧的指針作為參數(shù)。

判斷棧的pTop是不是和棧的pBottom指向相同；

-如果是，返回true；

-如果不是，返回false。

結(jié)束

pop 出棧

接受棧的指針、存儲出棧的值的整數(shù)指針作為參數(shù)，

判斷棧是否為空（用剛剛的empty方法）

-如果是，出棧失敗，返回false；

-如果不是，則繼續(xù)執(zhí)行

--定義新節(jié)點指針存儲當(dāng)前棧的pTop，新節(jié)點指針即為出棧節(jié)點

--修改當(dāng)前棧的pTop指向為pTop的下一個節(jié)點（1）

--將出棧節(jié)點的指賦值給存儲出棧的值的整數(shù)指針；（2）

【注】（1）、（2）順序可變；

--釋放出棧節(jié)點內(nèi)存；

--手動將棧定義為空；

--返回true

main調(diào)用執(zhí)行一波

成功時結(jié)果如下：

將壓棧代碼注釋，重新跑程序，查看出棧失敗場景。

出棧失敗時結(jié)果如下

clear 清空棧

創(chuàng)建兩個節(jié)點指針p、q，分別指向pTop、pTop->pNext，這樣釋放p內(nèi)存以后仍舊可以找到下一個節(jié)點去釋放。

這是老師給的方法。

先判斷是否為空，為空不執(zhí)行；

定義p存放pS.pTop；

定義q存放NULL；

當(dāng)p不等于pS->pBottom，那么不斷地free；

循環(huán)結(jié)束后將pTop指向pBottom。

結(jié)束。

棧的內(nèi)容確實比鏈表的簡單。

5、棧的應(yīng)用（34_棧的應(yīng)用 06:58）

函數(shù)調(diào)用

假設(shè)有f、g、y、k這幾個函數(shù)是這么調(diào)用的

f() {g()}

g() {y()}

y() {k()}

k() {}

那么函數(shù)執(zhí)行順序是這樣的

f() -> g() -> y() ->k()

當(dāng)執(zhí)行到了k函數(shù)以后，又會把值往上面回傳

k()-> y() -> ?g() -> f()

那么計算機就是用壓棧的原理去實現(xiàn)上面的函數(shù)調(diào)用的過程，仔細一看我們可以發(fā)現(xiàn)，當(dāng)f()內(nèi)等待g()的值的返回時，f()函數(shù)接下來要執(zhí)行的地址就可以壓棧中，以此類推，k函數(shù)是最頂部被壓入的函數(shù)，然后再逐個出棧找到下一個要執(zhí)行的語句的地址進行執(zhí)行（將值回傳），直到到了棧底的去執(zhí)行。

中斷 - 老師說不講，但是也很重要（？

表達式求值

3x2+5/6-4

利用兩個?？梢跃幱嬎闫鳌?/span>

內(nèi)存分配

緩沖處理

迷宮

以上源代碼

https://github.com/D1N910/learn-c/blob/main/haobingDataStructure/30/stack08.c

學(xué)習(xí)進度（34/63）

繼續(xù)加油