什么是堆什么是棧

1、一英文名稱堆和棧是CC編程中經(jīng)常遇到的兩個(gè)基本概念。先看一下它們的英文表示：堆――heap棧――stack二從數(shù)據(jù)結(jié)構(gòu)和系統(tǒng)兩個(gè)層次理解在具體的CC編程框架中，這兩個(gè)概念并不是并行的。深入到匯編級(jí)進(jìn)行研究就會(huì)發(fā)現(xiàn)，棧是機(jī)器系統(tǒng)提供的數(shù)據(jù)結(jié)構(gòu)，而堆是由CC函數(shù)庫(kù)提供的。這兩個(gè)概念可以從數(shù)據(jù)結(jié)構(gòu)和系統(tǒng)兩個(gè)層次去理解：1、從數(shù)據(jù)結(jié)構(gòu)層次理解，棧是一種先進(jìn)后出的線性表，只要符合先進(jìn)后出的原則的線性表都是棧。至于采用的存儲(chǔ)方式（實(shí)現(xiàn)方式）是順序存

2、儲(chǔ)（順序棧）還是鏈?zhǔn)酱鎯?chǔ)（鏈?zhǔn)綏＃┦菦](méi)有關(guān)系的。堆則是二叉樹(shù)的一種，有最大堆最小堆，排序算法中有常用的堆排序。2、從系統(tǒng)層次理解，棧是系統(tǒng)為運(yùn)行的程序分配的先進(jìn)后出的存儲(chǔ)區(qū)域。在學(xué)習(xí)bootloader時(shí)知道，在上電后初始化階段要為各個(gè)工作模式下分配堆棧，這里的堆棧實(shí)際上就是指stack，堆棧的說(shuō)法只是因?yàn)闅v史的原因。在執(zhí)行函數(shù)時(shí)，函數(shù)內(nèi)部局部變量的存儲(chǔ)單元可以在棧上創(chuàng)建（針對(duì)CISC架構(gòu)而言，RISC架構(gòu)下，局部變量的存儲(chǔ)單元是在寄存

3、器上創(chuàng)建），函數(shù)執(zhí)行結(jié)束時(shí)這些存儲(chǔ)單元自動(dòng)被釋放。堆是系統(tǒng)管理的可以被程序利用的全局存儲(chǔ)空間，動(dòng)態(tài)內(nèi)存分配就是從堆上分配。具體地說(shuō)，現(xiàn)在計(jì)算機(jī)（串行執(zhí)行機(jī)制），都直接在代碼層次支持棧這種數(shù)據(jù)結(jié)構(gòu)。這體現(xiàn)在，有專門(mén)的寄存器指向棧所在的地址，有專門(mén)的機(jī)器指令完成數(shù)據(jù)入棧出棧的操作。比如ARM指令中的stmfd和ldmfd。因?yàn)闂?nèi)存分配運(yùn)算內(nèi)置于處理器的指令集中，所以效率很高，但是支持的數(shù)據(jù)有限，一般是整數(shù)、指針、浮點(diǎn)數(shù)等系統(tǒng)直接支持的數(shù)據(jù)

4、類型，并不直接支持其他的數(shù)據(jù)結(jié)構(gòu)。在CISC中，對(duì)子程序的調(diào)用就是利用棧來(lái)完成的。CC中的自動(dòng)變量也是直接利用棧的例子，這就是為什么當(dāng)函數(shù)返回時(shí)，該函數(shù)的自動(dòng)變量失效的原因（因?yàn)闂；謴?fù)了調(diào)用前的狀態(tài)）。在RISC下，這些都是通過(guò)寄存器來(lái)完成的。這些留待第二部分總結(jié)中詳細(xì)闡述。和棧不同，堆的數(shù)據(jù)結(jié)構(gòu)并不是由系統(tǒng)（無(wú)論是機(jī)器系統(tǒng)還是操作系統(tǒng)）支持的，而是由函數(shù)庫(kù)提供的?；镜膍allocfree函數(shù)維護(hù)了一套內(nèi)部的堆數(shù)據(jù)結(jié)構(gòu)。當(dāng)程序使用這些

5、函heap：程序員自己申請(qǐng)，指明大小。2、申請(qǐng)后系統(tǒng)響應(yīng)stack：只要棧的剩余空間大于所申請(qǐng)空間，系統(tǒng)將為程序提供內(nèi)存，否則將報(bào)異常提示棧溢出。heap：首先應(yīng)該知道操作系統(tǒng)有一個(gè)記錄空閑內(nèi)存地址的鏈表，當(dāng)系統(tǒng)收到程序的申請(qǐng)時(shí)會(huì)遍歷該鏈表，尋找第一個(gè)空間大于所申請(qǐng)空間的堆結(jié)點(diǎn)，然后將該結(jié)點(diǎn)從空閑結(jié)點(diǎn)鏈表中刪除，并將該結(jié)點(diǎn)的空間分配給程序，另外，對(duì)于大多數(shù)系統(tǒng)，會(huì)在這塊內(nèi)存空間中的首地址處記錄本次分配的大小，這樣，代碼中的語(yǔ)句才能正確的

6、釋放本內(nèi)存空間。另外，由于找到的堆結(jié)點(diǎn)的大小不一定正好等于申請(qǐng)的大小，系統(tǒng)會(huì)自動(dòng)的將多余的那部分重新放入空閑鏈表中。3、申請(qǐng)大小的限制stack：在ARM中，stack預(yù)先設(shè)置好。在start.S中，可以有四種不同的棧：滿棧遞增，滿棧遞減，空棧遞增，空棧遞減。常用的是滿棧遞減，就是向下（低地址）方向生長(zhǎng)。如果分析bootloader的stack設(shè)置部分，這個(gè)很容易理解。heap：是向高地址擴(kuò)展的數(shù)據(jù)結(jié)構(gòu)，是不連續(xù)的內(nèi)存區(qū)域。這是由于系統(tǒng)

7、是用鏈表來(lái)存儲(chǔ)的空閑內(nèi)存地址的，自然是不連續(xù)的，而鏈表的遍歷方向是由低地址向高地址。堆的大小受限于計(jì)算機(jī)系統(tǒng)中有效的虛擬內(nèi)存。由此可見(jiàn)，堆獲得的空間比較靈活，也比較大。4、申請(qǐng)效率比較stack：由系統(tǒng)自動(dòng)分配，速度較快。但程序員是無(wú)法控制的。heap：由new分配的內(nèi)存，一般速度比較慢，而且容易產(chǎn)生內(nèi)存碎片不過(guò)用起來(lái)最方便。5、存儲(chǔ)內(nèi)容stack：在函數(shù)調(diào)用時(shí)，第一個(gè)進(jìn)棧的是主函數(shù)中后的下一條指令（函數(shù)調(diào)用語(yǔ)句的下一條可執(zhí)行語(yǔ)句）的地