堆棧和隊列在數(shù)據(jù)結(jié)構中是最基礎，但同時也是最重要的概念，很多小伙伴對兩者不是很了解，本文就言簡意賅的帶大家了解一下堆棧和隊列。
棧與隊列是兩種重要的特殊線性表，從結(jié)構上講，兩者都是線性表，但從操作上講，兩者支持的基本操作卻只是線性表操作的子集，是操作受限制的線性表。棧與隊列兩者最大的區(qū)別在于，棧元素后進先出(LIFO，Last In First Out)，而隊列元素先進先出(FIFO，F(xiàn)irst In First Out)。此外，針對隊列這一特殊數(shù)據(jù)結(jié)構，有時需考慮隊列元素的優(yōu)先級的關系，即根據(jù)用戶自定義的優(yōu)先級排序，出隊時優(yōu)先彈出優(yōu)先級更高(低)的元素，優(yōu)先隊列能更好地滿足實際問題中的需求，而在優(yōu)先隊列的各種實現(xiàn)中，堆是一種最高效的數(shù)據(jù)結(jié)構。本文分別介紹了順序棧、鏈式棧、鏈式隊列和循環(huán)隊列以及對應與前兩種隊列實現(xiàn)的最大/最小優(yōu)先級隊列，還有兩種堆結(jié)構，最大堆與最小堆的基本結(jié)構，并給出了相應的C++類代碼實現(xiàn)。
棧(Stack)
棧是限定只能在表頭進行插入(入棧)與刪除(出棧)操作的線性表，表頭端稱為棧頂，表尾端稱為棧底。
設有棧 $S=(a_1, a_2,…, a_n)$ ，則一般稱 $a_1$ 為棧底元素，$a_n$為棧頂元素，按 $a_1, a_2,…,a_n$ 的順序依次進棧，則根據(jù)元素入棧的規(guī)定，從棧頂?shù)綏５椎脑匾来螢?$a_n,…,a_2, a_1$，出棧時彈出的第一個元素為棧頂元素，即 $a_n$，也就是說棧是按后進先出的原則進行。故，?？煞Q為后進先出(Last In First Out, LIFO)的線性表。
棧有順序表和鏈表兩種實現(xiàn)方式。
順序棧(Sequence Stack)
在順序?qū)崿F(xiàn)中，利用一組地址連續(xù)的存儲單元即數(shù)組依次存放從棧底到棧頂?shù)臄?shù)據(jù)元素，將數(shù)據(jù)類型為ElemType的數(shù)據(jù)元素存放在數(shù)組中，并用count存儲數(shù)組中存儲的棧的實際元素個數(shù)。每次插入新的棧頂元素，如棧未滿，則操作成功，count值加一，而當刪除棧頂元素時，如棧不空，操作成功，并且count值減一。
隊列是一種先進先出(First In First Out，F(xiàn)IFO)的線性表，只允許在一端進行插入(入隊)操作，而在另一端進行刪除(出隊)操作。
在隊列中，允許入隊操作的一端稱為隊尾，允許出隊操作的一端稱為隊頭。
設有隊列 $q=(a_1, a_2,…,a_n)$，則 $a_1$ 稱為隊頭元素，$a_n$ 稱為隊尾元素，隊列中元素是按 $a_1, a_2,…,a_n$ 的順序入隊，同時也要求按照相同的順序出隊。
隊列也有兩種存儲結(jié)構：順序存儲結(jié)構和鏈式存儲結(jié)構。
一、什么是堆棧?
堆棧是一種線性數(shù)據(jù)結(jié)構，遵循后進先出即LIFO規(guī)則：添加到堆棧的第一個元素是最后一個要刪除的元素，而添加到堆棧的最后一個元素是第一個要刪除的元素。
棧
知識點概述
后進先出(Last In First Out，LIFO)的線性序列，稱為“?！?。棧也是一種線性表，只不過它是操作受限的線性表，只能在一端進出操作。進出的一端稱為棧頂(top)，另一端稱為棧底(base)。?？梢杂庙樞虼鎯Γ部梢杂面準酱鎯?，分別稱為順序棧和鏈棧。
堆棧
堆棧的定義及基本運算
堆棧簡稱為棧，是限定只能在表的一端進行插入和刪除操作的線性表。在表中，允許插入和刪除的一端稱作“棧頂”，另一端稱作“棧底”。通常將元素插入棧頂?shù)牟俜Q作為“入?！?進?；驂簵?，稱刪除棧頂元素的操作為“出?！?表
在堆棧結(jié)構中有兩種操作：
push
pop
1.1 push
push，將元素存儲到堆棧上，如圖所示，將3存到堆棧上。
1.2 pop
pop，從堆棧中移除一個元素，如圖所示，將3從堆棧上移除。
二、什么是隊列?
隊列是一種抽象數(shù)據(jù)類型和線性數(shù)據(jù)結(jié)構，基于FIFO(先進先出)，即先插入的元素將在隊列中最先被訪問。
隊列包含兩種操作：
enqueue
dequeue
2.1 enqueue
enqueue，將數(shù)據(jù)存儲到隊列中，如圖所示，將12存到隊列中。
2.2 dequeue
dequeue，將數(shù)據(jù)從隊列中移除，如圖，將10從隊列中移除。
三、堆棧和隊列的區(qū)別
3.1 工作原則
堆棧：遵循后進先出 (LIFO) 原則，最后插入的元素首先被刪除。
隊列：遵循先進先出 (FIFO) 原則，第一個添加的元素首先從列表中刪除。
3.2 操作
堆棧：
隊列：
3.3 工作原則
堆棧：pop 操作用于從堆棧中刪除元素，而 push 操作用于將元素插入堆棧中。
隊列：dequeue出隊操作從隊列中刪除元素，enqueue入隊操作將元素插入隊列。
3.4 類型
堆棧：沒有任何類型。
隊列：分為三種類型：循環(huán)隊列、優(yōu)先隊列、雙端隊列。
3.5 使用場景
堆棧：用于解決遞歸問題。
隊列：用于解決具有順序處理的問題。
3.6 線性集合
堆棧：垂直。
隊列：水平。
四、堆棧和隊列相似之處
4.1 線性數(shù)據(jù)結(jié)構
堆棧和隊列都是線性數(shù)據(jù)結(jié)構，這意味著元素是按順序存儲的，并且在一次運行中訪問。
4.2 大小靈活
堆棧和隊列的大小都是靈活的，這意味著它們可以根據(jù)運行時的要求進行增長和收縮。
總結(jié)
堆棧和隊列是比較常見的數(shù)據(jù)結(jié)構，本文用精簡的語言解釋了什么是堆棧以及什么是隊列，最后還進行了比較，至于到底使用堆棧還是使用隊列，還是要看場景，具體問題具體分析。
下載文檔
