深入理解堆和棧

引言

堆和棧是經常看到的兩個名詞了，以至于太平常反而沒有區深入了解它們，導致一些概念區分不清楚。實際上對堆和棧的理解需要從數據結構和操作系統這兩個層面來理解，因為在這兩種情形下它們的含義有些差別。

1.數據結構中的堆和棧

1.1 數據結構中的堆

目前國內教材中關于堆的定義非常多，大多數都不夠嚴謹，我個人比較推崇Wikipedia中關于堆的定義：堆(Heap)是計算機科學中一類特殊的數據結構的統稱。堆通常是一個可以被看做一棵樹的數組對象。在隊列中，調度程序反復提取隊列中第一個作業并運行，因為實際情況中某些時間較短的任務將等待很長時間才能結束，或者某些不短小，但具有重要性的作業，同樣應當具有優先權。堆即為解決此類問題設計的一種數據結構。

概括起來說就是: 堆是一類特殊的數據結構，它的作用是解決優先級隊列問題。只不過堆的實現一般都是采用二叉樹的方式，因而我們平常說的堆，不加特殊說明時，一般就是指二叉堆這種實現。

堆的性質如下:

+ 任意節點小于(或大于)它的左右孩子節點，最小元素(或最大元素)在堆的根上; + 堆總是一棵完全二叉樹,即除了最底層，其他層的節點都被元素填滿，且最低層盡可能地從左到右填入

將根節點最大的堆叫做最大堆或大根堆，根節點最小的堆叫做最小堆或小根堆。常見的堆有二叉堆、斐波那契堆等。

如下就是一個典型的堆示意圖:

堆的插入過程

新插入的節點放在完全二叉樹最后的位置，再和父節點比較。如果新節點比父節點小，那么交換兩者。交換之后，繼續和新的父節點比較，直到新節點不比父節點小，或者新節點成為根節點。這樣得到的樹，就保持著堆的性質。

示意圖如下:

堆的刪除

堆的刪除操作只能刪除根節點，根節點刪除后，我們會有兩個子樹，我們需要基于它們重構堆。重構的方法為：讓原來的最后一個節點(last)成為根節點，之后根據堆的性質進行調整。如果last大于它的某個子節點，則和該子節點進行交換。直到last節點不大于任一子節點，或者last節點成為葉節點。

示意圖如下:

1.2 數據結構中的棧

棧是一種先進后出的線性表，只要符合先進后出的原則的線性表都是棧。至于采用的存儲方式（實現方式）是順序存儲（順序棧）還是鏈式存儲（鏈式棧）是沒有關系的。棧的操作和代碼實現都非常簡單，這里不再贅述。

2.操作系統中的堆和棧

先來看一下一個C/C++程序中的內存分配:

• 堆區:一般由程序員分配釋放，若程序員不釋放，程序結束時可能由OS回收。注意它與數據結構中的堆是兩回事，分配方式倒是類似于鏈表。
• 棧區:由編譯器自動分配釋放，用于放函數的參數值，局部變量的值等。其操作方式類似于數據結構中的棧。
• 全局區(靜態區):全局變量和靜態變量的存儲是放在一塊的，初始化的全局變量和靜態變量在一塊區域， 未初始化的全局變量和未初始化的靜態變量在相鄰的另一塊區域。
• 文字常量區:常量字符串就是放在這里的，程序結束后由系統釋放
• 程序代碼區：存放函數體的二進制代碼

所以可以簡單的理解為:

heap：是由malloc之類函數分配的空間所在地,用于存放對象。地址是由低向高增長的。

stack：是自動分配變量，以及函數調用的時候所使用的一些空間。地址是由高向低減少的。

2.1 堆和棧申請大小的限制

堆：堆是向高地址擴展的數據結構，是不連續的內存區域。這是由于系統是用鏈表來存儲空閑地址的，而鏈表的遍歷方向是由低地址向高地址。堆的大小受限于計算機系統中有效的虛擬內存。由此可見，堆獲得的空間比較靈活，也比較大。

棧：在Windows下，棧是向低地址擴展的數據結構，是一塊連續的內存區域。這句話的意思是棧頂的地址和棧的最大容量是系統預先規定好的，在 WINDOWS下，棧的大小是2M（也有的說是1M，總之是一個編譯時就確定的常數），如果申請的空間超過棧的剩余空間時，將提示overflow。因 此，能從棧獲得的空間較小。在Linux中棧最大只能為10M.

2.2 申請效率的比較

棧由系統自動分配，速度較快。但程序員是無法控制的。

堆是由new分配的內存，一般速度比較慢，而且容易產生內存碎片,不過用起來最方便.

2.3 存儲內容的比較

stack:在函數調用時，第一個進棧的是主函數中后的下一條指令（函數調用語句的下一條可執行語句）的地址，然后是函數的各個參數，在大多數的C編譯器中，參數是由右往左入棧的，然后是函數中的局部變量。注意靜態變量是不入棧的。

當本次函數調用結束后，局部變量先出棧，然后是參數，最后棧頂指針指向最開始存的地址，也就是主函數中的下一條指令，程序由該點繼續運行。

heap:一般在堆的頭部用一個字節存放堆的大小。堆中的具體內容由程序員安排。

2.4 總結

堆和棧的區別可以用如下的比喻來看出：

使用棧就象我們去飯館里吃飯，只管點菜（發出申請）、付錢、和吃（使用），吃飽了就走，不必理會切菜、洗菜等準備工作和洗碗、刷鍋等掃尾工作，他的好處是快捷，但是自由度小。

使用堆就象是自己動手做喜歡吃的菜肴，比較麻煩，但是比較符合自己的口味，而且自由度大。

 

來自：http://blog.imallen.wang/blog/2016/11/20/shen-ru-li-jie-dui-he-zhan/