堆棧和隊列

什麼是堆？什麼是棧？什麼是隊列？

一、什麼是堆？

堆通常是一個可以被看做一棵樹的數組對象。堆總是滿足下列性質：

·堆中某個節點的值總是不大于或不小于其父節點的值；

·堆總是一棵完全二叉樹。

①将根節點最大的堆叫做最大堆或大根堆，根節點最小的堆叫做最小堆或小根堆。常見的堆有二叉堆、斐波那契堆等。

②堆是在程式運作時，而不是在程式編譯時，申請某個大小的記憶體空間。即動态配置設定記憶體，對其通路和對一般記憶體的通路沒有差別。

③堆是應用程式在運作的時候請求作業系統配置設定給自己記憶體，一般是申請/給予的過程。

④堆是指程式運作時申請的動态記憶體，而棧隻是指一種使用堆的方法(即先進後出)。

二、什麼是棧？（stack）

①棧（stack）又名堆棧，它是一種運算受限的線性表。其限制是僅允許在表的一端進行插入和删除運算。這一端被稱為棧頂，相對地，把另一端稱為棧底。

②棧就是一個桶，後放進去的先拿出來，它下面本來有的東西要等它出來之後才能出來（先進後出）

三、什麼是堆棧？

注意：其實堆棧本身就是棧，隻是換了個抽象的名字。

堆棧的特性： 最後一個放入堆棧中的物體總是被最先拿出來， 這個特性通常稱為後進先出(LIFO)隊列。 堆棧中定義了一些操作。 兩個最重要的是PUSH和POP。 PUSH操作在堆棧的頂部加入一 個元素。POP操作相反， 在堆棧頂部移去一個元素， 并将堆棧的大小減一。

四、什麼是隊列？

①隊列是一種特殊的線性表，特殊之處在于它隻允許在表的前端（front）進行删除操作，而在表的後端（rear）進行插入操作，和棧一樣，隊列是一種操作受限制的線性表。進行插入操作的端稱為隊尾，進行删除操作的端稱為隊頭。

②隊列中沒有元素時，稱為空隊列。

③建立順序隊列結構必須為其靜态配置設定或動态申請一片連續的存儲空間，并設定兩個指針進行管理。一個是隊頭指針front，它指向隊頭元素；另一個是隊尾指針rear，它指向下一個入隊元素的存儲位置。

④隊列采用的FIFO(first in first out)，新元素（等待進入隊列的元素）總是被插入到連結清單的尾部，而讀取的時候總是從連結清單的頭部開始讀取。每次讀取一個元素，釋放一個元素。所謂的動态建立，動态釋放。因而也不存在溢出等問題。由于連結清單由結構體間接而成，周遊也友善。（先進先出）