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

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

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