堆(heap)和棧(stack)是C/C++編程不可避免會(huì)碰到的兩個(gè)基本概念。首先，這兩個(gè)概念都可以在講數(shù)據(jù)結(jié)構(gòu)的書中找到，他們都是基本的數(shù)據(jù)結(jié)構(gòu)，雖然棧更為簡(jiǎn)單一些。???
???
??? 在具體的C/C++編程框架中，這兩個(gè)概念并不是并行的。對(duì)底層機(jī)器代碼的研究可以揭示，棧是機(jī)器系統(tǒng)提供的數(shù)據(jù)結(jié)構(gòu)，而堆則是C/C++函數(shù)庫(kù)提供的。??????

棧和堆其實(shí)有兩種理解： ?
? ?
? 其一，純粹的數(shù)據(jù)結(jié)構(gòu)的理解：棧是一種先進(jìn)后出的線性表，只要符合先進(jìn)后出的原則的線性表都是棧，采用數(shù)組還是鏈表來(lái)實(shí)現(xiàn)線性表是沒(méi)關(guān)系的。堆則是二叉樹的一種，有所謂最大堆最小堆，排序算法中有常用的堆排序。 ?
? ?
? 其二，系統(tǒng)的角度理解：棧，系統(tǒng)為運(yùn)行的程序分配的后進(jìn)先出的存儲(chǔ)區(qū)域（玩過(guò)匯編的話，必然知道每個(gè)程序都有所謂堆棧段），一般用來(lái)保存局部變量或者函數(shù) 參數(shù)。堆，系統(tǒng)管理的可被程序利用的全局存儲(chǔ)空間，一般用來(lái)保存全局變量和靜態(tài)局部變量，指針動(dòng)態(tài)分配得到的內(nèi)存也從堆中來(lái)。

??? 具體地說(shuō)，現(xiàn)代計(jì)算機(jī)(串行執(zhí)行機(jī)制)，都直接在代碼底層支持棧的數(shù)據(jù)結(jié)構(gòu)。這體現(xiàn)在，有專門的寄存器指向棧所在的地址，有專門的機(jī)器指令完成數(shù)據(jù)入棧出 棧的操作。這種機(jī)制的特點(diǎn)是效率高，支持的數(shù)據(jù)有限，一般是整數(shù)，指針，浮點(diǎn)數(shù)等系統(tǒng)直接支持的數(shù)據(jù)類型，并不直接支持其他的數(shù)據(jù)結(jié)構(gòu)。因?yàn)闂５倪@種特 點(diǎn)，對(duì)棧的使用在程序中是非常頻繁的。對(duì)子程序的調(diào)用就是直接利用棧完成的。機(jī)器的call指令里隱含了把返回地址推入棧，然后跳轉(zhuǎn)至子程序地址的操作， 而子程序中的ret指令則隱含從堆棧中彈出返回地址并跳轉(zhuǎn)之的操作。C/C++中的自動(dòng)變量是直接利用棧的例子，這也就是為什么當(dāng)函數(shù)返回時(shí)，該函數(shù)的自 動(dòng)變量自動(dòng)失效的原因(因?yàn)槎褩；謴?fù)了調(diào)用前的狀態(tài))。???
????
??? 和棧不同，堆的數(shù)據(jù)結(jié)構(gòu)并不是由系統(tǒng)(無(wú)論是機(jī)器系統(tǒng)還是操作系統(tǒng))支持的，而是由函數(shù)庫(kù)提供的?；镜膍alloc/realloc/free函數(shù)維護(hù) 了一套內(nèi)部的堆數(shù)據(jù)結(jié)構(gòu)。當(dāng)程序使用這些函數(shù)去獲得新的內(nèi)存空間時(shí)，這套函數(shù)首先試圖從內(nèi)部堆中尋找可用的內(nèi)存空間，如果沒(méi)有可以使用的內(nèi)存空間，則試圖 利用系統(tǒng)調(diào)用來(lái)動(dòng)態(tài)增加程序數(shù)據(jù)段的內(nèi)存大小，新分配得到的空間首先被組織進(jìn)內(nèi)部堆中去，然后再以適當(dāng)?shù)男问椒祷亟o調(diào)用者。當(dāng)程序釋放分配的內(nèi)存空間時(shí)， 這片內(nèi)存空間被返回內(nèi)部堆結(jié)構(gòu)中，可能會(huì)被適當(dāng)?shù)奶幚?比如和其他空閑空間合并成更大的空閑空間)，以更適合下一次內(nèi)存分配申請(qǐng)。這套復(fù)雜的分配機(jī)制實(shí)際 上相當(dāng)于一個(gè)內(nèi)存分配的緩沖池(Cache)，使用這套機(jī)制有如下若干原因：???
???
??? 1. ? 系統(tǒng)調(diào)用可能不支持任意大小的內(nèi)存分配。有些系統(tǒng)的系統(tǒng)調(diào)用只支持固定大小及其倍數(shù)的內(nèi)存請(qǐng)求(按頁(yè)分配)；這樣的話對(duì)于大量的小內(nèi)存分類來(lái)說(shuō)會(huì)造成浪費(fèi)。???
???
??? 2. ? 系統(tǒng)調(diào)用申請(qǐng)內(nèi)存可能是代價(jià)昂貴的。系統(tǒng)調(diào)用可能涉及用戶態(tài)和核心態(tài)的轉(zhuǎn)換。???
???
??? 3. ? 沒(méi)有管理的內(nèi)存分配在大量復(fù)雜內(nèi)存的分配釋放操作下很容易造成內(nèi)存碎片。???
???
??? 堆和棧的對(duì)比???
???
??? 從以上知識(shí)可知，棧是系統(tǒng)提供的功能，特點(diǎn)是快速高效，缺點(diǎn)是有限制，數(shù)據(jù)不靈活；而堆是函數(shù)庫(kù)提供的功能，特點(diǎn)是靈活方便，數(shù)據(jù)適應(yīng)面廣泛，但是效率有 一定降低。棧是系統(tǒng)數(shù)據(jù)結(jié)構(gòu)，對(duì)于進(jìn)程/線程是唯一的；堆是函數(shù)庫(kù)內(nèi)部數(shù)據(jù)結(jié)構(gòu)，不一定唯一。不同堆分配的內(nèi)存無(wú)法互相操作。?？臻g分靜態(tài)分配和動(dòng)態(tài)分配 兩種。靜態(tài)分配是編譯器完成的，比如自動(dòng)變量(auto)的分配。動(dòng)態(tài)分配由alloca函數(shù)完成。棧的動(dòng)態(tài)分配無(wú)需釋放(是自動(dòng)的)，也就沒(méi)有釋放函 數(shù)。為可移植的程序起見(jiàn)，棧的動(dòng)態(tài)分配操作是不被鼓勵(lì)的！堆空間的分配總是動(dòng)態(tài)的，雖然程序結(jié)束時(shí)所有的數(shù)據(jù)空間都會(huì)被釋放回系統(tǒng)，但是精確的申請(qǐng)內(nèi)存/ 釋放內(nèi)存匹配是良好程序的基本要素。