一、堆和棧,他們之間的區(qū)別和聯(lián)系
堆
數(shù)據(jù)結(jié)構(gòu)中堆是滿足父子節(jié)點(diǎn)大小(比如大根堆中規(guī)定父節(jié)點(diǎn)的值要比子節(jié)點(diǎn)大)關(guān)系的一種完全二叉樹。由于是完全二叉樹,可以用數(shù)組來(lái)實(shí)現(xiàn),用節(jié)點(diǎn)編號(hào)來(lái)訪問(wèn)和操作節(jié)點(diǎn),簡(jiǎn)化程序,提升效率。而其大小關(guān)系則為我們查詢堆中極值提供了常數(shù)級(jí)別的時(shí)間復(fù)雜度,又由二叉樹的性質(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)和釋放都要程序員自己寫代碼管理。
而操作系統(tǒng)的棧則是程序運(yùn)行時(shí)自動(dòng)擁有的一小塊內(nèi)存,大小在編譯期時(shí)由編譯器參數(shù)決定,用于局部變量的存放或者函數(shù)調(diào)用棧的保存。在 C 中如果聲明一個(gè)局部變量(例如 int a),它存放的地方就在棧中,而當(dāng)這個(gè)局部變量離開其作用域之后,所占用的內(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)壓棧,然后在棧頂開辟新空間用于保存新的函數(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ò)多(例如開個(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ù)的增刪比較方便。