对堆栈的认识
什么是堆和棧，它們在哪兒？
問題描述
編程語言書籍中經(jīng)常解釋值類型被創(chuàng)建在棧上，引用類型被創(chuàng)建在堆上，但是并沒有本質(zhì)上解釋這堆和棧是什么。我僅有高級語言編程經(jīng)驗(yàn)，沒有看過對此更清晰的解釋。我的意思是我理解什么是棧，但是它們到底是什么，在哪兒呢（站在實(shí)際的計算機(jī)物理內(nèi)存的角度上看）？
1、在通常情況下由操作系統(tǒng)（OS）和語言的運(yùn)行時（runtime）控制嗎？
2、它們的作用范圍是什么？
3、它們的大小由什么決定？
4、哪個更快？
答案一
棧是為執(zhí)行線程留出的內(nèi)存空間。當(dāng)函數(shù)被調(diào)用的時候，棧頂為局部變量和一些 bookkeeping 數(shù)據(jù)預(yù)留塊。當(dāng)函數(shù)執(zhí)行完畢，塊就沒有用了，可能在下次的函數(shù)調(diào)用的時候再被使用。棧通常用后進(jìn)先出（LIFO）的方式預(yù)留空間；因此最近的保留塊（reserved block）通常最先被釋放。這么做可以使跟蹤堆棧變的簡單；從棧中釋放塊（free block）只不過是指針的偏移而已。
堆（heap）是為動態(tài)分配預(yù)留的內(nèi)存空間。和棧不一樣，從堆上分配和重新分配塊沒有固定模式；你可以在任何時候分配和釋放它。這樣使得跟蹤哪部分堆已經(jīng)被分配和被釋放變的異常復(fù)雜；有許多定制的堆分配策略用來為不同的使用模式下調(diào)整堆的性能。
每一個線程都有一個棧，但是每一個應(yīng)用程序通常都只有一個堆（盡管為不同類型分配內(nèi)存使用多個堆的情況也是有的）。
直接回答你的問題：1.當(dāng)線程創(chuàng)建的時候，操作系統(tǒng)（OS）為每一個系統(tǒng)級（system-level）的線程分配棧。通常情況下，操作系統(tǒng)通過調(diào)用語言的運(yùn)行時（runtime）去為應(yīng)用程序分配堆。2.棧附屬于線程，因此當(dāng)線程結(jié)束時棧被回收。堆通常通過運(yùn)行時在應(yīng)用程序啟動時被分配，當(dāng)應(yīng)用程序（進(jìn)程）退出時被回收。3.當(dāng)線程被創(chuàng)建的時候，設(shè)置棧的大小。在應(yīng)用程序啟動的時候，設(shè)置堆的大小，但是可以在需要的時候擴(kuò)展（分配器向操作系統(tǒng)申請更多的內(nèi)存）。4.棧比堆要快，因?yàn)樗嫒∧Ｊ绞顾梢暂p松的分配和重新分配內(nèi)存（指針/整型只是進(jìn)行簡單的遞增或者遞減運(yùn)算），然而堆在分配和釋放的時候有更多的復(fù)雜的 bookkeeping 參與。另外，在棧上的每個字節(jié)頻繁的被復(fù)用也就意味著它可能映射到處理器緩存中，所以很快（譯者注：局部性原理）。
答案二
Stack:
1、和堆一樣存儲在計算機(jī) RAM 中。
2、在棧上創(chuàng)建變量的時候會擴(kuò)展，并且會自動回收。
3、相比堆而言在棧上分配要快的多。
4、用數(shù)據(jù)結(jié)構(gòu)中的棧實(shí)現(xiàn)。
5、存儲局部數(shù)據(jù)，返回地址，用做參數(shù)傳遞。
6、當(dāng)用棧過多時可導(dǎo)致棧溢出（無窮次（大量的）的遞歸調(diào)用，或者大量的內(nèi)存分配）。
7、在棧上的數(shù)據(jù)可以直接訪問（不是非要使用指針訪問）。
8、如果你在編譯之前精確的知道你需要分配數(shù)據(jù)的大小并且不是太大的時候，可以使用棧。
9、當(dāng)你程序啟動時決定棧的容量上限。
Heap：
1、和棧一樣存儲在計算機(jī)RAM。
2、在堆上的變量必須要手動釋放，不存在作用域的問題。數(shù)據(jù)可用 delete, delete[] 或者 free 來釋放。
3、相比在棧上分配內(nèi)存要慢。
4、通過程序按需分配。
5、大量的分配和釋放可造成內(nèi)存碎片。
6、在 C++ 中，在堆上創(chuàng)建數(shù)的據(jù)使用指針訪問，用 new 或者 malloc 分配內(nèi)存。
7、如果申請的緩沖區(qū)過大的話，可能申請失敗。
8、在運(yùn)行期間你不知道會需要多大的數(shù)據(jù)或者你需要分配大量的內(nèi)存的時候，建議你使用堆。
9、可能造成內(nèi)存泄露。
舉例：
int foo() { char *pBuffer; //<--nothing allocated yet (excluding the pointer itself, which is allocated here on the stack). bool b = true; // Allocated on the stack. if(b) { //Create 500 bytes on the stack char buffer[500]; //Create 500 bytes on the heap pBuffer = new char[500]; }//<-- buffer is deallocated here, pBuffer is not }//<--- oops there's a memory leak, I should have called delete[] pBuffer;答案三
堆和棧是兩種內(nèi)存分配的兩個統(tǒng)稱。可能有很多種不同的實(shí)現(xiàn)方式，但是實(shí)現(xiàn)要符合幾個基本的概念:
1、對棧而言，棧中的新加數(shù)據(jù)項(xiàng)放在其他數(shù)據(jù)的頂部，移除時你也只能移除最頂部的數(shù)據(jù)（不能越位獲取）。
2.對堆而言，數(shù)據(jù)項(xiàng)位置沒有固定的順序。你可以以任何順序插入和刪除，因?yàn)樗麄儧]有“頂部”數(shù)據(jù)這一概念。
上面上個圖片很好的描述了堆和棧分配內(nèi)存的方式。
在通常情況下由操作系統(tǒng)（OS）和語言的運(yùn)行時（runtime）控制嗎？
如前所述，堆和棧是一個統(tǒng)稱，可以有很多的實(shí)現(xiàn)方式。計算機(jī)程序通常有一個棧叫做調(diào)用棧，用來存儲當(dāng)前函數(shù)調(diào)用相關(guān)的信息（比如：主調(diào)函數(shù)的地址，局部變量），因?yàn)楹瘮?shù)調(diào)用之后需要返回給主調(diào)函數(shù)。棧通過擴(kuò)展和收縮來承載信息。實(shí)際上，程序不是由運(yùn)行時來控制的，它由編程語言、操作系統(tǒng)甚至是系統(tǒng)架構(gòu)來決定。
堆是在任何內(nèi)存中動態(tài)和隨機(jī)分配的（內(nèi)存的）統(tǒng)稱；也就是無序的。內(nèi)存通常由操作系統(tǒng)分配，通過應(yīng)用程序調(diào)用 API 接口去實(shí)現(xiàn)分配。在管理動態(tài)分配內(nèi)存上會有一些額外的開銷，不過這由操作系統(tǒng)來處理。
它們的作用范圍是什么？
調(diào)用棧是一個低層次的概念，就程序而言，它和“作用范圍”沒什么關(guān)系。如果你反匯編一些代碼，你就會看到指針引用堆棧部分。就高級語言而言，語言有它自己的范圍規(guī)則。一旦函數(shù)返回，函數(shù)中的局部變量會直接直接釋放。你的編程語言就是依據(jù)這個工作的。
在堆中，也很難去定義。作用范圍是由操作系統(tǒng)限定的，但是你的編程語言可能增加它自己的一些規(guī)則，去限定堆在應(yīng)用程序中的范圍。體系架構(gòu)和操作系統(tǒng)是使用虛擬地址的，然后由處理器翻譯到實(shí)際的物理地址中，還有頁面錯誤等等。它們記錄那個頁面屬于那個應(yīng)用程序。不過你不用關(guān)心這些，因?yàn)槟銉H僅在你的編程語言中分配和釋放內(nèi)存，和一些錯誤檢查（出現(xiàn)分配失敗和釋放失敗的原因）。
它們的大小由什么決定？
依舊，依賴于語言，編譯器，操作系統(tǒng)和架構(gòu)。棧通常提前分配好了，因?yàn)闂１仨毷沁B續(xù)的內(nèi)存塊。語言的編譯器或者操作系統(tǒng)決定它的大小。不要在棧上存儲大塊數(shù)據(jù)，這樣可以保證有足夠的空間不會溢出，除非出現(xiàn)了無限遞歸的情況（額，棧溢出了）或者其它不常見了編程決議。
堆是任何可以動態(tài)分配的內(nèi)存的統(tǒng)稱。這要看你怎么看待它了，它的大小是變動的。在現(xiàn)代處理器中和操作系統(tǒng)的工作方式是高度抽象的，因此你在正常情況下不需要擔(dān)心它實(shí)際的大小，除非你必須要使用你還沒有分配的內(nèi)存或者已經(jīng)釋放了的內(nèi)存。
哪個更快一些？
棧更快因?yàn)樗械目臻e內(nèi)存都是連續(xù)的，因此不需要對空閑內(nèi)存塊通過列表來維護(hù)。只是一個簡單的指向當(dāng)前棧頂?shù)闹羔槨＞幾g器通常用一個專門的、快速的寄存器來實(shí)現(xiàn)。更重要的一點(diǎn)事是，隨后的棧上操作通常集中在一個內(nèi)存塊的附近，這樣的話有利于處理器的高速訪問（譯者注：局部性原理）。
答案四
你問題的答案是依賴于實(shí)現(xiàn)的，根據(jù)不同的編譯器和處理器架構(gòu)而不同。下面簡單的解釋一下：
1、棧和堆都是用來從底層操作系統(tǒng)中獲取內(nèi)存的。
2、在多線程環(huán)境下每一個線程都可以有他自己完全的獨(dú)立的棧，但是他們共享堆。并行存取被堆控制而不是棧。
堆:
1、堆包含一個鏈表來維護(hù)已用和空閑的內(nèi)存塊。在堆上新分配（用 new 或者 malloc）內(nèi)存是從空閑的內(nèi)存塊中找到一些滿足要求的合適塊。這個操作會更新堆中的塊鏈表。這些元信息也存儲在堆上，經(jīng)常在每個塊的頭部一個很小區(qū)域。
2、堆的增加新快通常從地地址向高地址擴(kuò)展。因此你可以認(rèn)為堆隨著內(nèi)存分配而不斷的增加大小。如果申請的內(nèi)存大小很小的話，通常從底層操作系統(tǒng)中得到比申請大小要多的內(nèi)存。
3、申請和釋放許多小的塊可能會產(chǎn)生如下狀態(tài)：在已用塊之間存在很多小的空閑塊。進(jìn)而申請大塊內(nèi)存失敗，雖然空閑塊的總和足夠，但是空閑的小塊是零散的，不能滿足申請的大小，。這叫做“堆碎片”。
4、當(dāng)旁邊有空閑塊的已用塊被釋放時，新的空閑塊可能會與相鄰的空閑塊合并為一個大的空閑塊，這樣可以有效的減少“堆碎片”的產(chǎn)生。
棧:
1、棧經(jīng)常與 sp 寄存器（譯者注：”stack pointer”，了解匯編的朋友應(yīng)該都知道）一起工作，最初 sp 指向棧頂（棧的高地址）。
2、CPU 用 push 指令來將數(shù)據(jù)壓棧，用 pop 指令來彈棧。當(dāng)用 push 壓棧時，sp 值減少（向低地址擴(kuò)展）。當(dāng)用 pop 彈棧時，sp 值增大。存儲和獲取數(shù)據(jù)都是 CPU 寄存器的值。
3、當(dāng)函數(shù)被調(diào)用時，CPU使用特定的指令把當(dāng)前的 IP （譯者注：“instruction pointer”，是一個寄存器，用來記錄 CPU 指令的位置）壓棧。即執(zhí)行代碼的地址。CPU 接下來將調(diào)用函數(shù)地址賦給 IP ，進(jìn)行調(diào)用。當(dāng)函數(shù)返回時，舊的 IP 被彈棧，CPU 繼續(xù)去函數(shù)調(diào)用之前的代碼。
4、當(dāng)進(jìn)入函數(shù)時，sp 向下擴(kuò)展，擴(kuò)展到確保為函數(shù)的局部變量留足夠大小的空間。如果函數(shù)中有一個 32-bit 的局部變量會在棧中留夠四字節(jié)的空間。當(dāng)函數(shù)返回時，sp 通過返回原來的位置來釋放空間。
5、如果函數(shù)有參數(shù)的話，在函數(shù)調(diào)用之前，會將參數(shù)壓棧。函數(shù)中的代碼通過 sp 的當(dāng)前位置來定位參數(shù)并訪問它們。
6、函數(shù)嵌套調(diào)用和使用魔法一樣，每一次新調(diào)用的函數(shù)都會分配函數(shù)參數(shù)，返回值地址、局部變量空間、嵌套調(diào)用的活動記錄都要被壓入棧中。函數(shù)返回時，按照正確方式的撤銷。
7、棧要受到內(nèi)存塊的限制，不斷的函數(shù)嵌套/為局部變量分配太多的空間，可能會導(dǎo)致棧溢出。當(dāng)棧中的內(nèi)存區(qū)域都已經(jīng)被使用完之后繼續(xù)向下寫（低地址），會觸發(fā)一個 CPU 異常。這個異常接下會通過語言的運(yùn)行時轉(zhuǎn)成各種類型的棧溢出異常。（譯者注：“不同語言的異常提示不同，因此通過語言運(yùn)行時來轉(zhuǎn)換”我想他表達(dá)的是這個含義）
*函數(shù)的分配可以用堆來代替棧嗎？
不可以的，函數(shù)的活動記錄（即局部或者自動變量）被分配在棧上， 這樣做不但存儲了這些變量，而且可以用來嵌套函數(shù)的追蹤。
堆的管理依賴于運(yùn)行時環(huán)境，C 使用 malloc ，C++ 使用 new ，但是很多語言有垃圾回收機(jī)制。
棧是更低層次的特性與處理器架構(gòu)緊密的結(jié)合到一起。當(dāng)堆不夠時可以擴(kuò)展空間，這不難做到，因?yàn)榭梢杂袔旌瘮?shù)可以調(diào)用。但是，擴(kuò)展棧通常來說是不可能的，因?yàn)樵跅Ｒ绯龅臅r候，執(zhí)行線程就被操作系統(tǒng)關(guān)閉了，這已經(jīng)太晚了。
譯者注
關(guān)于堆棧的這個帖子，對我來說，收獲非常多。我之前看過一些資料，自己寫代碼的時候也常常思考。就這方面，也和祥子（我的大學(xué)舍友，現(xiàn)在北京郵電讀研，技術(shù)牛人）探討過多次了。但是終究是一個一個的知識點(diǎn)，這個帖子看完之后，豁然開朗，把知識點(diǎn)終于連接成了一個網(wǎng)。這種感覺，經(jīng)歷過的一定懂得，期間的興奮不言而喻。
這個帖子跟帖者不少，我選了評分最高的四個。這四個之間也有一些是重復(fù)的觀點(diǎn)。個人鐘愛第四個回答者，我看的時候，瞬間高潮了，有木有？不過需要一些匯編語言、操作系統(tǒng)、計算機(jī)組成原理的的基礎(chǔ)，知道那幾個寄存器是干什么的，要知道計算機(jī)的流水線指令工作機(jī)制，保護(hù)/恢復(fù)現(xiàn)場等概念。三個回復(fù)者都涉及到了操作系統(tǒng)中虛擬內(nèi)存；在比較速度的時候，大家一定要在腦中對“局部性原理”和計算機(jī)高速緩存有一個概念。
如果你把這篇文章看懂了，我相信你收獲的不只是堆和棧，你會理解的更多！
興奮之余，有幾點(diǎn)還是要強(qiáng)調(diào)的，翻譯沒有逐字逐詞翻譯，大部分是通過我個人的知識積累和對回帖者的意圖揣測而來的。請大家不要咬文嚼字，逐個推敲，我們的目的在于技術(shù)交流，不是么？達(dá)到這一目的就夠了。
下面是一些不確定點(diǎn):
1、我沒有聽過 bookkeeping data 這種說法，故沒有翻譯。從上下文理解來看，可以想成是用來寄存器值？函數(shù)參數(shù)？返回地址？如果有了解具體含義的朋友，煩請告知。
2、棧和堆棧是一回事，英文表達(dá)是 stack，堆是 heap。
3、調(diào)用棧的概念，我是第一次聽說，不太熟悉。大家可以去查查資料研究一下。
來自： 獨(dú)酌逸醉
鏈接：http://www.perfect-is-shit.com/what-and-where-are-the-stack-and-heap.html
原文：http://stackoverflow.com/questions/79923/what-and-where-are-the-stack-and-heap
總結(jié)
- 上一篇： 函数声明
- 下一篇： c语言链表贪吃蛇脚本之家,C++控制台实