|
|
堆棧就是這樣一種數(shù)據(jù)結(jié)構(gòu)。它是在內(nèi)存中開辟一個(gè)存儲(chǔ)區(qū)域，數(shù)據(jù)一個(gè)一個(gè)順序地存入（也就是“壓入——push”）這個(gè)區(qū)域之中。有一個(gè)地址指針總指向最后一個(gè)壓入堆棧的數(shù)據(jù)所在的數(shù)據(jù)單元，存放這個(gè)地址指針的寄存器就叫做堆棧指示器。開始放入數(shù)據(jù)的單元叫做“棧底”。數(shù)據(jù)一個(gè)一個(gè)地存入，這個(gè)過程叫做“壓�！薄Ｔ趬簵５倪^程中，每有一個(gè)數(shù)據(jù)壓入堆棧，就放在和前一個(gè)單元相連的后面一個(gè)單元中，堆棧指示器中的地址自動(dòng)加1。讀取這些數(shù)據(jù)時(shí)，按照堆棧指示器中的地址讀取數(shù)據(jù)，堆棧指示器中的地址數(shù)自動(dòng)減1。這個(gè)過程叫做“彈出pop”。如此就實(shí)現(xiàn)了后進(jìn)先出的原則。
堆棧是計(jì)算機(jī)中最常用的一種數(shù)據(jù)結(jié)構(gòu)，比如函數(shù)的調(diào)用在計(jì)算機(jī)中是用堆棧實(shí)現(xiàn)的。
堆棧可以用數(shù)組存儲(chǔ)，也可以用以后會(huì)介紹的鏈表存儲(chǔ)。
下面是一個(gè)堆棧的結(jié)構(gòu)體定義，包括一個(gè)棧頂指針，一個(gè)數(shù)據(jù)項(xiàng)數(shù)組。棧頂指針最開始指向-1,然后存入數(shù)據(jù)時(shí)，棧頂指針加1，取出數(shù)據(jù)后，棧頂指針減1。
堆和棧是兩個(gè)不同的概念。
簡(jiǎn)單的來講堆（heap）上分配的內(nèi)存，系統(tǒng)不釋放，而且是動(dòng)態(tài)分配的。棧（stack）上分配的內(nèi)存系統(tǒng)會(huì)自動(dòng)釋放，它是靜態(tài)分配的。運(yùn)行時(shí)棧叫堆棧。棧的分配是從內(nèi)存的高地址向低地址分配的，而堆則相反。
由malloc或new分配的內(nèi)存都是從heap上分配的內(nèi)存，從heap上分配的內(nèi)存必須有程序員自己釋放，用free來釋放，否則這塊內(nèi)存會(huì)一直被占用而得不到釋放，就出現(xiàn)了“內(nèi)存泄露（MemoryLeak）”。這樣會(huì)造成系統(tǒng)的可分配內(nèi)存的越來越少，導(dǎo)致系統(tǒng)崩潰。
簡(jiǎn)單的可以理解為：
heap：是由malloc之類函數(shù)分配的空間所在地。地址是由低向高增長(zhǎng)的。
stack：是自動(dòng)分配變量，以及函數(shù)調(diào)用的時(shí)候所使用的一些空間。地址是由高向低減少的。
棧：只要棧的剩余空間大于所申請(qǐng)空間，系統(tǒng)將為程序提供內(nèi)存，否則將報(bào)異常提示棧溢出。
堆：首先應(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)存空間中的首地址處記錄本次分配的大小，這樣，代碼中的delete語(yǔ)句才能正確的釋放本內(nèi)存空間。另外，由于找到的堆結(jié)點(diǎn)的大小不一定正好等于申請(qǐng)的大小，系統(tǒng)會(huì)自動(dòng)的將多余的那部分重新放入空閑鏈表中。
內(nèi)存碎片的理解：
1、你申請(qǐng)了一個(gè)4長(zhǎng)度的內(nèi)存。
2、你又申請(qǐng)了一個(gè)5長(zhǎng)度的內(nèi)存。
3、你釋放了1申請(qǐng)的4長(zhǎng)度的內(nèi)存。
4、你申請(qǐng)>;4長(zhǎng)度的內(nèi)存。因?yàn)?gt;;4，所以不會(huì)分配給前面的4個(gè)長(zhǎng)度中的內(nèi)存，那4個(gè)長(zhǎng)度的內(nèi)存就可以說是內(nèi)存碎片。
OS的各種內(nèi)存調(diào)度算法可以在不同程度上避免內(nèi)存碎片的出現(xiàn)，但是都不可能阻止。優(yōu)秀的程序員，會(huì)巧妙的安排程序的空間，盡量避免內(nèi)存碎片的出現(xiàn)。
|
|
QQ好友和群
QQ空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
