4
．解釋堆和棧的區(qū)別。
| | 區(qū)別 | 棧 | 堆 |
| OS意義上的區(qū)別 | 從內(nèi)存上講 | 由編譯器自動(dòng)分配釋放 ，存放函數(shù)的參數(shù)值，局部變量的值等。其操作方式類似于數(shù)據(jù)結(jié)構(gòu)中的棧。 | 一般由程序員分配釋放，若程序員不釋放，程序結(jié)束時(shí)可能由OS回收 。注意它與數(shù)據(jù)結(jié)構(gòu)中的堆是兩回事，分配方式倒是類似于鏈表. |
| 申請(qǐng)方式 | 由系統(tǒng)自動(dòng)分配。 例如，聲明在函數(shù)中一個(gè)局部變量 int b; 系統(tǒng)自動(dòng)在棧中為b開(kāi)辟空間? | 需要程序員自己申請(qǐng)，并指明大小，如c中malloc函數(shù)，c++中的new. |
| 申請(qǐng)后系統(tǒng)響應(yīng) | 只要棧的剩余空間大于所申請(qǐng)空間，系統(tǒng)將為程序提供內(nèi)存，否則將報(bào)異常提示棧溢出。? | 較復(fù)雜些，需要OS有一個(gè)記錄空閑內(nèi)存地址的鏈表 |
| 申請(qǐng)大小 | 在Windows下,棧是向低地址擴(kuò)展的數(shù)據(jù)結(jié)構(gòu)，是一塊連續(xù)的內(nèi)存的區(qū)域。空間限制在2M以內(nèi)。 | 堆是向高地址擴(kuò)展的數(shù)據(jù)結(jié)構(gòu)，是不連續(xù)的內(nèi)存區(qū)域。受虛存限制，空間可以很大（32位機(jī)4G）。 |
| 申請(qǐng)效率 | 棧由系統(tǒng)自動(dòng)分配，速度較快。但程序員是無(wú)法控制的。? | 堆是由new分配的內(nèi)存，一般速度比較慢，而且容易產(chǎn)生內(nèi)存碎片,不過(guò)用起來(lái)最方便.? |
| 存儲(chǔ)內(nèi)容 | 在函數(shù)調(diào)用時(shí)，第一個(gè)進(jìn)棧的是主函數(shù)中后的下一條指令（函數(shù)調(diào)用語(yǔ)句的下一條可執(zhí)行語(yǔ)句）的地址，然后是函數(shù)的各個(gè)參數(shù)，在大多數(shù)的C編譯器中，參數(shù)是由右往左入棧的，然后是函數(shù)中的局部變量。注意靜態(tài)變量是不入棧的。 | 一般是在堆的頭部用一個(gè)字節(jié)存放堆的大小。堆中的具體內(nèi)容有程序員安排。 |
| 存取效率 | 較快 | 較慢 |
| 數(shù)據(jù)結(jié)構(gòu)意義上的區(qū)別 | 定義 | 堆是個(gè)有意思的數(shù)據(jù)結(jié)構(gòu)，從邏輯上講，它是個(gè)完全二叉樹。它的兩個(gè)基本特點(diǎn):
一是，堆為順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)的完全二叉樹；
二是，此樹局部有序。
特點(diǎn)一大家都明白，特點(diǎn)二卻是在說(shuō)，比如最大堆，它不象排序二叉樹那樣是完全有序的，對(duì)于每一棵子樹（當(dāng)然也包括樹本身）的根，其值總是在左、右孩子結(jié)點(diǎn)中為最大的，而左、右孩子結(jié)點(diǎn)卻不一定有序。 | 棧（Stack）是限定只能在表的一端進(jìn)行插入和刪除操作的線性表。在表中，允許插入和刪除的一端稱作"棧頂(top)"，不允許插入和刪除的另一端稱作"棧底(bottom)" 。 |
| 用途 | 堆的用途，當(dāng)然很多了，大家最容易想到的，就是堆排序。 | 常用于系統(tǒng)中。 |
posted on 2006-09-07 18:14
創(chuàng)建更好的解決方案 閱讀(1073)
評(píng)論(0) 編輯 收藏 引用