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

堆

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

棧

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

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

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

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

延伸閱讀：

二、鏈表與數(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ù)組不能往后加，只能通過定義新的數(shù)組

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

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

上一篇

項(xiàng)目計(jì)劃管理怎么考核?

下一篇

用鏈表的目的是什么?