堆棧和隊(duì)列在數(shù)據(jù)結(jié)構(gòu)中是最基礎(chǔ)，但同時(shí)也是最重要的概念，很多小伙伴對(duì)兩者不是很了解，本文就言簡意賅的帶大家了解一下堆棧和隊(duì)列。

棧與隊(duì)列是兩種重要的特殊線性表，從結(jié)構(gòu)上講，兩者都是線性表，但從操作上講，兩者支持的基本操作卻只是線性表操作的子集，是操作受限制的線性表。棧與隊(duì)列兩者最大的區(qū)別在于，棧元素后進(jìn)先出(LIFO，Last In First Out)，而隊(duì)列元素先進(jìn)先出(FIFO，F(xiàn)irst In First Out)。此外，針對(duì)隊(duì)列這一特殊數(shù)據(jù)結(jié)構(gòu)，有時(shí)需考慮隊(duì)列元素的優(yōu)先級(jí)的關(guān)系，即根據(jù)用戶自定義的優(yōu)先級(jí)排序，出隊(duì)時(shí)優(yōu)先彈出優(yōu)先級(jí)更高(低)的元素，優(yōu)先隊(duì)列能更好地滿足實(shí)際問題中的需求，而在優(yōu)先隊(duì)列的各種實(shí)現(xiàn)中，堆是一種最高效的數(shù)據(jù)結(jié)構(gòu)。本文分別介紹了順序棧、鏈?zhǔn)綏！㈡準(zhǔn)疥?duì)列和循環(huán)隊(duì)列以及對(duì)應(yīng)與前兩種隊(duì)列實(shí)現(xiàn)的最大/最小優(yōu)先級(jí)隊(duì)列，還有兩種堆結(jié)構(gòu)，最大堆與最小堆的基本結(jié)構(gòu)，并給出了相應(yīng)的C++類代碼實(shí)現(xiàn)。

棧(Stack)

棧是限定只能在表頭進(jìn)行插入(入棧)與刪除(出棧)操作的線性表，表頭端稱為棧頂，表尾端稱為棧底。

設(shè)有棧 $S=(a_1, a_2,…, a_n)$ ，則一般稱 $a_1$ 為棧底元素，$a_n$為棧頂元素，按 $a_1, a_2,…,a_n$ 的順序依次進(jìn)棧，則根據(jù)元素入棧的規(guī)定，從棧頂?shù)綏５椎脑匾来螢?$a_n,…,a_2, a_1$，出棧時(shí)彈出的第一個(gè)元素為棧頂元素，即 $a_n$，也就是說棧是按后進(jìn)先出的原則進(jìn)行。故，棧可稱為后進(jìn)先出(Last In First Out, LIFO)的線性表。

棧有順序表和鏈表兩種實(shí)現(xiàn)方式。

順序棧(Sequence Stack)

在順序?qū)崿F(xiàn)中，利用一組地址連續(xù)的存儲(chǔ)單元即數(shù)組依次存放從棧底到棧頂?shù)臄?shù)據(jù)元素，將數(shù)據(jù)類型為ElemType的數(shù)據(jù)元素存放在數(shù)組中，并用count存儲(chǔ)數(shù)組中存儲(chǔ)的棧的實(shí)際元素個(gè)數(shù)。每次插入新的棧頂元素，如棧未滿，則操作成功，count值加一，而當(dāng)刪除棧頂元素時(shí)，如棧不空，操作成功，并且count值減一。

隊(duì)列是一種先進(jìn)先出(First In First Out，F(xiàn)IFO)的線性表，只允許在一端進(jìn)行插入(入隊(duì))操作，而在另一端進(jìn)行刪除(出隊(duì))操作。

在隊(duì)列中，允許入隊(duì)操作的一端稱為隊(duì)尾，允許出隊(duì)操作的一端稱為隊(duì)頭。

設(shè)有隊(duì)列 $q=(a_1, a_2,…,a_n)$，則 $a_1$ 稱為隊(duì)頭元素，$a_n$ 稱為隊(duì)尾元素，隊(duì)列中元素是按 $a_1, a_2,…,a_n$ 的順序入隊(duì)，同時(shí)也要求按照相同的順序出隊(duì)。

隊(duì)列也有兩種存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

一、什么是堆棧?

堆棧是一種線性數(shù)據(jù)結(jié)構(gòu)，遵循后進(jìn)先出即LIFO規(guī)則：添加到堆棧的第一個(gè)元素是最后一個(gè)要?jiǎng)h除的元素，而添加到堆棧的最后一個(gè)元素是第一個(gè)要?jiǎng)h除的元素。

棧

知識(shí)點(diǎn)概述

后進(jìn)先出(Last In First Out，LIFO)的線性序列，稱為“棧”。棧也是一種線性表，只不過它是操作受限的線性表，只能在一端進(jìn)出操作。進(jìn)出的一端稱為棧頂(top)，另一端稱為棧底(base)。?？梢杂庙樞虼鎯?chǔ)，也可以用鏈?zhǔn)酱鎯?chǔ)，分別稱為順序棧和鏈棧。

堆棧

堆棧的定義及基本運(yùn)算

堆棧簡稱為棧，是限定只能在表的一端進(jìn)行插入和刪除操作的線性表。在表中，允許插入和刪除的一端稱作“棧頂”，另一端稱作“棧底”。通常將元素插入棧頂?shù)牟俜Q作為“入?！?進(jìn)?；驂簵?，稱刪除棧頂元素的操作為“出?！?表

在堆棧結(jié)構(gòu)中有兩種操作：

push

pop

1.1 push

push，將元素存儲(chǔ)到堆棧上，如圖所示，將3存到堆棧上。

1.2 pop

pop，從堆棧中移除一個(gè)元素，如圖所示，將3從堆棧上移除。

二、什么是隊(duì)列?

隊(duì)列是一種抽象數(shù)據(jù)類型和線性數(shù)據(jù)結(jié)構(gòu)，基于FIFO(先進(jìn)先出)，即先插入的元素將在隊(duì)列中最先被訪問。

隊(duì)列包含兩種操作：

enqueue

dequeue

2.1 enqueue

enqueue，將數(shù)據(jù)存儲(chǔ)到隊(duì)列中，如圖所示，將12存到隊(duì)列中。

2.2 dequeue

dequeue，將數(shù)據(jù)從隊(duì)列中移除，如圖，將10從隊(duì)列中移除。

三、堆棧和隊(duì)列的區(qū)別

3.1 工作原則

堆棧：遵循后進(jìn)先出 (LIFO) 原則，最后插入的元素首先被刪除。

隊(duì)列：遵循先進(jìn)先出 (FIFO) 原則，第一個(gè)添加的元素首先從列表中刪除。

3.2 操作

堆棧：

隊(duì)列：

3.3 工作原則

堆棧：pop 操作用于從堆棧中刪除元素，而 push 操作用于將元素插入堆棧中。

隊(duì)列：dequeue出隊(duì)操作從隊(duì)列中刪除元素，enqueue入隊(duì)操作將元素插入隊(duì)列。

3.4 類型

堆棧：沒有任何類型。

隊(duì)列：分為三種類型：循環(huán)隊(duì)列、優(yōu)先隊(duì)列、雙端隊(duì)列。

3.5 使用場景

堆棧：用于解決遞歸問題。

隊(duì)列：用于解決具有順序處理的問題。

3.6 線性集合

堆棧：垂直。

隊(duì)列：水平。

四、堆棧和隊(duì)列相似之處

4.1 線性數(shù)據(jù)結(jié)構(gòu)

堆棧和隊(duì)列都是線性數(shù)據(jù)結(jié)構(gòu)，這意味著元素是按順序存儲(chǔ)的，并且在一次運(yùn)行中訪問。

4.2 大小靈活

堆棧和隊(duì)列的大小都是靈活的，這意味著它們可以根據(jù)運(yùn)行時(shí)的要求進(jìn)行增長和收縮。

總結(jié)

堆棧和隊(duì)列是比較常見的數(shù)據(jù)結(jié)構(gòu)，本文用精簡的語言解釋了什么是堆棧以及什么是隊(duì)列，最后還進(jìn)行了比較，至于到底使用堆棧還是使用隊(duì)列，還是要看場景，具體問題具體分析。