一、堆和棧，他們之間的區(qū)別和聯(lián)系

堆

數(shù)據(jù)結(jié)構(gòu)中堆是滿(mǎn)足父子節(jié)點(diǎn)大?。ū热绱蟾阎幸?guī)定父節(jié)點(diǎn)的值要比子節(jié)點(diǎn)大）關(guān)系的一種完全二叉樹(shù)。由于是完全二叉樹(shù)，可以用數(shù)組來(lái)實(shí)現(xiàn)，用節(jié)點(diǎn)編號(hào)來(lái)訪問(wèn)和操作節(jié)點(diǎn)，簡(jiǎn)化程序，提升效率。而其大小關(guān)系則為我們查詢(xún)堆中極值提供了常數(shù)級(jí)別的時(shí)間復(fù)雜度，又由二叉樹(shù)的性質(zhì)，插入和刪除則為對(duì)數(shù)級(jí)別時(shí)間復(fù)雜度。這就好像地位不同的人在排隊(duì)，排在最前面的一定是地位較高的人，所以堆是優(yōu)先隊(duì)列（Priority Queue）實(shí)現(xiàn)的基礎(chǔ)。利用這一特性，可以加速某些需要頻繁取隊(duì)列中極值的算法比如 A* 算法等。

棧

數(shù)據(jù)結(jié)構(gòu)中的棧則是一種相當(dāng)簡(jiǎn)單的結(jié)構(gòu)。就像是只有一個(gè)口的深深的文件桶，先進(jìn)去的文件會(huì)被壓在下面（push），而且我們每次只能取到最上面的文件（pop），體現(xiàn)了其先進(jìn)后出（FILO）的特性。雖然棧操作簡(jiǎn)單，但也有如單調(diào)棧等在棧內(nèi)保持一定數(shù)據(jù)特性的變種。

聯(lián)系與區(qū)別

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

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

延伸閱讀：

二、鏈表與數(shù)組的區(qū)別

數(shù)組：使用一塊連續(xù)的內(nèi)存空間地址去存放數(shù)據(jù)，例如：

int? a[5]={1,2,3,4,5}。突然我想繼續(xù)加兩個(gè)數(shù)據(jù)進(jìn)去，但是已經(jīng)定義好的數(shù)組不能往后加，只能通過(guò)定義新的數(shù)組

int b[7]={1,2,3,4,5,6,7}; 這樣就相當(dāng)不方便比較浪費(fèi)內(nèi)存資源,對(duì)數(shù)據(jù)的增刪不好操作。

鏈表：使用多個(gè)不連續(xù)的內(nèi)存空間去存儲(chǔ)數(shù)據(jù)，可以節(jié)省內(nèi)存資源（只有需要存儲(chǔ)數(shù)據(jù)時(shí)，才去劃分新的空間），對(duì)數(shù)據(jù)的增刪比較方便。