棧和堆以及棧區(qū)和堆區(qū)的區(qū)別
數(shù)據(jù)結(jié)構(gòu)中的棧和堆
- 棧：具有先進(jìn)后出性質(zhì)的數(shù)據(jù)結(jié)構(gòu)
- 堆：一種經(jīng)過排序的樹形數(shù)據(jù)結(jié)構(gòu)，節(jié)點的值最大/小，且根節(jié)點的兩個子樹也是一個堆，一般指二叉堆，常用來實現(xiàn)優(yōu)先隊列
進(jìn)程的內(nèi)存模型中的棧區(qū)和堆區(qū)
空間分配機(jī)制：
- 棧區(qū)：由編譯器自動分配釋放，存放函數(shù)的參數(shù)值，局部變量值等，操作類似于數(shù)據(jù)結(jié)構(gòu)中的棧。只要棧的剩余空間大于所申請空間，系統(tǒng)將為程序提供內(nèi)存，否則將報異常提示棧溢出，一般 Linux 為 8MB(ulimit -a 查看)
- 堆區(qū)：一般由程序員/用戶程序通過 malloc 或 free 等分配釋放，若程序員/用戶程序不主動釋放，程序結(jié)束時可能由操作系統(tǒng)回收，分配和維護(hù)方式類似于鏈表。
操作系統(tǒng)有一個記錄空閑內(nèi)存地址的鏈表，當(dāng)系統(tǒng)收到程序的申請時， 會遍歷該鏈表，尋找第一個空間大于所申請空間的堆結(jié)點，然后將該結(jié)點從空閑結(jié)點鏈表中刪除，并將該結(jié)點的空間分配給程序，另外，對于大多數(shù)系統(tǒng)，會在這塊內(nèi)存空間中的首地址處記錄本次分配的大小，這樣，代碼中的delete語句才能正確的釋放本內(nèi)存空間。另外，由于找到的堆結(jié)點的大小不一定正好等于申請的大小，系統(tǒng)會自動的將多余的那部分重新放入空閑鏈表中。
申請和存取效率比較：
- 棧：棧由系統(tǒng)自動分配，速度較快。但程序員是無法控制的。訪問時，由于直接將數(shù)據(jù)讀取到寄存器，尋址速度較快
- 堆：由new分配的內(nèi)存，一般速度比較慢，而且容易產(chǎn)生內(nèi)存碎片,不過用起來最方便。訪問時，需要先把指向堆上數(shù)據(jù)的指針讀入寄存器，然后讀取數(shù)據(jù)，較慢
Ref:
