數(shù)據(jù)結構
棧就像裝數(shù)據(jù)的桶或箱子它是一種具有后進先出性質(zhì)的數(shù)據(jù)結構，也就是說后存放的先取，先存放的后取。
這就如同我們要取出放在箱子里面底下的東西（放入的比較早的物體），我們首先要移開壓在它上面的物體（放入的比較晚的物體）。
使用數(shù)組的形式來實現(xiàn)棧，這種棧也稱為靜態(tài)棧；使用鏈表的形式來實現(xiàn)棧，這種棧也稱為動態(tài)棧。
堆像一棵倒過來的樹 ，堆是一種經(jīng)過排序的樹形數(shù)據(jù)結構，每個結點都有一個值。
通常我們所說的堆的數(shù)據(jù)結構，是指二叉堆。堆是一種特殊的完全二叉樹。
堆的特點是根結點的值最?。ɑ蜃畲螅?，且根結點的兩個子樹也是一個堆。由于堆的這個特性，常用來實現(xiàn)優(yōu)先隊列，堆的存取是隨意，無序的。這就如同我們在圖書館的書架上取書，雖然書的擺放是有順序的，但是我們想取任意一本時不必像棧一樣，先取出前面所有的書，可以直接取出想要的書。
堆?？臻g分配
棧：由操作系統(tǒng)自動分配釋放 ，存放函數(shù)的參數(shù)值，局部變量的值等。其操作方式類似于數(shù)據(jù)結構中的棧先進后出。
堆： 一般由程序員分配釋放， 若程序員不釋放，程序結束時可能由系統(tǒng)回收，分配方式倒是類似于鏈表。
可執(zhí)行程序包括BSS段、data段、text段（也稱文本段）。
BSS（Block Started by Symbol）通常是指用來存放程序中未初始化的全局變量和靜態(tài)變量的一塊內(nèi)存區(qū)域。特點是:可讀寫的，在程序執(zhí)行之前BSS段會自動清0。所以，未初始的全局變量在程序執(zhí)行之前已經(jīng)成0了。
注意和data段的區(qū)別，BSS存放的是未初始化的全局變量和靜態(tài)變量，data數(shù)據(jù)段存放的是初始化后的全局變量和靜態(tài)變量。data段的數(shù)據(jù)會加載進入可執(zhí)行文件中，bss段數(shù)據(jù)不會對可執(zhí)行文件的大小有影響，但是會有一些占位符操作，需要知道運行時bss數(shù)據(jù)需要的內(nèi)存大小。
文字常量區(qū) ： 常量字符串"abcd" 就是放在這里的，一般存在rodata段，處于data段和text段中間的一個區(qū)域里。程序結束后由系統(tǒng)釋放
程序代碼區(qū)(text) : 存放程序的二進制代碼。
堆&棧的區(qū)別
1：堆棧緩存方式
棧使用的是一級緩存， 通常被調(diào)用時處于運行內(nèi)存，調(diào)用完畢立即釋放。
堆則是存放在二級緩存中，生命周期由系統(tǒng)來決定（引用計數(shù)為0 就會觸發(fā)回收）。所以調(diào)用這些對象的速度要相對來得低一些。
2：申請方式和回收方式
棧內(nèi)存是由編譯器自動完成的，如局部變量的分配（即在一個函數(shù)中聲明一個 int 類型的變量i時，編譯器就會自動開辟一塊內(nèi)存以存放變量 i）。與此同時，其生存周期也只在函數(shù)的運行過程中，在運行后就釋放，并不可以再次訪問。
堆內(nèi)存是由程序員手動申請與釋放的，程序在運行的時候由程序員使用內(nèi)存分配函數(shù)（如 malloc 函數(shù)）來申請任意多少的內(nèi)存，使用完再由程序員自己負責使用內(nèi)存釋放函數(shù)（如 free 函數(shù)）釋放內(nèi)存
3：申請后效率
棧：只要棧的剩余空間大于所申請空間，系統(tǒng)將為程序提供內(nèi)存，否則將報異常提示棧溢出。棧內(nèi)存分配運算內(nèi)置于處理器的（指令集）中，系統(tǒng)自動分配速度更快。棧中的空閑內(nèi)存都是連續(xù)的，因此不需要維護空閑內(nèi)存塊。只是一個簡單的指向當前棧頂（棧的高地址）的指針sp。
堆：操作系統(tǒng)有一個記錄空閑內(nèi)存地址的鏈表，當系統(tǒng)收到程序的內(nèi)存分配申請時，會遍歷該鏈表，尋找第一個空間大于所申請空間的堆結點，然后將該結點從空閑結點鏈表中刪除，并將該結點的空間分配給程序，大多數(shù)系統(tǒng)，會在這塊內(nèi)存空間塊的首地址處記錄本次分配的大小，這樣，代碼中的 delete語句才能正確的釋放本內(nèi)存空間。另外，由于找到的堆結點的大小不一定正好等于申請的大小，系統(tǒng)會自動的將多余的那部分重新放入空閑鏈表中。由于頻繁分配和釋放（malloc / free）不同大小的堆空間勢必會造成內(nèi)存空間的不連續(xù)，從而造成大量碎片，導致程序效率降低。
5：申請大小的限制
棧：棧是向低地址擴展的數(shù)據(jù)結構，其地址的增長方向是向下進行的，向內(nèi)存地址減小的方向增長。是一塊連續(xù)的內(nèi)存的區(qū)域。這句話的意思是棧頂?shù)牡刂泛蜅５淖畲笕萘渴窍到y(tǒng)預先規(guī)定好的，是一個編譯時就確定的常數(shù)。如果申請的空間超過棧的剩余空間時，將提示overflow。能從棧獲得的空間有限。
堆：堆是向高地址擴展的數(shù)據(jù)結構，是不連續(xù)的內(nèi)存區(qū)域。是用鏈表來存儲空閑內(nèi)存地址的，鏈表的遍歷方向是由低地址向高地址進行的。堆的大小受限于計算機系統(tǒng)中有效的虛擬內(nèi)存，堆獲得的空間比較靈活，也比較大。
6：堆和棧中的存儲內(nèi)容
棧： 在函數(shù)調(diào)用時，第一個進棧的是主函數(shù)中函數(shù)調(diào)用后的下一條指令（函數(shù)調(diào)用語句的下一條可執(zhí)行語句）的地址（返回地址），然后是函數(shù)的各個參數(shù)，然后是函數(shù)中的局部變量。注意靜態(tài)變量是不入棧的。
當本次函數(shù)調(diào)用結束后，局部變量先出棧，然后是參數(shù)，最后棧頂指針指向最開始存的返回地址，也就是主函數(shù)中的下一條指令，程序由該點返回到主函數(shù)繼續(xù)往下執(zhí)行。
堆：一般是在堆的頭部用一個字節(jié)存放堆的大小。
?C 語言中，內(nèi)存分配方式有三種形式：
從靜態(tài)存儲區(qū)域分配：它是由編譯器自動分配和釋放的，程序編譯的時候就已經(jīng)分配好，這塊內(nèi)存在程序的整個運行期間都存在，直到整個程序運行結束時才被釋放，如全局變量與 static 變量。
在棧上分配：它同樣也是由編譯器自動分配和釋放的，即在執(zhí)行函數(shù)時，函數(shù)內(nèi)局部變量的存儲單元都可以在棧上創(chuàng)建，函數(shù)執(zhí)行結束時這些存儲單元將被自動釋放。棧有兩種分配方式：靜態(tài)分配和動態(tài)分配。
靜態(tài)分配是由編譯器自動完成的，如局部變量的分配（即在一個函數(shù)中聲明一個 int 類型的變量i時，編譯器就會自動開辟一塊內(nèi)存以存放變量 i）。與此同時，其生存周期也只在函數(shù)的運行過程中，在運行后就釋放，并不可以再次訪問。
動態(tài)分配由 alloca 函數(shù)進行分配，由編譯器進行釋放，無需任何手工實現(xiàn)。
堆上分配：也稱動態(tài)內(nèi)存分配，它是由程序員手動完成申請和釋放的。即程序在運行的時候由程序員使用內(nèi)存分配函數(shù)（如 malloc 函數(shù)）來申請任意多少的內(nèi)存，使用完之后再由程序員自己負責使用內(nèi)存釋放函數(shù)（如 free 函數(shù)）來釋放內(nèi)存。也就是說，動態(tài)內(nèi)存的整個生存期是由程序員自己決定的，使用非常靈活。需要注意的是，如果在堆上分配了內(nèi)存空間，就必須及時釋放它，否則將會導致運行的程序出現(xiàn)內(nèi)存泄漏等錯誤。
?C 語言中各類型變量的存儲位置和作用域。
全局變量：從靜態(tài)存儲區(qū)域分配，其作用域是全局作用域，也就是整個程序的生命周期內(nèi)都可以使用。與此同時，如果程序是由多個源文件構成的，那么全局變量只要在一個文件中定義，就可以在其他所有的文件中使用，但必須在其他文件中通過使用extern關鍵字來聲明該全局變量。
全局靜態(tài)變量：從靜態(tài)存儲區(qū)域分配，其生命周期也是與整個程序同在的，從程序開始到結束一直起作用。但是與全局變量不同的是，全局靜態(tài)變量作用域只在定義它的一個源文件內(nèi)，其他源文件不能使用。
局部變量: 從棧上分配，其作用域只是在局部函數(shù)內(nèi)，在定義該變量的函數(shù)內(nèi)，只要出了該函數(shù)，該局部變量就不再起作用，該變量的生命周期也只是和該函數(shù)同在。
局部靜態(tài)變量: 從靜態(tài)存儲區(qū)域分配，其在第一次初始化后就一直存在直到程序結束，該變量的特點是其作用域只在定義它的函數(shù)內(nèi)可見，出了該函數(shù)就不可見了,只是延長了變量的生命周期，作用域不變。
相關知識延伸：
在多線程環(huán)境下每一個線程都可以有他自己完全的獨立的棧，但是他們共享堆。并行存取被堆控制而不是棧。
堆的管理依賴于運行時環(huán)境，C 使用 malloc ，C++ 使用 new ，但是很多語言有垃圾回收機制。
棧是更低層次的特性與處理器架構緊密的結合到一起。當堆不夠時可以擴展空間，這不難做到，因為可以有庫函數(shù)可以調(diào)用。但是，擴展棧通常來說是不可能的，因為在棧溢出的時候，執(zhí)行線程就被操作系統(tǒng)關閉了，這已經(jīng)太晚了。
堆包含一個鏈表來維護已用和空閑的內(nèi)存塊。在堆上分配（用 new 或者 malloc）內(nèi)存是從空閑的內(nèi)存塊中找到滿足要求的內(nèi)存塊。這個操作會更新堆中的塊鏈表。
堆碎片 ：?申請和釋放許多小的內(nèi)存塊可能會產(chǎn)生：在已用塊之間存在很多小的空閑塊。進而申請大塊內(nèi)存失敗，雖然空閑塊的總和足夠，但是空閑的小塊是零散的，不能滿足申請的大小。當旁邊有空閑塊的已用塊被釋放時，新的空閑塊可能會與相鄰的空閑塊合并為一個大的空閑塊，這樣可以有效的減少“堆碎片”的產(chǎn)生。?
CPU 用 push 指令來將數(shù)據(jù)壓棧，用 pop 指令來彈棧。當用 push 壓棧時，sp 值減少（向低地址擴展）。當用 pop 彈棧時，sp 值增大。
當函數(shù)被調(diào)用時，CPU使用特定的指令把當前的 IP （“instruction pointer”，是一個寄存器，用來記錄 CPU 指令的位置）壓棧。CPU 接下來將調(diào)用函數(shù)地址賦給 IP ，進行調(diào)用。當函數(shù)返回時，舊的 IP 被彈棧，CPU 繼續(xù)往下執(zhí)行。當進入函數(shù)時，棧中sp指針 向下擴展（向低地址擴展），擴展到確保為函數(shù)的局部變量留足夠大小的空間。如果函數(shù)中有一個 32-bit 的局部變量會在棧中留夠四字節(jié)的空間。當函數(shù)返回時，sp 通過返回原來的位置來釋放空間。
棧是為執(zhí)行線程留出的內(nèi)存空間。棧受到內(nèi)存塊的限制，不斷的函數(shù)嵌套或者為局部變量分配太多的空間，可能會導致棧溢出。當棧中的內(nèi)存區(qū)域都已經(jīng)被用完之后繼續(xù)向下寫（低地址），會觸發(fā)一個 CPU 異常。棧溢出錯誤?？梢园堰@個占用太多內(nèi)存的局部變量用static 關鍵字修飾這樣局部變量變成靜態(tài)局部變量，存儲方式從棧上改到全局變量區(qū)數(shù)據(jù)段上減少對棧內(nèi)存的占用。
內(nèi)存通常由操作系統(tǒng)分配，通過應用程序調(diào)用 API 接口去實現(xiàn)分配。在管理動態(tài)分配內(nèi)存上會有一些額外的開銷，不過這由操作系統(tǒng)來處理。計算機程序通常有一個棧叫做調(diào)用棧，用來存儲當前函數(shù)調(diào)用相關的信息（比如：主調(diào)函數(shù)的地址，局部變量），因為函數(shù)調(diào)用之后需要返回給主調(diào)函數(shù)。
堆是在內(nèi)存中動態(tài)和隨機分配的，是無序的。
堆（heap）是為動態(tài)分配預留的內(nèi)存空間。從堆上分配和釋放內(nèi)存沒有固定模式；你可以在任何時候分配和釋放它。這樣使得跟蹤哪部分堆已經(jīng)被分配和被釋放變的異常復雜；
?1. 當線程創(chuàng)建的時候，操作系統(tǒng)（OS）為每一個系統(tǒng)級（system-level）的線程分配棧。通常情況下，操作系統(tǒng)通過調(diào)用語言的運行時（runtime）去為應用程序分配堆。?
2. 棧附屬于線程，因此當線程結束時棧被回收。堆通常通過運行時在應用程序啟動時被分配，當應用程序（進程）退出時被回收。
?3. 當線程被創(chuàng)建的時候，設置棧的大小。在應用程序啟動的時候，設置堆的大小，但是堆可以在需要的時候擴展（分配器向操作系統(tǒng)申請更多的內(nèi)存）。?
4. 棧比堆要快，在棧上的每個字節(jié)頻繁的被復用也就意味著它可能映射到處理器緩存中，所以很快（局部性原理）。
1.對棧而言，數(shù)據(jù)是有序的，先進后出，后進先出，不能越位。
2.對堆而言，數(shù)據(jù)是隨機無序的?？梢匀魏雾樞虿迦牒蛣h除。
參考地址：
