??write in front??
??所屬專欄：初階數(shù)據(jù)結(jié)構(gòu)
???博客主頁：睿睿的博客主頁
???代碼倉庫：??VS2022_C語言倉庫
??您的點贊、關(guān)注、收藏、評論，是對我最大的激勵和支持?。?！
關(guān)注我，關(guān)注我，關(guān)注我，你們將會看到更多的優(yōu)質(zhì)內(nèi)容?。?/p>
前言
例題1：循環(huán)隊列
??棧兩種線性表示都能實現(xiàn)，隊列呢？隊列適合使用鏈表實現(xiàn)，使用順序結(jié)構(gòu)(即固定的連續(xù)空間)實現(xiàn)時會出現(xiàn)假溢出的問題，因此大佬們設(shè)計出了循環(huán)隊列，循環(huán)隊列就是為了解決順序結(jié)構(gòu)實現(xiàn)隊列假溢出問題的現(xiàn)在我們來看看用順序表實現(xiàn)隊列：
因為隊列長度有限，所以我們要及時的判斷什么時候隊列滿了。那么怎么判斷隊列是否滿了呢？
如果我們通過隊尾和隊頂是否相等來判斷是否填滿就會發(fā)現(xiàn)，在隊列空的時候，隊尾也等于對隊頂。所以我們不能通過這種方法來判斷：
那么我們該如何解決呢？
方法1：
加一個size來計數(shù)
方法2：
多添加一個位置：
空的情況：
滿的情況：
下面我們就以方法2來實現(xiàn)代碼：
typedef struct
{
int *a;
int front;
int rear;
int k;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k)
{
MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->a=(int*)malloc(sizeof(int)*(k+1));
obj->k=k;
obj->front=obj->rear=0;
return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
return obj->rear==obj->front;
}
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->k+1);
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;
return obj->a[obj->front];
}
int myCircularQueueRear(MyCircularQueue* obj)
{
if(myCircularQueueIsEmpty(obj))
return -1;
return obj->a[(obj->rear-1+obj->k+1)%(obj->k+1)];
}
void myCircularQueueFree(MyCircularQueue* obj)
{
free(obj->a);
free(obj);
}
這里我們只要關(guān)注這幾點，其他的都很好實現(xiàn)：
空的情況：
滿的情況：
??在這里我們學(xué)到了如何在數(shù)組里建立循環(huán)！那就是通過mod數(shù)組的長度，就可以使數(shù)組循環(huán)起來！
找隊尾：
??尾部其實就是rear的后面一個元素，即rear-1，但是當(dāng)rear等于0的時候，-1就會導(dǎo)致越界。對一個正數(shù)加a模a，得到的值不變。對于rear=0的時候進(jìn)行這個操作就會避免越界的情況。
例題2：用隊列實現(xiàn)棧
??要通過隊列表示棧就要熟知他們兩個各自的性質(zhì)。棧是有“先進(jìn)后出”的特點，隊列有“先進(jìn)先出的特點”，綜合她兩的特點，我們通過以下方法來實現(xiàn)數(shù)據(jù)的出入：
- 保持一個隊列為空，一個隊列存數(shù)據(jù)
- 出棧的時候把前面的數(shù)據(jù)導(dǎo)入空隊列，將最后一個數(shù)據(jù)pop出去。
具體實現(xiàn)：（隊列的代碼之前寫過，就不展示了，詳細(xì)：棧與隊列）
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDatatype x);
void QueuePop(Queue* pq);
int QueueSize(Queue* pq);
bool QueueEmpty(Queue* pq);
QDatatype QueueFront(Queue* pq);
QDatatype QueueBack(Queue* pq);
typedef int QDatatype;
typedef struct QueueNode
{
struct QueueNode* next;
QDatatype data;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail;
int size;
}Queue;
typedef struct
{
Queue q1;
Queue q2;
} MyStack;
MyStack* myStackCreate()
{
MyStack*ptr=(MyStack*)malloc(sizeof(MyStack));
if(ptr==NULL)
{
perror("malloc::fail");
return 0;
}
QueueInit(&ptr->q1);
QueueInit(&ptr->q2);
return ptr;
}
void myStackPush(MyStack* obj, int x)
{
if(!QueueEmpty(&obj->q1))
{
QueuePush(&obj->q1,x);
}
else
{
QueuePush(&obj->q2,x);
}
}
int myStackPop(MyStack* obj)
{
Queue*emptyQ=&obj->q1;
Queue *noneQ=&obj->q2;
if(!QueueEmpty(emptyQ))
{
emptyQ=&obj->q2;
noneQ=&obj->q1;
}
while(QueueSize(noneQ)>1)
{
QueuePush(emptyQ,QueueFront(noneQ));
QueuePop(noneQ);
}
int top=QueueBack(noneQ);
QueuePop(noneQ);
return top;
}
int myStackTop(MyStack* obj)
{
if(!QueueEmpty(&obj->q1))
{
return QueueBack(&obj->q1);
}
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);
}
例題3：用棧實現(xiàn)隊列
將一個棧當(dāng)作輸入棧，用于壓入 push傳入的數(shù)據(jù)；另一個棧當(dāng)作輸出棧，用于 pop 和peek 操作。
每次 pop 或 peek時，若輸出棧為空則將輸入棧的全部數(shù)據(jù)依次彈出并壓入輸出棧，這樣輸出棧從棧頂往棧底的順序就是隊列從隊首往隊尾的順序。
具體代碼實現(xiàn)：
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top; // 棧頂
int capacity; // 容量
}Stack;
// 初始化棧
void StackInit(Stack* ps);
// 入棧
void StackPush(Stack* ps, STDataType data);
// 出棧
void StackPop(Stack* ps);
// 獲取棧頂元素
STDataType StackTop(Stack* ps);
// 獲取棧中有效元素個數(shù)
int StackSize(Stack* ps);
// 檢測棧是否為空，如果為空返回非零結(jié)果，如果不為空返回0
bool empty(Stack* ps);
// 銷毀棧
void StackDestroy(Stack* ps);
typedef struct
{
Stack pushST;
Stack popST;
} MyQueue;
int myQueuePeek(MyQueue* obj) ;
MyQueue* myQueueCreate()
{
MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue));
if(obj==NULL)
{
perror("malloc::fail");
return 0;
}
StackInit(&obj->pushST);
StackInit(&obj->popST);
return obj;
}
void myQueuePush(MyQueue* obj, int x)
{
assert(obj);
StackPush(&obj->pushST,x);
}
int myQueuePop(MyQueue* obj)
{
int top=myQueuePeek(obj);
StackPop(&obj->popST);
return top;
}
int myQueuePeek(MyQueue* obj)
{
if(empty(&obj->popST))
{
while(!empty(&obj->pushST))
{
StackPush(&obj->popST,StackTop(&obj->pushST));
StackPop(&obj->pushST);
}
}
return StackTop(&obj->popST);
}
bool myQueueEmpty(MyQueue* obj)
{
return empty(&obj->pushST)&&empty(&obj->popST);
}
void myQueueFree(MyQueue* obj) {
StackDestroy(&obj->pushST);
StackDestroy(&obj->popST);
free(obj);
}
例題4：括號匹配問題
我們遍歷給定的字符串 s。當(dāng)我們遇到一個左括號時，我們會期望在后續(xù)的遍歷中，有一個相同類型的右括號將其閉合。由于后遇到的左括號要先閉合，因此我們可以將這個左括號放入棧頂。
當(dāng)我們遇到一個右括號時，我們需要將一個相同類型的左括號閉合。此時，我們可以取出棧頂?shù)淖罄ㄌ柌⑴袛嗨鼈兪欠袷窍嗤愋偷睦ㄌ枴?strong>如果不是相同的類型，或者棧中并沒有左括號，那么字符串 s 無效，返回 False。
在遍歷結(jié)束后，如果棧中沒有左括號，說明我們將字符串 s中的所有左括號閉合，返回 True，否則返回 False。
注意到有效字符串的長度一定為偶數(shù)，因此如果字符串的長度為奇數(shù)，我們可以直接返回 False ，省去后續(xù)的遍歷判斷過程。
完整代碼：
總結(jié)
??這就是棧和隊列的相關(guān)oj題，你學(xué)會了嗎？
??更新不易，辛苦各位小伙伴們動動小手，??三連走一走???? ~ ~ ~ 你們真的對我很重要！最后，本文仍有許多不足之處，歡迎各位認(rèn)真讀完文章的小伙伴們隨時私信交流、批評指正！
專欄訂閱：
每日一題
c語言學(xué)習(xí)
算法
智力題
初階數(shù)據(jù)結(jié)構(gòu)
更新不易，辛苦各位小伙伴們動動小手，??三連走一走???? ~ ~ ~ 你們真的對我很重要！最后，本文仍有許多不足之處，歡迎各位認(rèn)真讀完文章的小伙伴們隨時私信交流、批評指正！文章來源：http://www.zghlxwxcb.cn/news/detail-435854.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-435854.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】棧與隊列經(jīng)典oj題的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
