?Hi！探索者們😉，歡迎踏入 408 數據結構的奇妙秘境🌿！?
我是 ankleless📚，和你并肩的尋寶人～ 這是我的探險手札🗺?，里面記著鏈表森林的岔路陷阱🕸?、棧與隊列城堡的機關密碼🔐、二叉樹山脈的攀登技巧🚶?♀?，還有哈希表迷宮的快捷密道🌀，盼著能幫你避開數據結構的暗礁險灘🌊。?
愿我們在算法峽谷🌄各自披荊斬棘，在復雜度峰頂🥇擊掌相慶，共觀數據流轉的星河璀璨🌠！沖呀！🚀
目錄
?編輯
1. 棧
1.1 基本概念
1.1.1 棧的定義
1.1.2 棧的基本操作
1.2 存儲結構
1.2.1 順序存儲
1.順序棧的實現
2. 順序棧的基本操作
1.2.2 共享棧
1.2.3?鏈式存儲
2. 隊列
2.1 基本概念
2.1.1 隊列的定義
2.2.2 隊列常見的基本操作
2.2 隊列的順序存儲結構
2.2.1 隊列的順序存儲
1. 棧
1.1 基本概念
1.1.1 棧的定義
棧（Stack）是只允許在一端進行插入或刪除操作的線性表。首先棧是一種線性表，但限定這種線性表只能在某一端進行插入和刪除操作。這種邏輯規則類似于手槍子彈的裝載和卸下，如下圖所示：
棧頂（Top）:線性表允許進行插入和刪除的一端（出棧和進棧）；
棧底（Bottom）：固定的，不允許進行插入和刪除的另一端；
空棧：不含任何元素的空表；
進棧（Push）：將一個新的元素添加到棧的棧頂的操作，新的元素會成為當前棧中新的棧頂；
出棧（Pop）：將棧的棧頂元素從棧中移除，由于棧只能操作棧頂，出棧后，原棧頂的下一個元素稱為新的棧頂。
如：
假設某個棧S=（a1, a2, a3, a4, a5, a6）(如上圖），那么我們可以知道a1為棧底元素，a6位棧頂元素。棧只能在棧頂進行插入和刪除操作，進棧次序依次為a1, a2, a3, a4, a5, a6;而出棧次序為a6, a5, a4, a3, a2, a1。由此可見，棧的操作特性可以明顯概括為后進先出（Last In First Out,LIFO）
注：每接觸一種新的數據結構，都應從邏輯結構、存儲結構和運算三個方面著手（數據結構的三大要素）
1.1.2 棧的基本操作
棧（Stack）后進先出（Last In First Out,LIFO）的特性決定了他是一種受限的訪問方式，僅允許在棧頂進行操作，他的基本操作如下：
#define Maxsize 50//定義棧中元素的最大個數typedef int Elemtype;//重定義類型名稱struct Sqstack
{Elemtype data[Maxsize];//存放棧中元素，底層是數組int top;//棧頂指針
};typedef struct Sqstack Sqstack;//重定義void InitStack(Sqstack* S);//初始化一個棧，傳入指針bool StackEmpty(Sqstack S);//判斷一個棧是否為空，若棧S為空則返回true,否則返回falsevoid Push(Sqstack* S, Elemtype x);//壓棧，若棧S未滿，則將x加入使之成為新棧頂void Pop(Sqstack* S, Elemtype* x);//出棧，若棧S非空，則用x返回棧頂元素void GetTop(Sqstack S, Elemtype* x);//讀取棧頂元素，但不出棧，若棧S非空，則用x返回棧頂元素void DestroyStack(Sqstack* S);//銷毀棧，并釋放棧S占用的存儲空間，在C++中"&"表示引用調用注：此處棧的存儲結構為順序存儲，底層是數組，由于棧的邏輯結構的限制，我們不能夠使用違反其邏輯結構的操作，如修改，頭插等（邏輯結構會顯著影響數據的運算）
在解答算法題時，若題干未做出限制，則也可以直接使用這些基本的操作函數；
棧的數學性質：當n個不同元素進棧時，出棧元素不同排列的個數為\(C_n = \frac{1}{n+1} \binom{2n}{n}\)，即卡特蘭數。其中，\(\binom{2n}{n}\)?是組合數，表示從 2n 個元素中選擇 n 個的組合數。
1.2 存儲結構
棧是一種操作受限的線性表，類似于線性表，他也有對應的兩種存儲方式
1.2.1 順序存儲
1.順序棧的實現
采用順序存儲的棧稱為順序棧，它利用一組地址連續的存儲單元存放自棧底到棧頂的數據元素，同時附設一個指針（top）指示當前棧頂元素的位置。
棧的順序存儲類型可描述為：
#define Maxsize 50//定義棧中元素的最大個數typedef int Elemtype;//重定義類型名稱struct Sqstack
{Elemtype data[Maxsize];//存放棧中元素，底層是數組int top;//棧頂指針
};棧頂指針：S.top，初始時設置S.top = -1;? ?
棧頂元素：S.data[S.top]；
進棧操作：棧不滿時，棧頂指針先加1，再送值到棧頂；
出棧操作：棧非空時，先取棧頂元素，再將棧頂指針減一；
棧空條件：S.top == -1；
棧滿條件：S.top == Maxsize - 1;
棧長：S.top + 1。
另一種常見的方式是：初始設置棧頂指針 S.top = 0；進棧時先將值送到棧頂，棧頂指針再加1；出棧時，棧頂指針先減1；再取棧頂元素；棧空的條件是S.top == 0；棧滿條件是 S.top == Maxsize
順序棧的入棧操作受數組上界的約束，當對棧的最大使用空間估計不足時，有可能會發生棧上溢，此時應及時向用戶報告信息，以便及時處理，避免出錯。
注：棧和隊列的判空、判滿條件，會因實際給的條件不同而變化，下面的代碼實現是在棧頂指針初始化-1的條件下的相應方法，而其他情況則需要具體情況具體分析。
2. 順序棧的基本操作
我們采用第一種方式對順序棧進行基本操作，如下圖，當棧空時S.top === -1；當進行壓棧和出棧操作時，S.top會指向新的棧頂。
下列是順序棧上常用的基本操作的實現。
（1）初始化
void InitStack(Sqstack* S)//初始化一個棧，傳入指針
{S->top = -1;//此時棧為空表
}（2）判棧空
bool StackEmpty(Sqstack S)//判斷一個棧是否為空，若棧S為空則返回true,否則返回false
{if (S.top == -1)return true;elsereturn false;
}（3）壓棧
void Push(Sqstack* S, Elemtype x)//壓棧，若棧S未滿，則將x加入使之成為新棧頂
{if (S->top == Maxsize - 1){printf("棧滿，無法壓棧\n");return;}S->top++;//先+1S->data[S->top] = x;//后輸入return;
}（4）出棧
void Pop(Sqstack* S, Elemtype* x)//出棧，若棧S非空，則用x返回棧頂元素
{if (S->top == -1){printf("棧空，無法出棧\n");return;}*x = S->data[S->top];//先賦值S->top--;//再-1return;}
（5）讀棧頂元素
void GetTop(Sqstack S, Elemtype* x)//讀取棧頂元素，但不出棧，若棧S非空，則用x返回棧頂元素
{if (S.top == -1){printf("棧空，無棧頂元素\n");return;}*x = S.data[S.top];printf("棧頂元素為%d\n", *x);return;
}僅為讀取棧頂元素，并沒有出棧操作，因此原棧頂元素依然保留在棧中。
（6）銷毀棧
void DestroyStack(Sqstack* S)//銷毀棧，并釋放棧S占用的存儲空間，在C++中"&"表示引用調用
{S->top == -1;printf("棧銷毀成功\n");
}注：這里的top指向的是棧頂元素，于是，進棧操作為S->data[++S->top] = x，出棧操作位*x = S->data[S->top--]。若棧頂指針初始化為S.top=0，即top指向棧頂元素的下一個位置，則入棧操作變為S->data[S->top++] = x；出棧操作變為*x = S->data[--S->top]。相應的棧空、棧滿條件也會發生變化，需要靈活思考，這一點也可以類比鏈表中的有無頭結點情況
1.2.2 共享棧
利用棧底位置相對不變的特性，可以讓兩個順序棧共享一個一維數組空間，將兩個棧的棧底分別設置在共享空間的兩端，兩個棧頂向共享空間的中間延伸。
兩個棧的棧頂指針都指向棧頂元素，top0 == - 1時0號棧為空，top1 = Maxsize時，1號棧為空；僅當兩個棧頂指針相鄰（top1 - top0 == 1）時，判斷棧滿。當0號棧入棧時 top0先加1再賦值，1號棧入棧時top1先減一再賦值；出棧時則剛好相反。
共享棧是為了更有效地利用存儲空間，兩個棧的空間相互調節，只有在整個存儲空間被占滿時才發生上溢。其存儲數據的時間復雜度均為O(1)?，所以對存儲效率沒有什么影響。
1.2.3?鏈式存儲
采用鏈式存儲的棧稱為鏈棧，鏈棧的優點便是便于多個棧共享存儲空間和提高其效率，且不存在棧滿上溢的情況。通常采用單鏈表實現鏈棧，并規定所有操作都是在單鏈表的表頭（視為棧頂）進行的。此處的舉例規定鏈棧沒有頭結點，Lhead指向棧頂元素,Lhead稱為棧頂指針（不要和單鏈表的表頭指針名稱搞混）。
棧的鏈式存儲類型可描述為
struct Linkstack
{Elemtype data;//存儲數據struct Linkstack* next;//指針域，指向下一個結點
};采用鏈式存儲，便于結點的插入和刪除。鏈棧的操作和鏈表類似，入棧和出棧的操作都在鏈表的表頭進行。需要注意的是，對于帶頭結點和不帶頭結點的鏈棧，具體的實現會有不同。
關于鏈棧的基本操作的實現將在后續的代碼中進行介紹。
2. 隊列
2.1 基本概念
2.1.1 隊列的定義
隊列（queue）簡稱隊，也是一種操作受限的線性表，只允許在表的一段進行插入，而在表的另一端進行刪除。向隊列中插入元素稱為入隊或進隊；刪除元素稱為出隊或離隊。這和我們日常生活中的排隊是一致的，最早排隊的也是最早離隊的，其操作的特性是先進先出（First In First Out,FIFO）
隊頭（Front）：允許刪除的一端，也稱為隊首。
隊尾（Rear）：允許插入的一端。
空隊列（Empty）：不含任何元素的空表。
2.2.2 隊列常見的基本操作
#define Maxsize 50typedef int Elemtype;//順序存儲結構-靜態數組
typedef struct
{Elemtype data[Maxsize];//用數組存放隊列元素int front, rear;//隊首指針和隊尾指針，他們具備指針的作用，但不是真正的指針
}SqQueue;typedef SqQueue SQ;bool InitQueue(SQ* Q);//初始化隊列，構造一個空隊列Qbool QueueEmpty(SQ Q);//判隊列空，若隊列空返回true，否則返回falsebool EnQueue(SQ* Q,Elemtype x);//入隊，若隊列Q未滿，將x加入，使之稱為新的隊尾。Elemtype DeQueue(SQ* Q);//出隊，若隊列Q非空，刪除隊首元素，用x返回bool GetHead(SQ Q, Elemtype* x);//讀隊首元素，若隊列Q非空，則將隊首元素賦值給x
注：棧和隊列是操作受限的線性表，因此不是任何對線性表的操作都可以作為棧和隊列的操作。比如，不可以隨便讀取棧或者隊列中間的某個數據。
2.2 隊列的順序存儲結構
2.2.1 隊列的順序存儲
隊列的順序實現是指分配一塊連續的存儲單元存放隊列中的元素，并附設兩個指針：隊首指針front指向隊首元素，隊尾指針rear指向隊尾元素的下一個位置（不同的版本或作者對front和rear的定義肯不同，這也會導致后續操作的代碼設置有所不同，需要根據具體問題具體分析）
隊列的順序存儲類型可描述為
#define Maxsize 50typedef int Elemtype;//順序存儲結構-靜態數組
typedef struct
{Elemtype data[Maxsize];//用數組存放隊列元素int front, rear;//隊首指針和隊尾指針
}SqQueue;初始時：Q.front = Q.rear = 0；
入隊操作：隊不滿時，先送值到隊尾元素，再將隊尾指針加一；
出隊操作：隊不空時，先取隊首元素值，再將隊首指針加一；
如下圖所示，當隊列初始化時，有 Q.front = Q.rear = 0成立，此時為空隊列；當隊列進行出隊五次的操作后，有 Q.front = Q.rear成立，此時為空隊列，故而Q.front = Q.rear可以作為隊列判空的條件。
思考一下：能否用Q.rear == Maxsize作為隊列滿的判斷條件呢？
答案顯然是不能，當出隊4次后，隊列中僅有一個元素，但此時仍滿足改條件。這時入隊出現“上溢出”，但這種溢出并不是真正的溢出，在data數組中依然存在可以存放元素的空位置，所以是一種“假溢出”。
2.2.2 循環隊列
針對順序隊列“假溢出”的問題，循環隊列可以很好地解決。
循環隊列是將順序隊列抽象成一個環狀的空間，即把存儲隊列元素的表從邏輯上視為一個環，稱為循環隊列。當隊首指針Q.front == Maxsize - 1后，再前進一個位置就自動到0，這可以利用除法取模運算（%）來實現。
初始時：Q.front = Q.rear = 0；
隊首指針進1：Q.front = (Q.front + 1)%Maxsize；
隊尾指針進1：Q.rear= (Q.rear + 1)%Maxsize；
隊列長度：(Q.rear + Maxsize - Q.front)%Maxsize；（此式子需要加強理解）
出入隊時：指針都按順時針方向進一，如下圖：
為了區分是隊空還是隊滿的情況，有三種處理方式：
1）犧牲一個單元來區分隊滿和隊空。入隊時少用一個隊列單元，這是一種較為普遍的做法，約定以“隊首指針在隊尾指針的下一個位置作為隊滿的標志”，如上圖（d2）所示。
這種情況的判空判滿十分重要
隊滿條件：(Q.rear + 1)%Maxsize == Q.front；
隊空條件：Q.front = Q.rear；
隊列中元素的個數：(Q.rear + Maxsize - Q.front)%Maxsize。
2）類型中增設size數據成員，表示元素個數。若刪除成功，則size減1，若插入成功，則size加1，隊空時，Q.size == 0；隊滿時，Q.size == Maxsize，這兩種情況都有Q.front = Q.rear。
3）類型中增設tag數據成員，以區分是隊滿還是隊空。刪除成功置tag = 0，若導致Q.front = Q.rear，則隊空；插入成功置tag = 1，若導致Q.front = Q.rear，則隊滿。
2.2.3 循環隊列的基本操作
（1）初始化
bool InitQueue(SQ* Q)//初始化隊列，構造一個空隊列Q
{Q->front = Q->rear = 0;//初始時兩個指針重合,且均為0return true;
}（2）判隊空
bool QueueEmpty(SQ Q)//判隊列空，若隊列空返回true，否則返回false
{if (Q.front == Q.rear)return true;elsereturn false;
}（3）入隊
bool EnQueue(SQ* Q, Elemtype x)//入隊，若隊列Q未滿，將x加入，使之稱為新的隊尾。
{if ((Q->rear +1)%Maxsize == Q->front)//棧滿,這個是循環隊列的判斷方式{printf("棧滿，無法插入\n");return false;}Q->data[Q->rear] = x;//插入數據Q->rear = (Q->rear + 1) % Maxsize;return true;
}（4）出隊
Elemtype DeQueue(SQ* Q)//出隊，若隊列Q非空，刪除隊首元素，用x返回
{if (Q->front == Q->rear){printf("棧空,無元素\n");return -1;}Elemtype x = Q->data[Q->front];//先保存返回值Q->front = (Q->front + 1) % Maxsize;//隨后隊首指針++return x;
}2.3 隊列的鏈式存儲結構
2.3.1 隊列的鏈式存儲
隊列的鏈式表示稱為鏈式隊列，它實際上是一個同時有隊首指針和隊尾指針的單鏈表，如下圖。隊首指針指向隊頭結點（出隊端），隊尾指針指向隊尾結點（入隊端），即單鏈表的最后一個結點。
隊列的鏈式存儲類型可表述為
typedef struct LinkNode//鏈式隊列結點
{Elemtype data;//用數組存放隊列元素struct LinkNode* next;//指向下一個結點
}LinkNode;typedef struct//鏈式隊列
{struct SqQueue* front;//隊首指針，出隊端struct SqQueue* rear;//隊尾指針，入隊端
}LinkQueue;不帶頭結點時，當Q.front == NULL且Q.rear ==NULL時，鏈式隊列為空。
帶頭結點時，當Q.front == Q.rear且LHead->next ==NULL時，鏈式隊列為空。
入隊時，建立一個新結點，將新結點插入到鏈表的尾部，并讓Q.rear指向這個新插入的結點（若原隊列為空隊，則令Q.front也指向該結點）。出隊時，首先判斷隊是否為空，若不空，則取出隊首元素，將其從鏈表中刪除，并讓Q.front指向下一個結點（若該結點為最后一個節點，則置Q.front和Q.rear都為NULL）。
不難看出，不帶頭結點的鏈式隊列在操作上往往比較麻煩，因此通常將鏈式隊列設計成一個帶頭結點的單鏈表，這樣插入和刪除操作就統一了，下圖為帶頭結點的鏈式隊列。
用單鏈表表示的鏈式隊列特別適合于數據元素變動比較大的情形，而且不存在隊列滿且產生溢出的問題。另外，假如程序中要使用多個隊列，與多個棧的情形一樣，最好使用鏈式隊列，這樣就不會出現存儲分配不合理和“溢出”的問題。
2.3.2 鏈式隊列的基本操作
（1）初始化
bool InitQueue(LinkQueue* Q)//初始化帶頭結點的鏈式隊列
{Q->front = Q->rear = (LinkNode*)malloc(sizeof(LinkNode));if (Q->front == NULL){perror("malloc\n");return false;}Q->front->next = NULL;return true;
}（2）判隊空
bool QueueEmpty(LinkQueue* Q)//判隊列空，若隊列空返回true，否則返回false
{if (Q->front == Q->rear)//判空條件return true;elsereturn false;
}
（3）入隊
ool EnQueue(LinkQueue* Q, Elemtype x)//入隊，若隊列Q未滿，將x加入，使之稱為新的隊尾。
{//沒有溢出風險LinkNode* q = (LinkNode*)malloc(sizeof(LinkNode));//創建存儲數據的結點if (q == NULL){perror("malloc\n");return false;}q->data = x;//載入數據q->next = NULL;Q->rear->next = q;Q->rear = q;//修改隊尾指針return true;}（4）出隊
bool DeQueue(LinkQueue* Q, Elemtype* x)//出隊，若隊列Q非空，刪除隊首元素，用x返回
{if (Q->front == Q->rear){printf("棧空\n");return false;}LinkNode* q = Q->front->next;//儲存要出隊的結點地址*x = q->data;//x返回值Q->front->next = q->next;if (Q->rear = q)Q->rear = Q->front;//如果只有一個結點，刪除后變空free(q);q = NULL;return true;
}
 -- MQTT篇)
