一、堆
堆是一種經(jīng)過(guò)排序的樹(shù)形數(shù)據(jù)結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)都有一個(gè)值，通常我們所說(shuō)的堆的數(shù)據(jù)結(jié)構(gòu)是指二叉樹(shù)。所以堆在數(shù)據(jù)結(jié)構(gòu)中通常可以被看做是一棵樹(shù)的數(shù)組對(duì)象。而且堆需要滿足一下兩個(gè)性質(zhì)：
（1）堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值；
（2）堆總是一棵完全二叉樹(shù)。
堆分為兩種情況，有最大堆和最小堆。將根節(jié)點(diǎn)最大的堆叫做最大堆或大根堆，根節(jié)點(diǎn)最小的堆叫做最小堆或小根堆。下圖圖一就是一個(gè)最大堆，圖二就是一個(gè)最小堆。在一個(gè)擺放好元素的最小堆中，可以看到，父結(jié)點(diǎn)中的元素一定比子結(jié)點(diǎn)的元素要小，但對(duì)于左右結(jié)點(diǎn)的大小則沒(méi)有規(guī)定誰(shuí)大誰(shuí)小。
堆常用來(lái)實(shí)現(xiàn)優(yōu)先隊(duì)列，堆的存取是隨意的，這就如同我們?cè)趫D書(shū)館的書(shū)架上取書(shū)，雖然書(shū)的擺放是有順序的，但是我們想取任意一本時(shí)不必像棧一樣，先取出前面所有的書(shū)，書(shū)架這種機(jī)制不同于箱子，我們可以直接取出我們想要的書(shū)。
二、棧
棧是限定僅在表尾進(jìn)行插入和刪除操作的線性表。我們把允許插入和刪除的一端稱為棧頂，另一端稱為棧底，不含任何數(shù)據(jù)元素的棧稱為空棧。棧的特殊之處在于它限制了這個(gè)線性表的插入和刪除位置，它始終只在棧頂進(jìn)行。
而且棧是一種具有后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，又稱為后進(jìn)先出的線性表，簡(jiǎn)稱 LIFO（Last In First Out）結(jié)構(gòu)。也就是說(shuō)后存放的先取，先存放的后取，這就類似于我們要在取放在箱子底部的東西（放進(jìn)去比較早的物體），我們首先要移開(kāi)壓在它上面的物體（放進(jìn)去比較晚的物體）。
堆棧中定義了一些操作。兩個(gè)最重要的是PUSH和POP。PUSH操作在堆棧的頂部加入一個(gè)元素。POP操作相反，在堆棧頂部移去一個(gè)元素，并將堆棧的大小減一。
注意：其實(shí)堆棧本身就是棧，只是換了個(gè)抽象的名字。
棧的應(yīng)用——遞歸
在高級(jí)語(yǔ)言中，調(diào)用自己和其它函數(shù)沒(méi)有本質(zhì)的不同。我們把一個(gè)直接用自己或通過(guò)一系列的調(diào)用語(yǔ)句間接地調(diào)用自己的函數(shù)，稱作遞歸函數(shù)。每個(gè)遞歸函數(shù)必須至少有一個(gè)條件，滿足時(shí)遞歸不再執(zhí)行，即不再引用自身而是返回值退出。
遞歸和迭代的區(qū)別是：迭代使用的是循環(huán)結(jié)構(gòu)，遞歸使用的是選擇結(jié)構(gòu)。 遞歸能使程序的結(jié)構(gòu)更清晰、更簡(jiǎn)潔、更容易讓人理解，從而減少讀懂代碼的時(shí)間。但是大量的遞歸調(diào)用會(huì)建立函數(shù)的副本，會(huì)耗費(fèi)大量的時(shí)間和內(nèi)存。迭代則不需要反復(fù)調(diào)用函數(shù)和占用額外的內(nèi)存。因此我們應(yīng)該視不同情況選擇不同的代碼實(shí)現(xiàn)方式。
在前行階段，對(duì)于每一層遞歸，函數(shù)的局部變量、參數(shù)值以及返回地址都被壓入棧中。在退回階段，位于棧頂?shù)木植孔兞?、參?shù)值和返回地址被彈出，用于返回調(diào)用層次中執(zhí)行代碼的其余部分，也就是恢復(fù)了調(diào)用的狀態(tài)。
三、隊(duì)列
隊(duì)列是只允許在一端進(jìn)行插入操作、而在另一端進(jìn)行刪除操作的線性表。允許插入的一端稱為隊(duì)尾，允許刪除的一端稱為隊(duì)頭。它是一種特殊的線性表，特殊之處在于它只允許在表的前端進(jìn)行刪除操作，而在表的后端進(jìn)行插入操作，和棧一樣，隊(duì)列是一種操作受限制的線性表。
而且隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，又稱為先進(jìn)先出的線性表，簡(jiǎn)稱 FIFO（First In First Out）結(jié)構(gòu)。也就是說(shuō)先放的先取，后放的后取，就如同行李過(guò)安檢的時(shí)候，先放進(jìn)去的行李在另一端總是先出來(lái)，后放入的行李會(huì)在最后面出來(lái)。
解決假溢出的辦法就是后面滿了，就再?gòu)念^開(kāi)始，也就是頭尾相接的循環(huán)。我們把隊(duì)列的這種頭尾相接的順序存儲(chǔ)結(jié)構(gòu)稱為循環(huán)隊(duì)列。
以上是數(shù)據(jù)結(jié)構(gòu)中的堆、棧和隊(duì)列，另補(bǔ)充一點(diǎn)：內(nèi)存分配中的堆區(qū)和棧區(qū)
內(nèi)存中的堆和棧第一個(gè)區(qū)別就是申請(qǐng)方式的不同：棧是系統(tǒng)自動(dòng)分配空間的，而堆則是程序員根據(jù)需要自己申請(qǐng)的空間。由于棧上的空間是自動(dòng)分配自動(dòng)回收的，所以棧上的數(shù)據(jù)的生存周期只是在函數(shù)的運(yùn)行過(guò)程中，運(yùn)行后就釋放掉，不可以再訪問(wèn)。而堆上的數(shù)據(jù)只要程序員不釋放空間，就一直可以訪問(wèn)到，不過(guò)缺點(diǎn)是一旦忘記釋放會(huì)造成內(nèi)存泄露。
申請(qǐng)效率的比較：棧由系統(tǒng)自動(dòng)分配，速度較快。但程序員是無(wú)法控制的。堆是由new分配的內(nèi)存，一般速度比較慢，而且容易產(chǎn)生內(nèi)存碎片，不過(guò)用起來(lái)最方便。
申請(qǐng)大小的限制：
棧：在Windows下，棧是向低地址擴(kuò)展的數(shù)據(jù)結(jié)構(gòu)，是一塊連續(xù)的內(nèi)存的區(qū)域。這句話的意思是棧頂?shù)牡刂泛蜅５淖畲笕萘渴窍到y(tǒng)預(yù)先規(guī)定好的，在Windows下，棧的大小是2M（也有的說(shuō)是1M，總之是一個(gè)編譯時(shí)就確定的常數(shù)），如果申請(qǐng)的空間超過(guò)棧的剩余空間時(shí)，將提示overflow。因此，能從棧獲得的空間較小。
堆：堆是向高地址擴(kuò)展的數(shù)據(jù)結(jié)構(gòu)，是不連續(xù)的內(nèi)存區(qū)域。這是由于系統(tǒng)是用鏈表來(lái)存儲(chǔ)空閑內(nèi)存地址的，自然是不連續(xù)的，而鏈表的遍歷方向是由低地址向高地址。堆的大小受限于計(jì)算機(jī)系統(tǒng)中有效的虛擬內(nèi)存。由此可見(jiàn)，堆獲得的空間比較靈活，也比較大。
