堆(heap)和棧(stack)是在計算機中常用的兩種數據結構。它們具有不同的特點和用途,對于程序員來說,了解堆和棧的區(qū)別是非常重要的。
首先,堆和棧的內存分配方式不同。堆是由程序員手動分配和釋放的,而棧是由操作系統(tǒng)自動分配和釋放的。在堆中,使用malloc()或new關鍵字來分配內存空間,通過free()或delete關鍵字來釋放內存。在棧中,變量的內存分配和釋放是由編譯器自動完成的,無需程序員干預。
其次,堆和棧的大小不同。棧的大小是固定的,一般在程序運行時就確定了,而堆的大小是動態(tài)增長的,可以根據需要動態(tài)地申請和釋放內存空間。
另外,堆和棧的數據訪問方式也有所不同。在堆中,數據的訪問是通過指針來實現的,需要通過指針尋址來訪問和操作數據。而在棧中,數據的訪問是通過變量名來實現的,可以直接訪問和操作變量。
堆和棧還有一個重要的區(qū)別是數據的生命周期。在堆中,數據的生命周期可以很長,需要手動釋放內存,否則會導致內存泄漏。而在棧中,變量的生命周期是由其所在的作用域來決定的,一旦離開作用域,變量就會被自動釋放。
在使用堆和棧時,還需要考慮到一些因素。堆是動態(tài)分配的,所以分配和釋放內存的速度較慢,并且可能會造成內存碎片的問題。棧是靜態(tài)分配的,所以分配和釋放內存的速度非??欤菞5拇笮∈怯邢薜模绻麑⒋罅康臄祿鎯υ跅V校赡軙е聴R绯龅膯栴}。
在實際應用中,堆和棧都有各自的使用場景。堆主要用于動態(tài)分配大量的內存空間,適合存儲復雜的數據結構,比如樹、圖等。棧主要用于保存函數的局部變量、參數值等,適合存儲簡單的數據類型。
總結起來,堆和棧在內存分配方式、大小、數據訪問方式、生命周期等方面有著不同的特點。程序員需要根據具體的需求,選擇合適的數據結構和內存分配方式,以提高程序的性能和效率
堆與棧的區(qū)別:空間分配棧操作系統(tǒng)自動分配釋放,堆由程序員分配釋放;緩存方式,棧使用的是一級緩存,堆則是存放在二級緩存;堆棧數據結構區(qū)別;管理方式不同;生長方式不同;空間大小不同;內存速率不同;存儲內容不同;分配方式不同。
1、堆??臻g分配區(qū)別
棧(操作系統(tǒng)):由操作系統(tǒng)(編譯器)自動分配釋放 ,存放函數的參數值,局部變量的值等。其操作方式類似于數據結構中的棧。
堆(操作系統(tǒng)): 一般由程序員分配釋放, 若程序員不釋放,程序結束時可能由OS回收,分配方式倒是類似于鏈表。
2、堆棧緩存方式區(qū)別
棧使用的是一級緩存, 它們通常都是被調用時處于存儲空間中,調用完畢立即釋放。
堆則是存放在二級緩存中,生命周期由虛擬機的垃圾回收算法來決定(并不是一旦成為孤兒對象就能被回收)。所以調用這些對象的速度要相對來得低一些。
3、堆棧數據結構區(qū)別
堆(數據結構):堆可以被看成是一棵樹,如:堆排序。
棧(數據結構):一種先進后出的數據結構。
4.管理方式不同
堆是由程序員通過 調用系統(tǒng)庫函數來管理內存,所以管理不力 就會出現常說的內存泄漏
棧是由計算機系統(tǒng)分配內存 而且系統(tǒng)有專門的寄存器存儲棧指針。
5.生長方式不同
堆是向高地址擴展 也就是常說的向上生長。是不連續(xù)的內存區(qū)域。
棧是向低地址擴展 也就是常說的向下生長。 是連續(xù)的內存區(qū)域。
6.空間大小不同
堆的大小 可以高達 4G 在32位Linux里系統(tǒng)有效的虛擬內存也有3.2G
棧的大小 一般是 1M ~10M 不等(和堆相差很多)。
7.內存速率不同
棧的內存速率較快。前面說了 棧是系統(tǒng)分配內存 ,而且有這FILO的出棧順序 所以棧的內存速率快些。
堆 因為是程序員分配內存 ,而且是由C/C++函數庫提供的。而且機制比較復雜,為了找打到一塊合適大小的內存區(qū)域 會挨個遍歷。所以耗時也就比較多些。
8.存儲內容不同
棧在函數調用時,首先壓入主調函數中下條指令(函數調用語句的下條可執(zhí)行語句)的地址,然后是函數實參,然后是被調函數的局部變量。本次調用結束后,局部變量先出棧,然后是參數,最后棧頂指針指向最開始存的指令地址,程序由該點繼續(xù)運行下條可執(zhí)行語句。
堆通常在頭部用一個字節(jié)存放其大小,堆用于存儲生存期與函數調用無關的數據,具體內容由程序員安排。
(其實我自己的理解是棧有自己的出棧方式FILO 所以局部調用結束后就直接出棧了,然后進行其他沒出棧的操作處理。而堆是先存需要的內存大小,然后后面的就交給創(chuàng)建者自己處理了)
9.分配方式不同
??伸o態(tài)分配或動態(tài)分配。靜態(tài)分配由編譯器完成,如局部變量的分配。動態(tài)分配由alloca函數在棧上申請空間,用完后自動釋放。
堆只能動態(tài)分配且手工釋放。(堆就好比OC語言里的MRC,而OC里的ARC就是蘋果幫我們處理的MRC)
1.3 堆與棧區(qū)別
堆與棧實際上是操作系統(tǒng)對進程占用的內存空間的兩種管理方式,主要有如下幾種區(qū)別:
(1)管理方式不同。
棧由操作系統(tǒng)自動分配釋放,無需我們手動控制;堆的申請和釋放工作由程序員控制,容易產生內存泄漏;
(2)空間大小不同。
每個進程擁有的棧大小要遠遠小于堆大小。理論上,進程可申請的堆大小為虛擬內存大小,進程棧的大小 64bits 的 Windows 默認 1MB,64bits 的 Linux 默認 10MB;
(3)生長方向不同。
堆的生長方向向上,內存地址由低到高;棧的生長方向向下,內存地址由高到低。
(4)分配方式不同。
堆都是動態(tài)分配的,沒有靜態(tài)分配的堆。棧有 2 種分配方式:靜態(tài)分配和動態(tài)分配。靜態(tài)分配是由操作系統(tǒng)完成的,比如局部變量的分配。動態(tài)分配由alloca()函數分配,但是棧的動態(tài)分配和堆是不同的,它的動態(tài)分配是由操作系統(tǒng)進行釋放,無需我們手工實現。
(5)分配效率不同。
棧由操作系統(tǒng)自動分配,會在硬件層級對棧提供支持:分配專門的寄存器存放棧的地址,壓棧出棧都有專門的指令執(zhí)行,這就決定了棧的效率比較高。堆則是由C/C++提供的庫函數或運算符來完成申請與管理,實現機制較為復雜,頻繁的內存申請容易產生內存碎片。顯然,堆的效率比棧要低得多。
(6)存放內容不同。
棧存放的內容,函數返回地址、相關參數、局部變量和寄存器內容等。當主函數調用另外一個函數的時候,要對當前函數執(zhí)行斷點進行保存,需要使用棧來實現,首先入棧的是主函數下一條語句的地址,即擴展指針寄存器的內容(EIP),然后是當前棧幀的底部地址,即擴展基址指針寄存器內容(EBP),再然后是被調函數的實參等,一般情況下是按照從右向左的順序入棧,之后是被調函數的局部變量,注意靜態(tài)變量是存放在數據段或者 BSS 段,是不入棧的。出棧的順序正好相反,最終棧頂指向主函數下一條語句的地址,主程序又從該地址開始執(zhí)行。堆,一般情況堆頂使用一個字節(jié)的空間來存放堆的大小,而堆中具體存放內容是由程序員來填充的。
從以上可以看到,堆和棧相比,由于大量 malloc()/free() 或 new/delete 的使用,容易造成大量的內存碎片,并且可能引發(fā)用戶態(tài)和核心態(tài)的切換,效率較低。棧相比于堆,在程序中應用較為廣泛,最常見的是函數的調用過程由棧來實現,函數返回地址、EBP、實參和局部變量都采用棧的方式存放。雖然棧有眾多的好處,但是由于和堆相比不是那么靈活,有時候分配大量的內存空間,主要還是用堆。
無論是堆還是棧,在內存使用時都要防止非法越界,越界導致的非法內存訪問可能會摧毀程序的堆、棧數據,輕則導致程序運行處于不確定狀態(tài),獲取不到預期結果,重則導致程序異常崩潰,這些都是我們編程時與內存打交道時應該注意的問題。
2.數據結構中的堆與棧
數據結構中,堆與棧是兩個常見的數據結構,理解二者的定義、用法與區(qū)別,能夠利用堆與棧解決很多實際問題。
2.1 棧簡介
棧是一種運算受限的線性表,其限制是指只僅允許在表的一端進行插入和刪除操作,這一端被稱為棧頂(Top),相對地,把另一端稱為棧底(Bottom)。把新元素放到棧頂元素的上面,使之成為新的棧頂元素稱作進棧、入?;驂簵?Push);把棧頂元素刪除,使其相鄰的元素成為新的棧頂元素稱作出?;蛲藯?Pop)。這種受限的運算使棧擁有“先進后出”的特性(First In Last Out),簡稱 FILO。
棧分順序棧和鏈式棧兩種。棧是一種線性結構,所以可以使用數組或鏈表(單向鏈表、雙向鏈表或循環(huán)鏈表)作為底層數據結構。使用數組實現的棧叫做順序棧,使用鏈表實現的棧叫做鏈式棧,二者的區(qū)別是順序棧中的元素地址連續(xù),鏈式棧中的元素地址不連續(xù)。