🔔前言：為學日進，為道日損，與諸君攜手共勉 💖💖💖

人生好似一個小小的佇列呀，春夏秋冬年年輪回，早中晚夜天天回圈，變化的是時間，不變的是我們對未來執著的信念！

🔔堆疊

💓堆疊的定義和基本操作

🌟堆疊的定義

堆疊(stack)是限定僅在表尾進行插入和洗掉操作的線性表
我們把允許插入和洗掉的一端稱為堆疊頂(top),另一端稱為(bottom),不含任何資料元素的堆疊稱為空堆疊，堆疊又稱為后進先出(Last In First Out)的線性表，簡稱LIFO結構，

注意:堆疊是一個線性表，也就是說堆疊是具有線性關系的，擁有它自己的直接前驅和直接后繼，只是，堆疊是一種特殊的線性表，只能在表尾進行插入和洗掉操作，這里的表尾通常也被叫做堆疊頂(top)

🌟堆疊的基本操作

堆疊的插入操作（push），叫做進堆疊，也稱壓堆疊、入堆疊，類似于將子彈壓入彈夾
堆疊的洗掉操作（pop），叫做出堆疊，有的也叫做彈堆疊，如同將彈夾中的子彈取出
進堆疊示意圖：

出堆疊示意圖：

進入下一個模塊啦~?
🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀

💓堆疊的存盤和實作

🌟堆疊陣列實作——演算法競賽必備

堆疊在演算法競賽中也算是常客了，只是使用它的時候需要注意，我們是用陣列模擬堆疊的思想來實作堆疊，那，為什么要用陣列了？我們平時學的都是結構體+指標實作的呀~

就筆者自己使用的C++而言，因為一般競賽中的測驗資料都要拉到極致，比如十萬、一百萬，假如使用結構體的方式，在new這十萬、一百萬的空間的時候，可能就超時了，包括下文的佇列也是同樣的道理，在競賽中，建議用陣列模擬，結構體加指標的玩法，筆者盲猜是用在工程中優化代碼效率的?
只是C++選手也可以偷偷懶，直接呼叫C++標準庫中提供的庫函式😉

下面就從一道例題來引入怎么用陣列快速的模擬堆疊吧~
例題描述：

?原題傳送門

參考代碼(C++版本)

#include <iostream>

using namespace std;

const int N = 100010;

int m;
int stk[N];     //用于模擬堆疊的陣列
int tt;         //尾指標

int main()
{
    cin >> m;
    while (m -- )
    {
        string op;
        int x;

        cin >> op;
        if (op == "push")
        {
            cin >> x;
            stk[ ++ tt] = x;    //尾指標向后移動，實作進堆疊
        }
        else if (op == "pop") tt -- ; // 尾指標向前移動，剔除陣列末尾元素，實作出堆疊
        else if (op == "empty") cout << (tt ? "NO" : "YES") << endl;
        else cout << stk[tt] << endl;
    }

    return 0;
}

🌻進堆疊(push)

陣列模擬的堆疊，進堆疊代碼很簡單，只有一行…

		stk[ ++ tt] = x;    //尾指標向后移動，實作進堆疊

操作的原理圖如下：

🌻出堆疊(pop)

出堆疊操作就更短了~

		 else if (op == "pop") tt -- ; // 尾指標向前移動，剔除陣列末尾元素，實作出堆疊

🌻獲取資訊——堆疊頂元素和堆疊是否為空

獲取堆疊頂元素也就是獲取尾指標tt所指的空間中的資訊，因為是陣列模擬的，所以直接將tt放到陣列里面

		 else cout << stk[tt] << endl;

判斷堆疊是不是空堆疊是通過陣列下標實作的，假如現在尾指標tt在堆疊底(索引為0)的位置，這個堆疊就是空堆疊，對于這道題而言,取巧用了三元運算子

  			else if (op == "empty") cout << (tt ? "NO" : "YES") << endl;

說什么？掌握啦，嗯好，那咱們進入下一個模塊~?
🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀

🌟堆疊的鏈式存盤結構及實作——工程開發和期末應試必備

下面的內容了，是資料結構用在工程上和期末考試的卷子上的😭

堆疊的鏈式存盤結構實際上就是一個單鏈表，叫做鏈堆疊，插入和洗掉操作只能在鏈堆疊的堆疊頂進行，堆疊頂指標Top應該在鏈表的哪頭？

假如按照正常邏輯，放在鏈表的尾部，插入操作要從頭結點開始，挨著挨著遍歷過去，到最后一個元素，也就是堆疊頂就可以實作插入，
洗掉操作了？洗掉操作其實是沒有辦法進行的，因為鏈表的洗掉要知道被洗掉結點的前一個結點的資訊，我們沒法從鏈表的尾結點倒著回去找它的前一個結點，也沒有辦法確定它的前一個結點的資訊，因此洗掉操作就無法實作，

因此經過前人的總結，將頭指標所指的位置當做堆疊頂對于插入和洗掉操作都十分方便

🌻鏈堆疊型別定義

和單鏈表相同，定義一個結點型別，型別中的成員變數是資料域和指標域

typedef int Datatype;

typedef struct stacknode{
    Datatype data;				//資料域
    struct stacknode* next; //指標域
}LinkStack;

🌻初始化堆疊

首先創建一個鏈堆疊S，然后通過NULL將這個創建的堆疊清空，回傳被清空后的鏈堆疊的地址資訊
參考實作代碼：

LinkStack* InitStack()
{
    LinkStack* S;
    S = NULL;
    return S;
}

🌻判斷堆疊空

判斷一個堆疊是否為空，若堆疊為空，則回傳1，否則回傳0
參考實作代碼：

int EmptyStack(LinkStack* S)
{
    if(S == NULL) return 1;
    else return 0;

}

🌻進堆疊

實作流程：
①將新插入的結點p的指標域指向原堆疊頂S
②將堆疊頂S指向新結點p

參考實作代碼：

LinkStack* push(LinkStack *S,Datatype x)
{
    LinkStack* p;
    p = (LinkStack*)malloc(sizeof(struct stacknode));	//生成新結點 
    p->data = x;			//將x放到新結點的資料域 
    p->next = S; 		//將新結點插入鏈表的表頭之前 
    S = p;  				//讓頭指標執行這個新插入的p，可以理解為讓top指標指向這個新插入的結點

	return S; 			//回傳堆疊頂S 

}

🌻出堆疊

①p指標指向原堆疊頂S
② 堆疊頂S指向其下一個結點
③釋放p指標所指的空間

參考實作代碼：

LinkStack* pop(LinkStack* S , Datatype *x)
{
    LinkStack* p;
    if(EmptyStack(S))	//先判斷堆疊是否為空堆疊
    {
        printf("堆疊為空\n");
        return NULL;
    }else
    {
	    *x = S->data;		//堆疊頂元素取出來賦值給x 
	    p = S; 				//p指標指向原本的堆疊頂S 
	    S = S->next;		//原堆疊頂S指向下一個結點 
	    free(p);			//釋放原堆疊頂空間 
	    return S;			//回傳堆疊頂S 
    }
}

好啦~
鏈堆疊的兩個核心操作入堆疊push 和 出堆疊pop 就沒有啦，相信小伙伴已經明白是這么一回事了，下面的獲取堆疊頂元素和輸出堆疊中內容就相對輕松很多啦~

🌻取堆疊頂元素

參考實作代碼：

int GetTop(LinkStack* S,Datatype *x)
{
   
    if(EmptyStack(S))	 //先判斷堆疊是否為空
    {
        printf("堆疊為空\n");
        return 0;
    }else
    {
        *x = S->data;	//堆疊頂元素賦值給變數x 
        return 1;
    }

}

🌻顯示堆疊內元素

參考實作代碼

void ShowStack(LinkStack *S)
{

    LinkStack *p = S;
    if(p == NULL)
    {
        printf("堆疊為空\n");
    }else
    {
        printf("從堆疊頂起，各元素依次為：\n");
        while(p != NULL)
        {
            printf("%d\t",p->data);
            p = p->next;
        }
    }
}

🌟堆疊的應用舉例

🌻"進制轉換"領域

以十進制轉二進制為例，操作的流程是每次模2取得余數，整數自身除以權重2，從而更新整數自己，
可以考慮是將余數放到陣列里，用一個回圈反轉陣列，再用一個回圈將新的陣列遍歷輸出，聽起來其實還是蠻麻煩的

那么結合堆疊的先入后出的特性，會不會更好操作了？用push將余數壓入堆疊，再用pop將放到堆疊里面的余數一個一個的取出來，是不是感覺整體思路都清爽了很多了

實作流程：
用一個回圈處理傳入的十進制整數x，將它和2取余的結果入堆疊
用一個回圈輸出堆疊中的內容

參考實作代碼

//十進制轉二進制
void D_B(LinkStack *S,Datatype x)
{
   
    while(x)				 //讓余數入堆疊
    {
        S = push(S,x % 2);
        x /= 2;
    }
    printf("轉換后的二進制為：");
    while(!EmptyStack(S))
    {
        S = pop(S,&x);		//依次從堆疊中彈出每一個余數
        printf("%d",x);		//輸入每個余數
    }
}

🌻"運算式求值"領域

因為這個板塊有好多習題可以拎出來細細品味，所以筆者想在《演算法基礎》專欄中更出
比如2020年就有一道真題：2020年ACM-ICPC省賽B題 相同括號配對

💓堆疊總結

對于堆疊而言，最主要是要清楚它先入后出的特性，其次拿捏清楚指向堆疊頂元素的"指標"，因為無論是陣列模擬的堆疊還是結構體實作的堆疊，核心操作都是對指標的移動

相信小伙伴已經學會了吧，那咱們進入下一個模塊啦~?
🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀

🔔佇列

💓佇列的定義和基本運算

🌟佇列的定義

佇列是只允許在一端進行插入操作，而在另外一端進行洗掉操作的線性表
佇列是一種先進先出(First In First Out)的線性表，簡稱FIFO，允許插入的一端稱為隊尾，允許洗掉的一端稱為隊頭，

🌟佇列的基本運算

💓佇列的存盤和實作

🌟佇列陣列實作——演算法競賽必備

佇列在演算法競賽中也是常客了，主流的依舊是使用的陣列模擬的佇列，原因和堆疊用陣列模擬的原因一致，
佇列用得最多，知名度最廣的應該是在邊權相等的情況下用寬度優先搜索去求最短路徑，進而還有拓撲排序等等

下面依舊是從一道例題中引入陣列模擬佇列
樣例描述：

?原題傳送門

參考實作代碼(C++版本)

#include <iostream>

using namespace std;

const int N = 100010;

int m;
int q[N];//模擬佇列的陣列
hh, tt = -1;//隊頭和隊尾

int main()
{
    cin >> m;

    while (m -- )
    {
        string op;
        int x;

        cin >> op;
        if (op == "push")
        {
            cin >> x;
            q[ ++ tt] = x; //移動尾指標實作插入
        }
        else if (op == "pop") hh ++ ; //移動頭指標位置，實作洗掉
        else if (op == "empty") cout << (hh <= tt ? "NO" : "YES") << endl;
        else cout << q[hh] << endl;
    }

    return 0;
}

佇列的初始狀態如下圖

在初始化狀態中，隊頭隊尾都放在索引為0的位置也是可以的，那么在后面移動尾指標tt的時候使用后綴++即可，

		//隊尾從-1開始
		 q[ ++ tt] = x; //移動尾指標實作插入
		 
		 //變通===> 隊尾從0開始
		 q[tt ++] = x; //移動尾指標實作插入

🌻入隊

因為本質是陣列，所以當有新資料插入的時候，讓新資料插入到陣列的尾部就可以實作入隊操作，

            cin >> x;
            q[ ++ tt] = x; //移動尾指標實作插入

🌻出隊

陣列模擬的佇列中，使用隊頭指標hh來維護佇列中第一個元素的位置，當有元素要出隊了，那么通過移動隊頭指標調整佇列的區間，從而確定新的隊頭，

		else if (op == "pop") hh ++ ; //移動頭指標位置，實作洗掉

新的姿勢增加了😉，那咱們向下一個模塊出發啦~?
🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀

🌟佇列鏈表實作——工程開發和期末應試必備

🌻鏈佇列型別定義

使用結構體加上指標實作的佇列在本質上仍舊是線性表中的鏈表，只是對它開發了新的特性，實作了先進先出(FIFO)的效果，

參考實作代碼

typedef int DataType;		//定義DataType為int 型
typedef struct qnode{		//鏈佇列存盤型別 
	DataType data;			//定義鏈隊中每個結點的資料域 
	struct qnode *next;		//定義鏈隊中每個結點的指標域 
}LinkListQ; 

typedef struct
{
	LinkListQ *front,*rear; //鏈佇列的隊頭指標和隊尾指標 
}LinkQueue;					

只是對于佇列而言，為了實作維護一段隊伍的效果，需要額外增加一個隊頭指標front和一個隊尾指標rear

LinkListQ *front,*rear; //鏈佇列的隊頭指標和隊尾指標 

🌻初始化佇列

操作流程：
①先建立一個佇列的頭結點Q，該頭結點中有維護佇列的隊頭指標front和隊尾指標rear
② 建立一個鏈隊的頭結點p,并讓其指標域為空
③ 將Q->front 和 Q->rear都指向該頭結點并回傳指標Q
參考實作代碼：

LinkQueue *InitQueue()
{
	LinkQueue *Q;
	LinkListQ *p;
	Q = (LinkQueue *) malloc(sizeof (LinkQueue));  //建立鏈佇列頭指標所指的結點 
	p = (LinkListQ *)malloc(sizeof(LinkListQ));		//建立鏈佇列的頭結點 
	p->next = NULL;
	Q->front = p;									//Q指標所指的front指標指向p 
	Q->rear  = p;									//Q指標所指的rear指標指向p 
	
	return Q;
}

🌻入隊操作

實作流程：
①將新結點插入到隊尾，原本隊尾的指標域Q->rear->next 指向新結點p(Q->rear->next = p;)
②將隊尾Q->rear指向新結點p(Q->rear = p; )
參考實作代碼：

//入隊函式 
void InQueue(LinkQueue *Q,DataType x)
{
	LinkListQ *p;
	p = (LinkListQ *)malloc(sizeof(LinkListQ));	//生成新的結點
	p->data = x;								//將x存入新結點的資料域 
	p->next = NULL;					
	Q->rear->next = p;							//將新結點插入到鏈隊之后 
	Q->rear = p; 								//隊尾指標指向隊尾元素 
}

🌻出隊操作

操作①：將隊頭指標的指標域指向原本隊頭元素的下一個位置的地址（Q->front->next = p->next;）
操作②：當佇列中僅含有一個元素的時候，出隊后隊尾指標指向隊頭指標所指向的位置(if(p->next == NULL) Q->rear = Q->front)
操作③：釋放p指標所指的空間

參考實作代碼：

//判斷佇列是否為空的函式
int EmptyQueue(LinkQueue *Q) 
{
	if(Q->front == Q->rear) return 1;
	else return 0;
}

//出隊函式 
int DeQueue(LinkQueue *Q,DataType *x)
{
	LinkListQ *p;
	if(EmptyQueue(Q))  						//呼叫判空函式，判斷當前佇列是不是為空
	{
		printf("隊空，無法出隊任何元素\n")	;
		return 0;
	}else  									//佇列不空 
	{
		p = Q->front->next;					//p指向隊頭元素
		*x = p->data;						//取出隊頭元素賦值給x
		Q->front->next = p->next;			//隊頭指標的指標域中存放新隊頭元素的地址
		if(p->next == NULL)  Q->rear = Q->front; //處理佇列中只有一個元素的情況
		free(p);
		return 1;
		 
	}
}

🌻求隊頭元素

參考實作代碼：

int GetFront(LinkQueue *Q,DataType *x) 
{
	if(EmptyQueue(Q))				//呼叫判空函式，判斷當前佇列是不是為空
	{
		printf("佇列為空，無法獲取任何元素");
		return 0;
	}else
	{
		*x = Q->front->next->data;	//將隊頭元素中存放的資料給x
		return 1; 
	}
}

🌻 遍歷鏈隊

void ShowQueue(LinkQueue *Q)
{
	LinkListQ *p = Q->front->next;
	if(p == NULL) printf("佇列為空，無法顯示任何元素\n");
	else
	{
		printf("從隊頭起，佇列中的每個元素是：");
		while(p != NULL)
		{
			printf("%d ",p->data);
			p = p->next;
		}
	}
}

好啦~到這里，鏈佇列的操作就沒有啦，核心的了，是出隊和入隊操作，使用結構體加指標實作的佇列，在代碼量上確實多了很多😭

曾經高考考場上笑談一方，現在只求老師給個重點，就讓鏈堆疊和鏈佇列在考場上最后綻放一次吧

新的痛苦增加了呀，朋友們
🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀

🌟佇列的應用舉例

🌻"寬度優先搜索(BFS)"方向

佇列是寬搜實作的核心結構，因為筆者之前已經詳解總結和演示過寬搜，那我這里就不再贅述啦，小伙伴們可以看看這篇文章喔
演算法基礎系列第三章——層層推進的BFS
假如感覺已經掌握了寬搜的小伙伴，可以考慮去壁咚一下佇列在高等圖演算法中的玩法
演算法基礎系列第三章——萬字精編手把手教你壁咚拓撲排序，讓ta乖乖聽話~

🌻"優先佇列"——堆

優先佇列是一種特殊的佇列了，優先佇列的出隊是按照元素的優先級出隊，比如，數值最小的先出隊，或者數值最大的先出隊，優先佇列和二叉樹結合起來，就又變成了一種神器——堆
同樣的，因為筆者之前已經寫過和堆相關的內容了，現在就直接推薦小伙伴們去看一看啦~
資料結構——被優先佇列玩起來的“樹“

💓佇列總結

陣列模擬的佇列實作和操作都是比較清晰和輕松的，只是有時候需要注意元素假如要進行多次的入隊和出隊，那么用于實作佇列結構的陣列開頭部分的空間就會被嚴重浪費，這種情況可以采用"回圈佇列"的方式優化，筆者這里就不展開講了，我想在后續的《演算法基礎》專欄中結合習題進行系統的剖析，

結構體+指標的實作方式就要對指標十分小心，清楚當前的指標是指向誰的

🔔寫在最后🎈🎈🎈

編者暫時也閱歷有限，可能個別地方考慮不周，若有偏僻，歡迎小伙伴們及時指正喔( ^ - ^ )

持續更新對資料結構的總結和理解ing💖💖💖