1.堆和棧

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

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

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

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

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

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

棧區(qū)：處于相對較高的地址，以地址的增長方向為上的話，棧地址是向下增長的；

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

一個例子：

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

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

但是，p本身是在棧中。

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

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

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

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

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

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

(d)申請大小的限制

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

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

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

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

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

(f)存取效率

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

2）棧：char s1[]=”hellow tigerjibo”;是在運行時賦值的；用數(shù)組比用指針速度更快一些，指針在底層匯編中需要用edx寄存器中轉(zhuǎn)一下，而數(shù)組在棧上讀取。

補充：

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

(g)分配方式：

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

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

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

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

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

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

（1）堆棧

基本概念

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

(b)允許進行插入和刪除操作的一端稱為棧頂，另一端稱為棧底。
作用：可以完成從輸入數(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)順序堆棧

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

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

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

(b)鏈式堆棧

鏈式堆棧：鏈式存儲結(jié)構(gòu)的堆棧。

鏈式棧的存儲結(jié)構(gòu)：它是以頭指針為棧頂，在頭指針處插入或刪除，帶頭結(jié)點的鏈式堆棧結(jié)構(gòu)：

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

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

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

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

（2）隊列

基本概念

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

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

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

(a)初始化QueueInitiate(Q) 

(b)非空否QueueNotEmpty(Q)

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

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

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

隊列類型：

(a)順序隊列

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

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

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

可采取四種方法解決：

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

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

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

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

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

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

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

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

1)使用一個計數(shù)器記錄隊列中元素個數(shù)（即隊列長度）；

判隊滿：count>0 && rear==front
判隊空：count==0

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

判隊滿：tag==1 && rear==front
判隊空：tag==0 && rear==front

3)少用一個存儲單元

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

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

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

(c)鏈式隊列

鏈式隊列：鏈式存儲結(jié)構(gòu)的隊列。
鏈式隊列的存儲結(jié)構(gòu)：鏈式隊列的隊頭指針指向隊列的當(dāng)前隊頭結(jié)點;隊尾指針指在隊列的當(dāng)前隊尾結(jié)點。一個不帶頭結(jié)點的鏈式隊列的結(jié)構(gòu)。

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

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

(d)優(yōu)先級隊列

優(yōu)先級隊列：帶有優(yōu)先級的隊列。

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

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

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

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

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

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

最新評論