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