什麼是“堆”,"棧","堆疊","佇列",它們的區別

原創：

GuoXY

如果你學過資料結構，就一定會遇到“堆”，“棧”，“堆疊”，“佇列”，而最關鍵的是這些到底是什麼意思？最關鍵的是即使你去面試，這些都還會問到，所以如果你不懂對你是損失很大的。

堆疊都是一種資料項按序排列的資料結構，只能在一端(稱為棧頂(top))對資料項進行插入和刪除。

要點：堆：順序隨意 棧：後進先出(Last-In/First-Out)

#FormatImgID_1#

堆

堆：什麼是堆？又該怎麼理解呢？

①堆通常是一個可以被看做一棵樹的陣列物件。堆總是滿足下列性質：

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

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

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

②堆是在程式執行時，而不是在程式編譯時，申請某個大小的記憶體空間。即動態分配記憶體，對其訪問和對一般記憶體的訪問沒有區別。

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

④堆是指程式執行時申請的動態記憶體，而棧只是指一種使用堆的方法（即先進後出）。

棧

棧：什麼是棧？又該怎麼理解呢？

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

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

③棧（Stack）是作業系統在建立某個程序時或者執行緒（在支援多執行緒的作業系統中是執行緒）為這個執行緒建立的儲存區域，該區域具有FIFO的特性，在編譯的時候可以指定需要的Stack的大小。

堆疊

堆疊：什麼是堆疊？又該怎麼理解呢？

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

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

總結：

堆、棧區別總結：

1。堆疊空間分配

①棧（作業系統）：由作業系統自動分配釋放 ，存放函式的引數值，區域性變數的值等。其操作方式類似於資料結構中的棧。

②堆（作業系統）： 一般由程式設計師分配釋放， 若程式設計師不釋放，程式結束時可能由OS回收，分配方式倒是類似於連結串列。

2。堆疊快取方式

①棧使用的是一級快取， 他們通常都是被呼叫時處於儲存空間中，呼叫完畢立即釋放。

②堆則是存放在二級快取中，生命週期由虛擬機器的垃圾回收演算法來決定（並不是一旦成為孤兒物件就能被回收）。所以呼叫這些物件的速度要相對來得低一些。

3。堆疊資料結構區別

①堆（資料結構）：堆可以被看成是一棵樹，如：堆排序。

②棧（資料結構）：一種先進後出的資料結構。

佇列：

佇列：什麼是佇列？又該怎麼理解呢？

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

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

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

④佇列採用的FIFO（first in first out），新元素（等待進入佇列的元素）總是被插入到連結串列的尾部，而讀取的時候總是從連結串列的頭部開始讀取。每次讀取一個元素，釋放一個元素。所謂的動態建立，動態釋放。因而也不存在溢位等問題。由於連結串列由結構體間接而成，遍歷也方便。（先進先出）

區別:

堆、棧、佇列之間的區別是？

①堆是在程式執行時，而不是在程式編譯時，申請某個大小的記憶體空間。即動態分配記憶體，對其訪問和對一般記憶體的訪問沒有區別。

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

③佇列只能在隊頭做刪除操作，在隊尾做插入操作。而棧只能在棧頂做插入和刪除操作。（先進先出）