一、堆和棧,他們之間的區別和聯系
堆
數據結構中堆是滿足父子節點大小(比如大根堆中規定父節點的值要比子節點大)關系的一種完全二叉樹。由于是完全二叉樹,可以用數組來實現,用節點編號來訪問和操作節點,簡化程序,提升效率。而其大小關系則為我們查詢堆中極值提供了常數級別的時間復雜度,又由二叉樹的性質,插入和刪除則為對數級別時間復雜度。這就好像地位不同的人在排隊,排在最前面的一定是地位較高的人,所以堆是優先隊列(Priority Queue)實現的基礎。利用這一特性,可以加速某些需要頻繁取隊列中極值的算法比如 A* 算法等。
棧
數據結構中的棧則是一種相當簡單的結構。就像是只有一個口的深深的文件桶,先進去的文件會被壓在下面(push),而且我們每次只能取到最上面的文件(pop),體現了其先進后出(FILO)的特性。雖然棧操作簡單,但也有如單調棧等在棧內保持一定數據特性的變種。
聯系與區別
操作系統中的堆和棧都是指內存空間,不同的是堆為按需申請、動態分配,例如 C 中的 malloc 函數和 C++ 中的 new 操作(當然 C++ 的 new 不僅僅是申請內存這么簡單)。內存中的空閑空間并不是連續的,而是不同程序占用了不同的一塊一塊的內存,即使是同一個程序也可能占用了不同地方的多塊內存。操作系統中則會對這些空間進行統一的管理,在應用程序提出申請時,就會從堆中按照一定算法找出一塊可用內存,標記占用空間等信息之后返回其起始地址給程序。在程序結束之前,操作系統不會刪除已經申請的內存,而是要靠程序主動提出釋放的請求(free、delete),如果使用后忘記釋放,就會造成所謂的內存泄漏問題。因此堆基本上可以理解為當前可以使用的空閑內存,但是其申請和釋放都要程序員自己寫代碼管理。
而操作系統的棧則是程序運行時自動擁有的一小塊內存,大小在編譯期時由編譯器參數決定,用于局部變量的存放或者函數調用棧的保存。在 C 中如果聲明一個局部變量(例如 int a),它存放的地方就在棧中,而當這個局部變量離開其作用域之后,所占用的內存則會被自動釋放,因此在 C 中局部變量也叫自動變量。棧的另一個作用則是保存函數調用棧,這時和數據結構的棧就有關系了。在函數調用過程中,常常會多層甚至遞歸調用。每一個函數調用都有各自的局部變量值和返回值,每一次函數調用其實是先將當前函數的狀態壓棧,然后在棧頂開辟新空間用于保存新的函數狀態,接下來才是函數執行。當函數執行完畢之后,棧先進后出的特性使得后調用的函數先返回,這樣可以保證返回值的有序傳遞,也保證函數現場可以按順序恢復。操作系統的棧在內存中高地址向低地址增長,也即低地址為棧頂,高地址為棧底。這就導致了棧的空間有限制,一旦局部變量申請過多(例如開個超大數組),或者函數調用太深(例如遞歸太多次),那么就會導致棧溢出(Stack Overflow),操作系統這時候就會直接把你的程序殺掉。
延伸閱讀:
二、鏈表與數組的區別
數組:使用一塊連續的內存空間地址去存放數據,例如:
int? a[5]={1,2,3,4,5}。突然我想繼續加兩個數據進去,但是已經定義好的數組不能往后加,只能通過定義新的數組
int b[7]={1,2,3,4,5,6,7}; 這樣就相當不方便比較浪費內存資源,對數據的增刪不好操作。
鏈表:使用多個不連續的內存空間去存儲數據,可以節省內存資源(只有需要存儲數據時,才去劃分新的空間),對數據的增刪比較方便。