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