一、堆和棧，他們之間的區別和聯系

堆

數據結構中堆是滿足父子節點大?。ū热绱蟾阎幸幎ǜ腹濣c的值要比子節點大）關系的一種完全二叉樹。由于是完全二叉樹，可以用數組來實現，用節點編號來訪問和操作節點，簡化程序，提升效率。而其大小關系則為我們查詢堆中極值提供了常數級別的時間復雜度，又由二叉樹的性質，插入和刪除則為對數級別時間復雜度。這就好像地位不同的人在排隊，排在最前面的一定是地位較高的人，所以堆是優先隊列（Priority Queue）實現的基礎。利用這一特性，可以加速某些需要頻繁取隊列中極值的算法比如 A* 算法等。

棧

數據結構中的棧則是一種相當簡單的結構。就像是只有一個口的深深的文件桶，先進去的文件會被壓在下面（push），而且我們每次只能取到最上面的文件（pop），體現了其先進后出（FILO）的特性。雖然棧操作簡單，但也有如單調棧等在棧內保持一定數據特性的變種。

聯系與區別

操作系統中的堆和棧都是指內存空間，不同的是堆為按需申請、動態分配，例如 C 中的 malloc 函數和 C++ 中的 new 操作（當然 C++ 的 new 不僅僅是申請內存這么簡單）。內存中的空閑空間并不是連續的，而是不同程序占用了不同的一塊一塊的內存，即使是同一個程序也可能占用了不同地方的多塊內存。操作系統中則會對這些空間進行統一的管理，在應用程序提出申請時，就會從堆中按照一定算法找出一塊可用內存，標記占用空間等信息之后返回其起始地址給程序。在程序結束之前，操作系統不會刪除已經申請的內存，而是要靠程序主動提出釋放的請求（free、delete），如果使用后忘記釋放，就會造成所謂的內存泄漏問題。因此堆基本上可以理解為當前可以使用的空閑內存，但是其申請和釋放都要程序員自己寫代碼管理。

而操作系統的棧則是程序運行時自動擁有的一小塊內存，大小在編譯期時由編譯器參數決定，用于局部變量的存放或者函數調用棧的保存。在 C 中如果聲明一個局部變量（例如 int a），它存放的地方就在棧中，而當這個局部變量離開其作用域之后，所占用的內存則會被自動釋放，因此在 C 中局部變量也叫自動變量。棧的另一個作用則是保存函數調用棧，這時和數據結構的棧就有關系了。在函數調用過程中，常常會多層甚至遞歸調用。每一個函數調用都有各自的局部變量值和返回值，每一次函數調用其實是先將當前函數的狀態壓棧，然后在棧頂開辟新空間用于保存新的函數狀態，接下來才是函數執行。當函數執行完畢之后，棧先進后出的特性使得后調用的函數先返回，這樣可以保證返回值的有序傳遞，也保證函數現場可以按順序恢復。操作系統的棧在內存中高地址向低地址增長，也即低地址為棧頂，高地址為棧底。這就導致了棧的空間有限制，一旦局部變量申請過多（例如開個超大數組），或者函數調用太深（例如遞歸太多次），那么就會導致棧溢出（Stack Overflow），操作系統這時候就會直接把你的程序殺掉。

延伸閱讀：

二、鏈表與數組的區別

數組：使用一塊連續的內存空間地址去存放數據，例如：

int? a[5]={1,2,3,4,5}。突然我想繼續加兩個數據進去，但是已經定義好的數組不能往后加，只能通過定義新的數組

int b[7]={1,2,3,4,5,6,7}; 這樣就相當不方便比較浪費內存資源,對數據的增刪不好操作。

鏈表：使用多個不連續的內存空間去存儲數據，可以節省內存資源（只有需要存儲數據時，才去劃分新的空間），對數據的增刪比較方便。