🔥 數據結構修煉場 🔥

💥 棧與隊列 · 終極試煉 💥
🚀 理論已加載完畢，代碼之魂覺醒時刻！
?? 是時候用實戰點燃你的算法之力了——

「題目風暴，來襲！」
（握緊鍵盤，接受挑戰吧 ?）

---

“Talk is cheap. Show me the code.”
????????????????—— Linus Torvalds

1.有效的括號

題目：

畫圖分析：

具體思路如下：

1. 使用棧來處理括號匹配：棧是一種后進先出（LIFO）的數據結構，非常適合處理括號匹配問題。當遇到左括號（[、(、{）時，將其壓入棧中；當遇到右括號（]、)、}）時，從棧中彈出一個左括號進行匹配。
2. 遍歷字符串：從字符串的第一個字符開始，逐個字符進行處理。
3. 處理左括號：如果當前字符是左括號，將其壓入棧中。
4. 處理右括號：如果當前字符是右括號，檢查棧是否為空。如果棧為空，說明沒有對應的左括號，字符串無效；如果棧不為空，彈出棧頂元素，檢查棧頂元素是否與當前右括號匹配。如果不匹配，字符串無效。
5. 檢查棧是否為空：遍歷完字符串后，如果棧為空，說明所有的左括號都有對應的右括號，字符串有效；否則，字符串無效。

代碼分析：

bool isValid(char*s)
{//定義一個棧Stack st;StackInit(&st);//初始化一個布爾變量 ret 為 true，用于記錄字符串是否有效bool ret = true;// while 循環遍歷字符串while (*s != '\0'){//處理左括號if (*s == '[' || *s == '(' || *s == '{'){StackPush(&st, *s);++s;//如果當前字符是左括號，將其壓入棧中，并將指針 s 指向下一個字符}//處理右括號else{//先檢查棧是否為空if (StackEmpty(&st))//這里為空，說明沒有對應的左括號{ret = false;break;//跳出循環}//如果棧不為空，獲取棧頂元素char top = StackTop(&st);//檢查棧頂元素是否與當前右括號匹配//不匹配，將 ret 置為 false 并跳出循環if (*s == ']' && top != '[')//當當前字符是右中括號 ] 時，檢查棧頂元素是否為左中括號 [。//如果不是，說明括號不匹配，字符串無效，將 ret 設為 false 并跳出循環。{ret = false;break;}if (*s == ')' && top != '('){ret = false;break;}if (*s == '}' && top != '{'){ret = false;break;}//匹配，彈出棧頂元素，并將指針 s 指向下一個字符StackPop(&st);++s;}}//檢查棧是否為空if (*s == '\0'){ret = StackEmpty(&st);}//遍歷完字符串后，如果棧為空，說明所有的左括號都有對應的右括號，將 ret 置為 true；//否則，將 ret 置為 falseStackDestory(&st);return ret;
}int main()
{//定義一個測試字符串 testchar test[] = "{[()]}";//調用 isValid 函數判斷該字符串是否有效，并將結果存儲在 result 中bool result= isValid(test);if (result){printf("字符串有效\n");}else{printf("字符串無效\n");}return 0;
}

問題：為什么要檢查棧是否為空🤔🤔🤔

if (*s == '\0')
{ret = StackEmpty(&st);
}

原因：
在遍歷完字符串后，還需要檢查棧是否為空。因為如果字符串是有效的，那么所有的左括號都應該有對應的右括號與之匹配，即棧中不應該有剩余的左括號。所以使用StackEmpty(&st)來檢查棧是否為空，如果棧為空，說明所有括號都匹配成功，將ret設為 true；如果棧不為空，說明還有左括號沒有對應的右括號，字符串無效，將ret設為 false。
綜上所述，這一步是為了確保字符串中所有的左括號都有對應的右括號，避免出現多余的左括號

2.用隊列實現棧

題目：

解題思路

棧遵循后進先出（LIFO）的原則，而隊列遵循先進先出（FIFO）的原則。要利用兩個隊列模擬棧，關鍵在于合理運用兩個隊列的入隊和出隊操作，以此實現棧的入棧、出棧、獲取棧頂元素以及判斷棧是否為空等操作。

• 入棧操作：把新元素添加到非空的隊列里。若兩個隊列都為空，可任選一個隊列添加元素。
• 出棧操作：把非空隊列里除最后一個元素之外的所有元素轉移到另一個空隊列中，接著將最后一個元素出隊，這個元素就是棧頂元素。
• 獲取棧頂元素：直接獲取非空隊列的隊尾元素。
• 判斷棧是否為空：當兩個隊列都為空時，棧為空。

代碼分析：

// 定義用兩個隊列模擬的棧結構體
typedef struct{Queue q1;Queue q2;
} MyStack;// 創建棧
MyStack* myStackCreate() 
{MyStack* st = (MyStack*)malloc(sizeof(MyStack));if (st == NULL) {printf("內存分配失敗\n");exit(-1);}//調用 QueueInit 函數對 q1 和 q2 兩個隊列進行初始化//&st->q1 表示取 st 所指向的結構體中 q1 成員的地址QueueInit(&st->q1);QueueInit(&st->q2);return st;//回指向新創建的 MyStack 結構體的指針
}// 入棧
void myStackPush(MyStack* obj, int x)//MyStack* obj 是指向要操作的棧的指針 
{//檢查 q1 隊列是否為空if (!QueueEmpty(&obj->q1)) //表示 q1 隊列不為空{QueuePush(&obj->q1, x);//若 q1 隊列不為空，就把元素 x 入隊到 q1 中}else {QueuePush(&obj->q2, x);//若 q1 隊列為空，將元素 x 入隊到 q2 中}
}// 出棧
int myStackPop(MyStack* obj)
{//初始化兩個指針 emptyQ 和 nonemptyQ，分別指向 q1 和 q2 隊列Queue* emptyQ = &obj->q1;Queue* nonemptyQ = &obj->q2;//檢查 q1 隊列是否為空，若不為空，交換 emptyQ 和 nonemptyQ 的指向if (!QueueEmpty(&obj->q1)) {emptyQ = &obj->q2;nonemptyQ = &obj->q1;}//當非空隊列中的元素數量大于 1 時，執行循環while (QueueSize(nonemptyQ) > 1) {QueuePush(emptyQ, QueueFront(nonemptyQ));//把非空隊列的隊首元素入隊到空隊列中QueuePop(nonemptyQ);//將非空隊列的隊首元素出隊}int top = QueueFront(nonemptyQ);//獲取非空隊列的隊首元素，此元素即為棧頂元素QueuePop(nonemptyQ);//將棧頂元素出隊return top;//返回棧頂元素
}// 獲取棧頂元素
int myStackTop(MyStack* obj)
{if (!QueueEmpty(&obj->q1))//檢查 q1 隊列是否為空，若不為空 {return QueueBack(&obj->q1);//返回 q1 隊列的隊尾元素}else {return QueueBack(&obj->q2);//若 q1 隊列為空，返回 q2 隊列的隊尾元素}
}// 判斷棧是否為空
bool myStackEmpty(MyStack* obj) 
{return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);//當且僅當 q1 和 q2 兩個隊列都為空時，返回 true，否則返回 false
}// 銷毀棧
void myStackFree(MyStack* obj)
{if (obj == NULL){return;}QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);
}
int main()
{MyStack* st = myStackCreate();if (st == NULL) {return 1;檢查棧是否創建成功，若失敗，返回 1 表示程序異常退出}//依次將元素 1、2、3 入棧myStackPush(st, 1);myStackPush(st, 2);myStackPush(st, 3);while (!myStackEmpty(st)){printf("棧頂元素為: %d\n", myStackTop(st));myStackPop(st);}myStackFree(st);return 0;
}

運行結果：

3.用棧實現隊列

題目：

代碼分析：

typedef struct
{//兩個棧Stack _pushST;//注意這里很容易錯Stack _popST;//要空格表示兩個成員變量是棧類型
}MyQueue;MyQueue* mQueueCreate()
{MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));StackInit(&q->_pushST);StackInit(&q->_popST);return q;
}//入棧
void myQueuePush(MyQueue* obj, int x)
{StackPush(&obj->_pushST, x);
}//出棧
int myQueuePop(MyQueue* obj)
{int front = myQueuePeek(obj);StackPop(&obj->_popST);return front;
}int myQueuePeek(MyQueue* obj)
{//如果是非空的if (!StackEmpty(&obj->_popST)){return StackTop(&obj->_popST);//返回_pushST隊頭的數據}//為空就要把另外一個棧里面的數據導過來else{while (!StackEmpty(&obj->_pushST)){StackPush(&obj->_popST, StackTop(&obj->_pushST));StackPop(&obj->_pushST);//將_pushST里面的數據導到_popST里面}return StackTop(&obj->_popST);}
}//判斷是不是為空
//判斷隊列是否為空函數
bool myQueueEmpty(MyQueue* obj)
{return StackEmpty(&obj->_popST) && StackEmpty(&obj->_pushST);
}void myQueueFree(MyQueue* obj)
{StackDestory(&obj->_pushST);//調用 StackDestory 函數分別銷毀 _pushST 和 _popST 棧，釋放棧所占用的內存StackDestory(&obj->_popST);free(obj);//最后使用 free 函數釋放 MyQueue 結構體本身所占用的內存
}//棧是后進先出；隊列是先進先出
int main() 
{MyQueue* queue = mQueueCreate();// 入隊操作myQueuePush(queue, 1);myQueuePush(queue, 2);myQueuePush(queue, 3);// 獲取隊頭元素//注意：在這段用兩個棧模擬隊列的代碼里，獲取隊頭元素主要是從 _popST 棧獲取printf("隊頭元素: %d\n", myQueuePeek(queue));// 出隊操作printf("出隊元素: %d\n", myQueuePop(queue));printf("出隊元素: %d\n", myQueuePop(queue));// 再次入隊myQueuePush(queue, 4);// 繼續出隊while (!myQueueEmpty(queue)) {printf("出隊元素: %d\n", myQueuePop(queue));}// 釋放隊列內存myQueueFree(queue);return 0;
}

詳細解析:

1. 結構體定義

typedef struct
{//兩個棧Stack _pushST; // 用于入隊操作的棧Stack _popST;  // 用于出隊操作的棧
}MyQueue;

• 定義了一個名為MyQueue的結構體，該結構體包含兩個Stack類型的成員變量_pushST和 _popST。
• _pushST 棧主要用于元素的入隊操作，新元素會被壓入這個棧。
• _popST 棧用于元素的出隊操作，當需要出隊時，會從這個棧中彈出元素。

2. 隊列創建函數

MyQueue* mQueueCreate()
{MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));StackInit(&q->_pushST);StackInit(&q->_popST);return q;
}

• mQueueCreate 函數的作用是創建一個新的MyQueue實例。
• 首先使用malloc函數為MyQueue結構體分配內存空間。
• 然后調用StackInit函數分別對_pushST和_popST棧進行初始化。
• 最后返回指向新創建的MyQueue實例的指針。

3. 入隊操作函數

//入棧
void myQueuePush(MyQueue* obj, int x)
{StackPush(&obj->_pushST, x);
}

• myQueuePush 函數用于將一個整數x插入到隊列中。
• 直接調用StackPush函數將元素x壓入_pushST棧，因為_pushST棧專門用于入隊操作

4. 出隊操作函數

//出棧
int myQueuePop(MyQueue* obj)
{int front = myQueuePeek(obj);StackPop(&obj->_popST);return front;
}

• myQueuePop 函數用于從隊列中移除并返回隊頭元素。
• 首先調用myQueuePeek函數獲取隊頭元素的值，并將其存儲在變量front中。
• 然后調用StackPop函數從_popST棧中彈出隊頭元素。
• 最后返回隊頭元素的值。

5. 獲取隊頭元素函數

int myQueuePeek(MyQueue* obj)
{//如果是非空的if (!StackEmpty(&obj->_popST)){return StackTop(&obj->_popST); // 返回_pushST隊頭的數據}//為空就要把另外一個棧里面的數據導過來else{while (!StackEmpty(&obj->_pushST)){StackPush(&obj->_popST, StackTop(&obj->_pushST));StackPop(&obj->_pushST);//將_pushST里面的數據導到_popST里面}return StackTop(&obj->_popST);}
}

• myQueuePeek 函數用于返回隊列的隊頭元素，但不將其從隊列中移除。
• 首先檢查_popST棧是否為空。如果不為空，直接調用StackTop函數返回_popST棧的棧頂元素，因為 _popST 棧的棧頂元素就是隊列的隊頭元素。
• 如果_popST棧為空，則需要將_pushST棧中的所有元素依次彈出并壓入_popST棧中，這樣 _popST 棧中的元素順序就與隊列的順序一致了。
• 最后返回_popST棧的棧頂元素。

代碼運行：

4.設計循環隊列

題目：

畫圖分析：

代碼分析：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef struct
{int* _a;//是一個整數指針，用于指向存儲隊列元素的動態數組int _front;//表示隊列的隊頭位置int _rear;//表示隊列的隊尾位置int _k;//表示隊列的最大容量
}MyCircularQueue;//初始化
MyCircularQueue* myCircularQueueCreate(int k)
{MyCircularQueue* q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//為 MyCircularQueue 結構體分配內存q->_a = (int*)malloc(sizeof(int) * (k + 1));//多開一個空間//為存儲隊列元素的數組分配 k + 1 個整數的空間，多開一個空間是為了區分隊列滿和隊列空的情況q->_front = 0;q->_rear = 0;q->_k = k;//記錄隊列的最大容量 kreturn q;
}//空的
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{return obj->_front == obj->_rear;//當 _front 和 _rear 相等時，隊列為空
}//滿的
bool myCircularQueueIsFull(MyCircularQueue* obj)
{return (obj->_rear + 1) % (obj->_k + 1) == obj->_front;
}//插入數據
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{//如果是滿的if (myCircularQueueIsFull(obj)){return false;}//入數據obj->_a[obj->_rear] = value;//將元素插入到隊尾位置obj->_rear++;obj->_rear %= (obj->_k  + 1);//更新 _rear 的位置，使用取模運算實現循環return true;
}//刪除數據
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{//為空if (myCircularQueueIsEmpty(obj)){return false;}++obj->_front;obj->_front %= (obj->_k + 1);return true;
}//獲取隊頭的數據
int myCircularQueueFront(MyCircularQueue* obj)
{//如果是空的if(myCircularQueueIsEmpty(obj)){return -1;}else{return obj->_a[obj->_front];//返回隊頭元素}
}//獲取隊尾的數據
int myCircularQueueRear(MyCircularQueue* obj)
{//如果是空的if (myCircularQueueIsEmpty(obj)){return -1;}else{int tail = obj->_rear - 1;//計算隊尾元素的位置，考慮循環的情況if (tail == -1){tail = obj->_k;}return obj->_a[tail];//返回隊尾元素}
}//釋放
void myCircularQueueFree(MyCircularQueue* obj)
{free(obj->_a);free(obj);
}int main() 
{MyCircularQueue* queue = myCircularQueueCreate(3);myCircularQueueEnQueue(queue, 1);myCircularQueueEnQueue(queue, 2);myCircularQueueEnQueue(queue, 3);printf("Front: %d\n", myCircularQueueFront(queue));//打印隊頭printf("Rear: %d\n", myCircularQueueRear(queue));//打印隊尾myCircularQueueDeQueue(queue);//隊頭元素 1 出隊printf("Front after dequeue: %d\n", myCircularQueueFront(queue));//那就2變成了隊頭myCircularQueueFree(queue);return 0;
}

運行結果：

🤔🤔🤔思考一個問題：
這里是怎么使用取模運算實現循環的

入隊操作中的取模運算

// 插入數據
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{// 如果是滿的if (myCircularQueueIsFull(obj)){return false;}// 入數據obj->_a[obj->_rear] = value;obj->_rear++;obj->_rear %= (obj->_k + 1);return true;
}

1. 元素入隊：obj->_a[obj->_rear] = value; 把新元素value存到_rear所指向的位置。
2. 移動隊尾指針：obj->_rear++; 讓_rear指針向后移動一位。
3. 取模運算實現循環：obj->_rear %= (obj->_k + 1); 對_rear進行取模運算，其除數為 _k + 1（_k 代表隊列的最大容量）。

示例說明：

• 假設隊列的最大容量_k為 3，那么數組的大小就是 _k + 1 = 4，數組下標范圍是0到 3。
• 初始時，_rear = 0，插入元素后，_rear 變為 1。
• 持續插入元素，當_rear變為3時，再插入元素，_rear 先加1變成 4，然后進行取模運算 4 % 4 = 0，這就使得_rear又回到了數組的起始位置，達成了循環的效果。

出隊操作中的取模運算

// 刪除數據
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{// 為空if (myCircularQueueIsEmpty(obj)){return false;}++obj->_front;obj->_front %= (obj->_k + 1);return true;
}

1. 移動隊頭指針：++obj->_front; 讓 _front 指針向后移動一位。
2. 取模運算實現循環：obj->_front %= (obj->_k + 1); 對 _front 進行取模運算，除數同樣是 _k + 1。

示例說明：

• 同樣假設隊列的最大容量 _k 為 3，數組大小為 4，下標范圍是0到 3。
• 初始時，_front = 0，出隊操作后，_front 變為 1。
• 不斷進行出隊操作，當_front變為3時，再出隊，_front 先加1變成 4，接著進行取模運算 4 % 4 = 0，_front 又回到了數組的起始位置，實現了循環。

總結：在循環隊列中，取模運算能夠把指針的移動范圍限制在數組的有效下標范圍之內，當指針移動到數組末尾時，通過取模運算可以讓指針回到數組的起始位置，從而實現循環的效果。這樣就能高效地利用數組空間，避免 “假溢出” 問題。

🎉🎉🎉
在這里本章就結束啦~
我們下期見~