圖均為手繪,代碼基于vs2022實現

系列文章目錄

數據結構初探: 順序表
數據結構初探:鏈表之單鏈表篇
數據結構初探:鏈表之雙向鏈表篇
鏈表特別篇:鏈表經典算法問題
數據結構:棧篇
數據結構:隊列篇

---

---

前言

• 棧和隊列作為基礎數據結構，是算法設計中的重要基石。它們在操作系統、編譯器設計、網絡協議等領域有著廣泛應用。本文將通過C語言實現經典算法問題，幫助讀者深入理解它們的底層原理和應用技巧。學習這些內容不僅能提升算法能力，還能加深對內存管理和數據結構設計的理解。

---

一.有效的括號(leetcode 20)

讓我們先來看看題目:

讓我們來理清楚思路:

• 首先,我們可以用棧來實現匹配

1.我們將左括號入棧;
2.在遍歷中找到右括號,進行匹配;

• 在這個過程中,我們需要手撕一個棧的代碼出來,加在題目代碼之前,如果發現還不太熟練,可以再去我的這篇博客中熟悉熟悉—> 數據結構:棧篇
• 我們還是上代碼實際感受一下吧(考慮到篇幅有限,已省略棧的代碼):

//注意這里是字符,棧的代碼中要將int改為char
//typedef char STDataType;
bool isValid(char* s) {ST st;//創建棧STInit(&st);//初始化棧while(*s)//依次遍歷字符串{if(*s == '(' || *s == '[' || *s == '{')//如果是左括號{STPush(&st,*s);//我們就將其入棧}else//其他情況{if(STEmpty(&st))//如果沒找到左括號,就算下面有右括號{//我們也無法找到匹配的括號STDestroy(&st);//所以銷毀,防止內存泄漏return false;//直接返回false,表示找不到匹配的括號}//因為題目要求的是按順序一一對應;char top=STTop(&st);//此時記錄下棧頂元素STPop(&st);//再pop,表示出棧操作//匹配括號邏輯結構//大家可以自行分析;//即如果右括號沒有在棧頂找到對應的左括號,則錯誤if((*s == ')' && top != '(')||(*s == ']' && top != '[')||(*s == '}' && top != '{')){STDestroy(&st);//所以銷毀,防止內存泄漏return false;//直接返回false,表示找不到匹配的括號}}s++;//更新循環條件}bool ret=STEmpty(&st);//記錄是否找到對應括號的狀態STDestroy(&st);//銷毀,防止內存泄漏return ret;//返回對應狀態
}

學完后,自己多多練習,自行手撕,理清邏輯即可;

二.用隊列實現棧(leetcode 225)

讓我們先來看看題目:

讓我們來理清楚思路:
我們需要用到兩個隊列來實現棧:

• 一個用來當作入棧隊列
• 一個用來當作出棧隊列
• 我們還要注意其LIFO的性質,和隨進隨出的特點
  1.我們需要保持一個隊列為空,一個隊列存數據
  2.出棧,把前面的數據導入空隊列
  3.如此兩班來回倒,就可以實現棧的特性;
  邏輯如圖:
  
  在這個過程中,我們需要手撕隊列的代碼出來,加在題目代碼之前,如果發現還不太熟練,可以再去我的這篇博客中熟悉熟悉—> 數據結構:隊列篇
  我們來實戰一下:

//創建兩個隊列的結構體
typedef struct {Queue q1;Queue q2;
} MyStack;
//我們需要動態開辟出空間來實現mystack
MyStack* myStackCreate() {MyStack* pst=(MyStack*)malloc(sizeof(MyStack));if(pst == NULL){perror("malloc fail");return NULL;}QueueInit(&pst->q1);//對兩個隊列初始化QueueInit(&pst->q2);return pst;//返回初始化后的我們的mystack
}
//來實現棧的插入
void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(&obj->q1))//如果q1不為空就插入到q1里{//反正有一個隊列里面是空的,我們不能插入,一旦插入就會弄亂整體的邏輯QueuePush(&obj->q1,x);//可以參看上文圖進行理解}else//如果q2不為空就插入到q2里{//兩個都為空就隨便選一個QueuePush(&obj->q2,x);}
}
//實現棧的刪除,題目要求:移除并返回棧頂元素
int myStackPop(MyStack* obj) {//首先要明確哪個為空,哪個為非空Queue* emptyQ=&obj->q1;//假設q1為空Queue* nonemptyQ=&obj->q2;//q2不為空if(!QueueEmpty(&obj->q1))//驗證是否正確{//進入則是不正確emptyQ=&obj->q2;//不正確則交換nonemptyQ=&obj->q1;}while(QueueSize(nonemptyQ) > 1)//設置遍歷循環{QueuePush(emptyQ,QueueFront(nonemptyQ));//將非空的前面n-1個挪入空隊列QueuePop(nonemptyQ);//pop掉已經挪入的那n-1個}//剩下的就是要按照棧的特性LIFO順序的數據int top=QueueFront(nonemptyQ);//按照題目要求記錄下數據QueuePop(nonemptyQ);//popreturn top;//返回數據
}
//返回棧頂元素
int myStackTop(MyStack* obj) {if(!QueueEmpty(&obj->q1))//找非空隊列{return QueueBack(&obj->q1);//返回隊尾元素,按照模擬邏輯}//此時隊尾就是棧頂else{return QueueBack(&obj->q2);}
}
//判空
bool myStackEmpty(MyStack* obj) {
//兩個隊列都為空,模擬棧才為空return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}
//銷毀
void myStackFree(MyStack* obj) {QueueDestroy(&obj->q1);//將自己開辟的空間都釋放QueueDestroy(&obj->q2);//否則會有內存泄漏問題free(obj);
}

銷毀邏輯示例圖:

三.用棧實現隊列(leetcode 232)

讓我們先來看看題目:

讓我們來理清楚思路:
我們需要用到兩個棧來實現隊列:

• 一個用來當作入隊棧
• 一個用來當作出隊棧
• 我們還要注意其FIFO的性質,和隨進隨出的特點
  1.我們需要保持一個入隊棧,一個出隊棧
  2.出隊列,把前面的數據導入空棧
  3.當出隊棧不為空時,不能再將出隊棧中的數據導入,否則順序會亂;
  如圖:
  
  讓我們來感受一下代碼:

typedef struct {ST pushst;//入隊棧ST popst;//出隊棧
} MyQueue;int myQueuePeek(MyQueue* obj);//返回隊頭元素的函數聲明;
//動態開辟
MyQueue* myQueueCreate() {MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));if(obj==NULL){perror("malloc fail");return NULL;}STInit(&obj->pushst);//初始化兩個棧STInit(&obj->popst);return obj;//返回模擬隊列
}void myQueuePush(MyQueue* obj, int x) {STPush(&obj->pushst,x);//正常往入隊棧中直接插入
}
//按題目要求,從隊列的開頭移除并返回元素
int myQueuePop(MyQueue* obj) {int front=myQueuePeek(obj);//記錄隊頭元素STPop(&obj->popst);//刪除return front; //返回元素
}int myQueuePeek(MyQueue* obj) {if(STEmpty(&obj->popst))//如果出隊棧為空{while(!STEmpty(&obj->pushst))//開始遍歷循環{//并且入隊棧不為空STPush(&obj->popst,STTop(&obj->pushst));//將全部元素挪過去STPop(&obj->pushst);//在入隊棧中刪除的操作}}return STTop(&obj->popst);//返回棧頂即是隊頭,可以參看上圖;
}
//判空
bool myQueueEmpty(MyQueue* obj) {
//兩個棧都為空,才為空return STEmpty(&obj->pushst) && STEmpty(&obj->popst);
}
//釋放所有動態開辟的空間
void myQueueFree(MyQueue* obj) {STDestroy(&obj->pushst);STDestroy(&obj->popst);free(obj);}

四.設計循環隊列(leetcode 622)

讓我們來看看題目:

我們來理清楚邏輯:
這里我們選擇用數組來實現,鏈表實現也是可以的,但是相對來說,數組實現會更加容易;對于數組是否滿了,我們有兩種解決辦法:

• 在結構體中加入size來計量;
• 空出一個位置來提醒判斷已滿
  讓我們來實戰:

//定義結構體
typedef struct {int* a;//靜態數組int front;//頭int rear;//尾int k;//滿數據時候的個數
} MyCircularQueue;
bool myCircularQueueIsEmpty(MyCircularQueue* obj);//函數聲明,防止編譯錯誤
bool myCircularQueueIsFull(MyCircularQueue* obj);
//開出對應大小的空間
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));if(obj==NULL){perror("malloc fail");return NULL;}obj->a=(int*)malloc(sizeof(int)*(k+1));//多開,防止溢出if(obj->a==NULL){perror("malloc fail");return NULL;}obj->front=obj->rear=0;//指向開頭obj->k=k;return obj;
}
//插入
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))//如果是滿的{return false;//返回false,表示不能再插入了}obj->a[obj->rear++] = value;//否則存儲值,并且rear++到下一個位置;obj->rear %= (obj->k+1);//對尾取模,比如,1%5==1,3%5==3,如果滿了5%5==0//就會循環回到數組開始的下標return true;//返回true,表示還可以插入
}
//刪除
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))//如果是空的{return false;//返回false,表示不能再刪除了}obj->front++;//頭往下一個位置走,這個就與我們曾經講過的順序表里面的刪除一樣的//只要我們不把它計量在有效個數中就可以刪除它obj->front %= (obj->k+1);//對頭取模,比如,1%5==1,3%5==3,如果滿了5%5==0//就會循環回到數組開始的下標return true;//返回true,表示還可以刪除
}
//按題目要求:從隊首獲取元素。如果隊列為空，返回 -1
int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))//若為空{return -1;//返回}return obj->a[obj->front];//返回頭元素
}
//按題目要求:獲取隊尾元素。如果隊列為空，返回 -1 
int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}return obj->a[(obj->rear-1+obj->k+1) % (obj->k+1)];//防止因為rear在下標0的位置--,而發生錯誤;//通過取模,來造成循環;
}
//簡單的判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->rear == obj->front;
}
//判斷滿
bool myCircularQueueIsFull(MyCircularQueue* obj) {//通過取模,來造成循環;return (obj->rear+1) % (obj->k+1) == obj->front;//保證rear的下一個是頭
}
//釋放,相同與前兩題,可以自行畫圖理解;
void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}

以上就是我要講的所有的經典問題,你學會了嗎?

---

五.總結

在本次博客中，我們圍繞棧和隊列這兩種基礎數據結構，通過C語言實現經典算法問題，深入探索了它們的底層原理與應用技巧。

• 首先是“有效的括號”問題，利用棧來匹配括號，左括號入棧，右括號與棧頂元素匹配，這種方式充分展現了棧“后進先出”（LIFO）的特性，在處理具有成對結構的數據時十分有效 ，能夠清晰地判斷括號是否匹配，避免邏輯混亂。
• 接著，在“用隊列實現棧”和“用棧實現隊列”的問題中，分別運用兩個隊列和兩個棧來模擬對方的特性。用隊列實現棧時，通過在兩個隊列間來回轉移數據，確保滿足棧的LIFO性質；用棧實現隊列則是利用兩個棧，在入隊棧和出隊棧間合理轉移數據，保證隊列“先進先出”（FIFO）的特性。這兩個問題不僅鍛煉了對數據結構特性的靈活運用，還讓我們深入理解了不同數據結構間的轉換和模擬方法。
• 最后，在“設計循環隊列”中，使用數組實現循環隊列，通過巧妙的取模操作實現隊列的循環，同時提供了判空和判滿的方法。這種實現方式既高效又簡潔，充分利用了數組的連續性和可索引性，加深了我們對隊列數據結構的理解和應用能力。

通過解決這些經典算法問題，我們不僅掌握了棧和隊列在實際編程中的應用，還提升了算法設計、邏輯思維以及內存管理的能力。希望讀者能夠通過不斷練習，熟練掌握這些知識，在后續的編程學習和實踐中更加得心應手，靈活運用棧和隊列解決各種復雜的實際問題，為更深入的算法學習和系統開發打下堅實的基礎。