詳解 Stack 與 Heap 之間的特性與差異
前前言
最近由於工作上的需要，也出自於想重新審視自己在軟體工程師這條路上所欠缺的能力，因此計畫打算參照 John Washam 所撰寫的著名文章: Coding Interview University 裡面的內容來一步步研讀與核對自己不熟悉的地方，期許自己在經過此次的計畫後能更具備一位成熟工程師所需要的知識與技巧。
前言
堆(Heap)與棧(Stack)為軟體開發人員需要具備的基礎觀念之一，這兩個名詞在不同的背景下有不同的代表意思:
在程式內存的討論中: 堆與棧表示了兩種不同的內存管理方式
在資料結構的討論中: 堆與棧表示了兩種不同的資料儲存結構
即便兩者的代表意思不同，但其背後的原理與概念大致相同，因此這邊介紹會直接以程式記憶體的角度做切入。
先來看一張程式啟動時記憶體的分配狀態圖:
資料結構中的棧
Stack 是一種只允許在儲存容器的一端進行插入和删除的動作，稱為棧頂 (Stack Top)，操作採取先進後出(First in-Last out，FILO)的資料堆疊儲存方式。當把新元素放到棧頂元素的上面，使之成為新的棧頂元素稱作進棧、入棧或壓棧（Push）; 把棧頂元素删除，使其相鄰的元素成為新的棧頂元素稱作出棧或退棧（Pop )。
程式內存中的棧
Stack 由作業系統自動管理，用於儲存程式中 Function 的呼叫、傳入參數以及所有區域變數，採取先進後出的方式依序堆疊放置在棧內，相鄰變數對應的地址間不會存在其它变量，並且其數據在生命週期結束後由系統回收取出。另外，Stack在記憶體位置上的生長方向是由高往低生長，越後面進入 Stack 中的變量其對應的記憶體位址也越小。
每個程式所分配到的 Stack 大小在編譯完成就固定了，若是在執行的過程中要塞入 Stack 中的數據大小大於 Stack 中所剩餘的儲存空間，此時就會爆出記憶體空間不足。 (Stack Overflow!)
資料結構中的堆
堆是一種樹形資料結構的通稱，是特化過的的完全二分法樹，其滿足樹中所有節點的值總是不大於（或不小於）父節點的值，此特性又稱作堆序性。在堆中根節點是最大（或最小）節点。擁有最小根節點稱之為小根堆，最大根節點稱之為大根堆。另外堆的左右子節點没有大小順序的差別。對堆中任意節點的插入、刪除以及建立都要滿足此一堆序性。
程式內存中的堆
Heap 用於儲存程式運行期間動態分配的記憶體區域，由程式人員分配與釋放，可以適應不同大小和數量的資料。Heap 在可分配的空間大小上比其 Stack 來的大上許多，使用上也較彈性。
但是，它也存在一些缺點。由於 heap 是手動管理的，必須確保每個分配的內存塊都被正確地釋放，否則就會產生內存泄漏（memory leak），這會導致系統資源的浪費和性能問題，如果開發人員沒有正當的回收使用到的 Heap 區域記憶體的話會直到程式結束執行時由作業系統回收。
此外，請求 heap 記憶體區塊時時需要與作業系統溝通，因此速度會比 stack 來的較慢。另外，由於 heap 是透過上述的特化二分樹來儲存，從作業系統中閒置的記憶體區塊分割出來記憶體區段會掛在相對應的節點上，因此申請的記憶體空間在地址上不一定是連續的，並且其記憶體位址生長方向是由低往到高生長，但後進入的變數位址不一定大於先進入的變數位址(呼應前面提到的不連續性)。
總結
- 記憶體位址生長方向: Stack 由高到低、Heap 由低到高
- 請求速度: Stack 較快、Heap 較慢
- 空間大小: Stack 較小、Heap 較大
- 分配方式: Stack 由系統自動發放、Heap 由程式人員分配釋放
- 數據結構: Stack 是先進後出、Heap 是特化二分樹
希望在看完上述內容後可以快速複習與更加深 Stack 與 Heap 之間的特性與差異之處。
補充: C++ 中的 Heap 與 Stack
C++ 的語言概念中其實並沒有 Heap 或 Stack 之類的概念，相反地是使用資料的 Storage Behaviour 來區分，如 automatic storage、 dynamic storage、static storage and thread local storage. 每個 storage 依其實現方式再來區分其資料儲存於哪一區。
參考資料
