🔥 數據結構修煉場 🔥
💥 棧與隊列 · 終極試煉 💥
🚀 理論已加載完畢,代碼之魂覺醒時刻!
?? 是時候用實戰
點燃你的算法之力了——
「題目風暴,來襲!」
(握緊鍵盤,接受挑戰吧 ?)
“Talk is cheap. Show me the code.”
????????????????—— Linus Torvalds
1.有效的括號
題目:
畫圖分析:
具體思路如下:
- 使用棧來處理括號匹配:棧是一種后進先出(LIFO)的數據結構,非常適合處理括號匹配問題。當遇到左括號([、(、{)時,將其壓入棧中;當遇到右括號(]、)、})時,從棧中彈出一個左括號進行匹配。
- 遍歷字符串:從字符串的第一個字符開始,逐個字符進行處理。
- 處理左括號:如果當前字符是左括號,將其壓入棧中。
- 處理右括號:如果當前字符是右括號,檢查棧是否為空。如果棧為空,說明沒有對應的左括號,字符串無效;如果棧不為空,彈出棧頂元素,檢查棧頂元素是否與當前右括號匹配。如果不匹配,字符串無效。
- 檢查棧是否為空:遍歷完字符串后,如果棧為空,說明所有的左括號都有對應的右括號,字符串有效;否則,字符串無效。
代碼分析:
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;
}
詳細解析:
- 結構體定義
typedef struct
{//兩個棧Stack _pushST; // 用于入隊操作的棧Stack _popST; // 用于出隊操作的棧
}MyQueue;
- 定義了一個名為
MyQueue
的結構體,該結構體包含兩個Stack
類型的成員變量_pushST
和_popST
。 _pushST
棧主要用于元素的入隊
操作,新元素會被壓入這個棧。_popST
棧用于元素的出隊
操作,當需要出隊時,會從這個棧中彈出元素。
- 隊列創建函數
MyQueue* mQueueCreate()
{MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));StackInit(&q->_pushST);StackInit(&q->_popST);return q;
}
mQueueCreate
函數的作用是創建一個新的MyQueue
實例。- 首先使用
malloc
函數為MyQueue
結構體分配內存空間。 - 然后調用
StackInit
函數分別對_pushST
和_popST
棧進行初始化。 - 最后返回指向新創建的
MyQueue
實例的指針。
- 入隊操作函數
//入棧
void myQueuePush(MyQueue* obj, int x)
{StackPush(&obj->_pushST, x);
}
myQueuePush
函數用于將一個整數x
插入到隊列中。- 直接調用
StackPush
函數將元素x
壓入_pushST
棧,因為_pushST
棧專門用于入隊操作
- 出隊操作函數
//出棧
int myQueuePop(MyQueue* obj)
{int front = myQueuePeek(obj);StackPop(&obj->_popST);return front;
}
myQueuePop
函數用于從隊列中移除
并返回
隊頭元素。- 首先調用
myQueuePeek
函數獲取隊頭
元素的值,并將其存儲在變量front
中。 - 然后調用
StackPop
函數從_popST
棧中彈出隊頭元素。 - 最后返回
隊頭
元素的值。
- 獲取隊頭元素函數
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;
}
- 元素入隊:
obj->_a[obj->_rear] = value;
把新元素value
存到_rear
所指向的位置。 - 移動隊尾指針:
obj->_rear++;
讓_rear
指針向后移動一位。 - 取模運算實現循環:
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;
}
- 移動隊頭指針:
++obj->_front;
讓_front
指針向后移動一位。 - 取模運算實現循環:
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
又回到了數組的起始位置,實現了循環
。
總結:在循環隊列中,取模運算能夠把指針的移動范圍限制在數組的有效下標范圍之內,當指針移動到數組末尾時,通過取模運算可以讓指針回到數組的起始位置,從而實現循環的效果。這樣就能高效地利用數組空間,避免 “假溢出” 問題。
🎉🎉🎉
在這里本章就結束啦~
我們下期見~