1.堆和棧

（1）數(shù)據(jù)結(jié)構(gòu)的堆和棧

堆棧是兩種數(shù)據(jù)結(jié)構(gòu)。

棧（棧像裝數(shù)據(jù)的桶或箱子）：是一種具有后進(jìn)先出性質(zhì)的數(shù)據(jù)結(jié)構(gòu)，也就是說后存放的先取，先存放的后取。這就如同要取出放在箱子里面底下的東西（放入的比較早的物體），首先要移開壓在它上面的物體（放入的比較晚的物體）。

堆（堆像一棵倒過來的樹）：是一種經(jīng)過排序的樹形數(shù)據(jù)結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)都有一個(gè)值。通常所說的堆的數(shù)據(jù)結(jié)構(gòu)，是指二叉堆。堆的特點(diǎn)是根結(jié)點(diǎn)的值最?。ɑ蜃畲螅?，且根結(jié)點(diǎn)的兩個(gè)子樹也是一個(gè)堆。由于堆的這個(gè)特性，常用來實(shí)現(xiàn)優(yōu)先隊(duì)列，堆的存取是隨意，這就如同在圖書館的書架上取書，雖然書的擺放是有順序的，但是想取任意一本時(shí)不必像棧一樣，先取出前面所有的書，書架這種機(jī)制不同于箱子，我們可以直接取出我們想要的書。

（2）內(nèi)存分配中的堆和棧

C語(yǔ)言程序內(nèi)存分配中的堆和棧。C語(yǔ)言程序經(jīng)過編譯連接后形成編譯、連接后形成的二進(jìn)制映像文件由棧，堆，數(shù)據(jù)段（由三部分部分組成：只讀數(shù)據(jù)段，已經(jīng)初始化讀寫數(shù)據(jù)段，未初始化數(shù)據(jù)段即BBS）和代碼段組成，如下圖所示：

棧區(qū)：處于相對(duì)較高的地址，以地址的增長(zhǎng)方向?yàn)樯系脑?，棧地址是向下增長(zhǎng)的；

堆區(qū)：是向上增長(zhǎng)的用于分配程序員申請(qǐng)的內(nèi)存空間。

一個(gè)例子：

main.cpp 
int a = 0; 全局初始化區(qū) 
char *p1; 全局未初始化區(qū) 
main() 
{ 
 int b; 棧 
 char s[] = "abc"; 棧 
 char *p2; 棧 
 char *p3 = "123456"; //123456\0在常量區(qū)，p3在棧上。 
 static int c =0； 全局（靜態(tài)）初始化區(qū) 
 p1 = (char *)malloc(10); 堆 
 p2 = (char *)malloc(20); 堆 
}

堆和棧的區(qū)別：

(a)申請(qǐng)方式和回收方式不同
1)棧（satck）:由系統(tǒng)自動(dòng)分配。例如，聲明在函數(shù)中一個(gè)局部變量int b;系統(tǒng)自動(dòng)在棧中為b開辟空間。
2)堆（heap）:需程序員自己申請(qǐng)（調(diào)用malloc,realloc,calloc）,并指明大小，并由程序員進(jìn)行釋放。容易產(chǎn)生memory leak.
例如: char  *p;

         p = (char *)malloc(sizeof(char));

但是，p本身是在棧中。

由于棧上的空間是自動(dòng)分配自動(dòng)回收的，所以棧上的數(shù)據(jù)的生存周期只是在函數(shù)的運(yùn)行過程中，運(yùn)行后就釋放掉，不可以再訪問。而堆上的數(shù)據(jù)只要程序員不釋放空間，就一直可以訪問到，不過缺點(diǎn)是一旦忘記釋放會(huì)造成內(nèi)存泄露。

(b)申請(qǐng)后系統(tǒng)的響應(yīng)

1）棧：只要棧的空間大于所申請(qǐng)空間，系統(tǒng)將為程序提供內(nèi)存，否則將報(bào)異常提示棧溢出。

2）堆：首先應(yīng)該知道操作系統(tǒng)有一個(gè)記錄空閑內(nèi)存地址的鏈表，但系統(tǒng)收到程序的申請(qǐng)時(shí)，會(huì)遍歷該鏈表，尋找第一個(gè)空間大于所申請(qǐng)空間的堆結(jié)點(diǎn)，然后將該結(jié)點(diǎn)從空閑鏈表中刪除，并將該結(jié)點(diǎn)的空間分配給程序，另外，對(duì)于大多數(shù)系統(tǒng)，會(huì)在這塊內(nèi)存空間中的首地址處記錄本次分配的大小，這樣，代碼中的free語(yǔ)句才能正確的釋放本內(nèi)存空間。另外，找到的堆結(jié)點(diǎn)的大小不一定正好等于申請(qǐng)的大小，系統(tǒng)會(huì)自動(dòng)的將多余的那部分重新放入空閑鏈表中。
說明：對(duì)于堆來講，頻繁的new/delete勢(shì)必會(huì)造成內(nèi)存空間的不連續(xù)，從而造成大量的碎片，使程序效率降低。對(duì)于棧來講，則不會(huì)存在這個(gè)問題。

堆會(huì)在申請(qǐng)后還要做一些后續(xù)的工作這就會(huì)引出申請(qǐng)效率的問題。

(c)申請(qǐng)效率
1）棧由系統(tǒng)自動(dòng)分配，速度快。但程序員是無法控制。
2）堆是由malloc分配的內(nèi)存，一般速度比較慢，而且容易產(chǎn)生碎片，不過用起來最方便。

(d)申請(qǐng)大小的限制

1）棧：在Windows下,棧是向低地址擴(kuò)展的數(shù)據(jù)結(jié)構(gòu)，是一塊連續(xù)的內(nèi)存的區(qū)域。這句話的意思是棧頂?shù)牡刂泛蜅５淖畲笕萘渴窍到y(tǒng)預(yù)先規(guī)定好的，在Windows下，棧的大小是2M（也有的說是1M，總之是一個(gè)編譯時(shí)就確定的常數(shù)），如果申請(qǐng)的空間超過棧的剩余空間時(shí)，將提示overflow。因此，能從棧獲得的空間較小。 

2）堆：堆是向高地址擴(kuò)展的數(shù)據(jù)結(jié)構(gòu)，是不連續(xù)的內(nèi)存區(qū)域。這是由于系統(tǒng)是用鏈表來存儲(chǔ)的空閑內(nèi)存地址的，自然是不連續(xù)的，而鏈表的遍歷方向是由低地址向高地址。堆的大小受限于計(jì)算機(jī)系統(tǒng)中有效的虛擬內(nèi)存。由此可見，堆獲得的空間比較靈活，也比較大。

(e)堆和棧中的存儲(chǔ)內(nèi)容

1）棧： 在函數(shù)調(diào)用時(shí)，第一個(gè)進(jìn)棧的是主函數(shù)中函數(shù)調(diào)用后的下一條指令（函數(shù)調(diào)用語(yǔ)句的下一條可執(zhí)行語(yǔ)句）的地址，然后是函數(shù)的各個(gè)參數(shù)，在大多數(shù)的C編譯器中，參數(shù)是由右往左入棧的，然后是函數(shù)中的局部變量。注意靜態(tài)變量是不入棧的。 
當(dāng)本次函數(shù)調(diào)用結(jié)束后，局部變量先出棧，然后是參數(shù)，最后棧頂指針指向最開始存的地址，也就是主函數(shù)中的下一條指令，程序由該點(diǎn)繼續(xù)運(yùn)行。 

2）堆：一般是在堆的頭部用一個(gè)字節(jié)存放堆的大小。堆中的具體內(nèi)容有程序員安排。

(f)存取效率

1）堆：char *s1=”hellow tigerjibo”;是在編譯是就確定的；

2）棧：char s1[]=”hellow tigerjibo”;是在運(yùn)行時(shí)賦值的；用數(shù)組比用指針?biāo)俣雀煲恍羔樤诘讓訁R編中需要用edx寄存器中轉(zhuǎn)一下，而數(shù)組在棧上讀取。

補(bǔ)充：

棧是機(jī)器系統(tǒng)提供的數(shù)據(jù)結(jié)構(gòu)，計(jì)算機(jī)會(huì)在底層對(duì)棧提供支持：分配專門的寄存器存放棧的地址，壓棧出棧都有專門的指令執(zhí)行，這就決定了棧的效率比較高。堆則是C/C++函數(shù)庫(kù)提供的，它的機(jī)制是很復(fù)雜的，例如為了分配一塊內(nèi)存，庫(kù)函數(shù)會(huì)按照一定的算法（具體的算法可以參考數(shù)據(jù)結(jié)構(gòu)/操作系統(tǒng)）在堆內(nèi)存中搜索可用的足夠大小的空間，如果沒有足夠大小的空間（可能是由于內(nèi)存碎片太多），就有可能調(diào)用系統(tǒng)功能去增加程序數(shù)據(jù)段的內(nèi)存空間，這樣就有機(jī)會(huì)分到足夠大小的內(nèi)存，然后進(jìn)行返回。顯然，堆的效率比棧要低得多。

(g)分配方式：

1）堆都是動(dòng)態(tài)分配的，沒有靜態(tài)分配的堆。

2）棧有兩種分配方式：靜態(tài)分配和動(dòng)態(tài)分配。靜態(tài)分配是編譯器完成的，比如局部變量的分配。動(dòng)態(tài)分配由alloca函數(shù)進(jìn)行分配，但是棧的動(dòng)態(tài)分配和堆是不同的。它的動(dòng)態(tài)分配是由編譯器進(jìn)行釋放，無需手工實(shí)現(xiàn)。

最后，關(guān)于棧和堆一個(gè)形象的比喻：

使用棧就象我們?nèi)ワ堭^里吃飯，只管點(diǎn)菜（發(fā)出申請(qǐng)）、付錢、和吃（使用），吃飽了就走，不必理會(huì)切菜、洗菜等準(zhǔn)備工作和洗碗、刷鍋等掃尾工作，好處是快捷，但是自由度小。

使用堆就象是自己動(dòng)手做喜歡吃的菜肴，比較麻煩，但是比較符合自己的口味，而且自由度大。

2.堆棧和隊(duì)列（數(shù)據(jù)結(jié)構(gòu)）

（1）堆棧

基本概念

(a)定義:限定只能在固定一端進(jìn)行插入和刪除操作的線性表。
特點(diǎn)：后進(jìn)先出。

(b)允許進(jìn)行插入和刪除操作的一端稱為棧頂，另一端稱為棧底。
作用：可以完成從輸入數(shù)據(jù)序列到某些輸出數(shù)據(jù)序列的轉(zhuǎn)換。

堆棧抽象數(shù)據(jù)類型

數(shù)據(jù)集合: 
{a0,a1,…,an-1} ，ai的數(shù)據(jù)類型為DataType。

操作集合：

(a) StackInitiate(S) ：初始化堆棧S
(b) StackNotEmpty(S)：堆棧S非空否
(c)StackPush(S, x) ：入棧
(d)StackPop(S, d)：出棧
(e)StackTop(S, d)：取棧頂數(shù)據(jù)元素

堆棧類型

(a)順序堆棧

順序堆棧：順序存儲(chǔ)結(jié)構(gòu)的堆棧。
順序棧的存儲(chǔ)結(jié)構(gòu)：利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素。

數(shù)據(jù)結(jié)構(gòu)：

typedef struct
{
 DataTypestack[MaxStackSize];
 int top;
}SeqStack;

(b)鏈?zhǔn)蕉褩?/p>

鏈?zhǔn)蕉褩＃烘準(zhǔn)酱鎯?chǔ)結(jié)構(gòu)的堆棧。

鏈?zhǔn)綏５拇鎯?chǔ)結(jié)構(gòu)：它是以頭指針為棧頂，在頭指針處插入或刪除，帶頭結(jié)點(diǎn)的鏈?zhǔn)蕉褩＝Y(jié)構(gòu)：

鏈棧中每個(gè)結(jié)點(diǎn)由兩個(gè)域構(gòu)成：data域和next域。

結(jié)點(diǎn)結(jié)構(gòu)體定義如下

typedef struct snode
{  
  DataType data;
  struct snode *next;
} LSNode;

采用鏈棧存儲(chǔ)方式的優(yōu)點(diǎn)是：當(dāng)棧中元素個(gè)數(shù)變化較大，準(zhǔn)確數(shù)字難以確定時(shí)，鏈棧較順序堆棧方便。

（2）隊(duì)列

基本概念

定義:只能在表的一端進(jìn)行插入操作（隊(duì)尾），在表的另一端進(jìn)行刪除操作的線性表（隊(duì)頭）。一個(gè)隊(duì)列的示意圖如下：

隊(duì)列抽象數(shù)據(jù)類型

數(shù)據(jù)集合:{a0,a1,…,an-1}，ai的數(shù)據(jù)類型為DataType。
操作集合：

(a)初始化QueueInitiate(Q) 

(b)非空否QueueNotEmpty(Q)

(c)入隊(duì)列QueueAppend(Q,x)

(d)出隊(duì)列QueueDelete(Q,d)

(e)取隊(duì)頭數(shù)據(jù)元素QueueGet(Q, d)

隊(duì)列類型：

(a)順序隊(duì)列

順序隊(duì)列：順序存儲(chǔ)結(jié)構(gòu)的隊(duì)列。

順序隊(duì)列的存儲(chǔ)結(jié)構(gòu)：有6個(gè)存儲(chǔ)空間的順序隊(duì)列動(dòng)態(tài)示意圖如下。

順序隊(duì)列的“假溢出”問題：因多次入隊(duì)列和出隊(duì)列操作后出現(xiàn)的雖有存儲(chǔ)空間但不能進(jìn)行入隊(duì)列操作的情況。

可采取四種方法解決：

1)采用順序循環(huán)隊(duì)列；

2)按最大可能的進(jìn)隊(duì)操作次數(shù)設(shè)置順序隊(duì)列的最大元素個(gè)數(shù)（最差的方法）；

3)修改出隊(duì)算法，使每次出隊(duì)列后都把隊(duì)列中剩余數(shù)據(jù)元素向隊(duì)頭方向移動(dòng)一個(gè)位置；

4)修改入隊(duì)算法，增加判斷條件，當(dāng)假溢出時(shí)，把隊(duì)列中的數(shù)據(jù)元素向?qū)︻^移動(dòng)，然后方完成入隊(duì)操作。

(b)順序循環(huán)隊(duì)列

基本原理：把順序隊(duì)列所使用的存儲(chǔ)空間構(gòu)造成一個(gè)邏輯上首尾相連的循環(huán)隊(duì)列。當(dāng)rear和front達(dá)到MaxQueueSize-1后，再前進(jìn)一個(gè)位置就自動(dòng)到0。

順序循環(huán)隊(duì)列的隊(duì)空和隊(duì)滿判斷問題：

在順序循環(huán)隊(duì)列中，隊(duì)空特征是front=rear，隊(duì)滿時(shí)也會(huì)是front=rear，判決條件將出現(xiàn)二義性，解決方案有三：

1)使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素個(gè)數(shù)（即隊(duì)列長(zhǎng)度）；

判隊(duì)滿：count>0 && rear==front
判隊(duì)空：count==0

2)設(shè)標(biāo)志位：出隊(duì)時(shí)置0,入隊(duì)時(shí)置1,則可識(shí)別當(dāng)前front=rear  屬于何種情況；

判隊(duì)滿：tag==1 && rear==front
判隊(duì)空：tag==0 && rear==front

3)少用一個(gè)存儲(chǔ)單元

判隊(duì)滿：front=(rear+1)%MaxQueueSize
判隊(duì)空：rear==front

順序循環(huán)隊(duì)列的結(jié)構(gòu)體定義如下：

typedef struct
{
  DataType queue[MaxQueueSize];
  int rear;
  int front;
  int count;
} SeqCQueue; 

(c)鏈?zhǔn)疥?duì)列

鏈?zhǔn)疥?duì)列：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的隊(duì)列。
鏈?zhǔn)疥?duì)列的存儲(chǔ)結(jié)構(gòu)：鏈?zhǔn)疥?duì)列的隊(duì)頭指針指向隊(duì)列的當(dāng)前隊(duì)頭結(jié)點(diǎn);隊(duì)尾指針指在隊(duì)列的當(dāng)前隊(duì)尾結(jié)點(diǎn)。一個(gè)不帶頭結(jié)點(diǎn)的鏈?zhǔn)疥?duì)列的結(jié)構(gòu)。

結(jié)點(diǎn)的結(jié)構(gòu)體可定義如下：

typedef struct qnode
{
  DataTypedata;
  struct qnode*next;
}LQNode;
隊(duì)頭指針front和隊(duì)尾指針rear的結(jié)構(gòu)體類型：
typedef struct
{
 LQNode *front;
 LQNode *rear;
}LQueue;

(d)優(yōu)先級(jí)隊(duì)列

優(yōu)先級(jí)隊(duì)列：帶有優(yōu)先級(jí)的隊(duì)列。

順序優(yōu)先級(jí)隊(duì)列：用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的優(yōu)先級(jí)隊(duì)列。

優(yōu)先級(jí)隊(duì)列和一般隊(duì)列的主要區(qū)別：優(yōu)先級(jí)隊(duì)列的出隊(duì)列操作不是把隊(duì)頭元素出隊(duì)列，而是把隊(duì)列中優(yōu)先級(jí)最高的元素出隊(duì)列。

它的數(shù)據(jù)元素定義為如下結(jié)構(gòu)體：

struct DataType              
{
 ElemType elem;//數(shù)據(jù)元素
 int priority;   //優(yōu)先級(jí)
};

注：順序優(yōu)先級(jí)隊(duì)列除出隊(duì)列操作外的其他操作的實(shí)現(xiàn)方法與前邊討論的順序隊(duì)列操作的實(shí)現(xiàn)方法相同。

以上所述是小編給大家介紹的C語(yǔ)言中堆棧和隊(duì)列，希望對(duì)大家有所幫助，如果大家有任何疑問請(qǐng)給我留言，小編會(huì)及時(shí)回復(fù)大家的。在此也非常感謝大家對(duì)腳本之家網(wǎng)站的支持！

最新評(píng)論