W...Y的主頁???
代碼庫(kù)分享???
在之前的博客中，我們學(xué)習(xí)了棧與隊(duì)列的基本內(nèi)容，并且實(shí)現(xiàn)了棧與隊(duì)列。今天我們進(jìn)行刷題訓(xùn)練，走進(jìn)棧與隊(duì)列的世界中去感受一番?。?！
目錄
括號(hào)匹配問題
?使用隊(duì)列實(shí)現(xiàn)棧
用棧實(shí)現(xiàn)隊(duì)列
設(shè)計(jì)循環(huán)隊(duì)列
括號(hào)匹配問題
給定一個(gè)只包括?
'('，')'，'{'，'}'，'['，']'?的字符串?s?，判斷字符串是否有效。有效字符串需滿足：
- 左括號(hào)必須用相同類型的右括號(hào)閉合。
- 左括號(hào)必須以正確的順序閉合。
- 每個(gè)右括號(hào)都有一個(gè)對(duì)應(yīng)的相同類型的左括號(hào)。
OJ鏈接?【leetcode 20.有效的括號(hào)】
這道題我們先做分析：滿足的三大條件總結(jié)：類型匹配、順序匹配、數(shù)量匹配。要滿足這三個(gè)條件才可以返回true，反之則返回false。
最左邊的括號(hào)要與最右邊的括號(hào)進(jìn)行匹配，這里我們就可以使用棧先進(jìn)后出的特性來完成。當(dāng)我們遇到一個(gè)左括號(hào)時(shí)，讓其進(jìn)棧進(jìn)行儲(chǔ)存。反之遇到右括號(hào)時(shí)，讓棧中元素進(jìn)行出棧進(jìn)行匹配。?
#include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef char STDataType; typedef struct Stack { STDataType* a; int top; int capacity; }ST; void STInit(ST* ps); void STDestroy(ST* ps); void STPush(ST* ps, STDataType x); void STPop(ST* ps); int STSize(ST* ps); bool STEmpty(ST* ps); STDataType STTop(ST* ps); void STInit(ST* ps) { assert(ps); ps->a = NULL; ps->capacity = 0; ps->top = 0; } void STDestroy(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = ps->capacity = 0; } void STPush(ST* ps, STDataType x) { assert(ps); if (ps->top == ps->capacity) { int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity); if (tmp == NULL) { perror("realloc"); exit(-1); } ps->a = tmp; ps->capacity = newCapacity; } ps->a[ps->top] = x; ps->top++; } void STPop(ST* ps) { assert(ps); assert(ps->top > 0); --ps->top; } int STSize(ST* ps) { assert(ps); return ps->top; } bool STEmpty(ST* ps) { assert(ps); return ps->top == 0; } STDataType STTop(ST* ps) { assert(ps); assert(ps->top > 0); return ps->a[ps->top - 1]; } bool isValid(char * s){ ST st; STInit(&st); char topval; while(*s) { if(*s == '('||*s == '['||*s == '{') { STPush(&st, *s); } else { if(STEmpty(&st)) { STDestroy(&st); return false; } topval = STTop(&st); STPop(&st); if((*s == ']' && topval != '[') || (*s == ')' && topval != '(') || (*s == '}' && topval != '{')) { STDestroy(&st); return false; } } s++; } bool ret = STEmpty(&st); STDestroy(&st); return ret; }leetcode這道題中，對(duì)C語言非常不友好，如果想使用棧數(shù)據(jù)結(jié)構(gòu)就必須自己寫接口，我們可以使用博主之前博客中實(shí)現(xiàn)棧的接口復(fù)制粘貼上即可完成。
bool ret = STEmpty(&st);
? ? STDestroy(&st);
? ? return ret;最后三句代碼，是為了驗(yàn)證括號(hào)數(shù)量匹配的問題，如果循環(huán)完成后棧中還有括號(hào)元素，證明示例中左右括號(hào)不匹配數(shù)量有問題，必須返回false。
?使用隊(duì)列實(shí)現(xiàn)棧
請(qǐng)你僅使用兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)后入先出（LIFO）的棧，并支持普通棧的全部四種操作（
push、top、pop?和?empty）。實(shí)現(xiàn)?
MyStack?類：
void push(int x)?將元素 x 壓入棧頂。int pop()?移除并返回棧頂元素。int top()?返回棧頂元素。boolean empty()?如果棧是空的，返回?true?；否則，返回?false?。注意：
- 你只能使用隊(duì)列的基本操作 —— 也就是?
push to back、peek/pop from front、size?和?is empty?這些操作。- 你所使用的語言也許不支持隊(duì)列。?你可以使用 list （列表）或者 deque（雙端隊(duì)列）來模擬一個(gè)隊(duì)列?, 只要是標(biāo)準(zhǔn)的隊(duì)列操作即可。
OJ鏈接?【leetcode255.用隊(duì)列實(shí)現(xiàn)?！?/p>
分析：
錯(cuò)誤想法：假設(shè)第一個(gè)隊(duì)列中有四個(gè)數(shù)據(jù)1、2、3、4，隊(duì)列的特點(diǎn)是先進(jìn)先出。我們一般的想法為把內(nèi)容反轉(zhuǎn)一下，再先進(jìn)先出即可。但是這個(gè)想法是錯(cuò)誤的，當(dāng)我們反轉(zhuǎn)后取出4后假設(shè)再push加入5和6兩個(gè)數(shù)據(jù)。前面的數(shù)據(jù)會(huì)如同棧一樣后進(jìn)先出，但是到5和6時(shí)又會(huì)成為隊(duì)列出5和6。所以這個(gè)方法是不可行的。
正確想法：
當(dāng)我們?nèi)绻鹥op釋放完4后繼續(xù)想再次push錄入數(shù)據(jù)，我們應(yīng)該錄入到哪里？
我們應(yīng)該錄入到不為空的隊(duì)列中，然后繼續(xù)進(jìn)行上面的操作即可完成使用隊(duì)列實(shí)現(xiàn)棧的特性
?總結(jié)：不為空的隊(duì)列進(jìn)行存入數(shù)據(jù)，為空的隊(duì)列進(jìn)行導(dǎo)入數(shù)據(jù)?。?！
實(shí)現(xiàn)如下：
#include<stdio.h> #include<stdlib.h> #include<assert.h> #include<string.h> #include<stdbool.h> typedef int QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType data; }QNode; typedef struct Queue { QNode* head; QNode* tail; int size; }Que; void QueueInit(Que* pq); void QueueDestroy(Que* pq); void QueuePush(Que* pq, QDataType x); void QueuePop(Que* pq); QDataType QueueFront(Que* pq); QDataType QueueBack(Que* pq); bool QueueEmpty(Que* pq); int QueueSize(Que* pq); void QueueInit(Que* pq) { pq->head = pq->tail = NULL; pq->size = 0; } void QueueDestroy(Que* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->head = pq->tail = NULL; pq->size = 0; } int QueueSize(Que* pq) { assert(pq); return pq->size; } void QueuePush(Que* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc"); exit(-1); } newnode->data = x; newnode->next = NULL; if (pq->tail == NULL) { pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = newnode; } pq->size++; } void QueuePop(Que* pq) { assert(pq); assert(!QueueEmpty(pq)); if (pq->head->next == NULL) { free(pq->head); pq->head = pq->tail = NULL; } else { QNode* next = pq->head->next; free(pq->head); pq->head = next; } pq->size--; } QDataType QueueFront(Que* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->head->data; } QDataType QueueBack(Que* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->tail->data; } bool QueueEmpty(Que* pq) { assert(pq); return pq->tail == NULL; } typedef struct { Que q1; Que q2; } MyStack; MyStack* myStackCreate() { MyStack* pst = (MyStack*)malloc(sizeof(MyStack)); QueueInit(&pst->q1); QueueInit(&pst->q2); return pst; } void myStackPush(MyStack* obj, int x) { if(!QueueEmpty(&obj->q1)) { QueuePush(&obj->q1, x); } else { QueuePush(&obj->q2, x); } } int myStackPop(MyStack* obj) { Que* empty = &obj->q1; Que* noempty = &obj->q2; if(!QueueEmpty(&obj->q1)) { noempty = &obj->q1; empty = &obj->q2; } //前size-1個(gè)空隊(duì)列 while(QueueSize(noempty)>1) { QueuePush(empty,QueueFront(noempty)); QueuePop(noempty); } int top = QueueFront(noempty); QueuePop(noempty); return 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); } /** * Your MyStack struct will be instantiated and called as such: * MyStack* obj = myStackCreate(); * myStackPush(obj, x); * int param_2 = myStackPop(obj); * int param_3 = myStackTop(obj); * bool param_4 = myStackEmpty(obj); * myStackFree(obj); */這道題C語言也沒有任何鏈表接口，我們得去寫完整。但是這些類型的題目都是低耦合的，只要接口不變，內(nèi)容怎么改變都無所謂，我們繼續(xù)復(fù)制粘貼隊(duì)列的實(shí)現(xiàn)。
但是這這題需要兩個(gè)隊(duì)列，所以嵌套關(guān)系比較復(fù)雜，下面提供一張關(guān)系圖片進(jìn)行參考：
用棧實(shí)現(xiàn)隊(duì)列
請(qǐng)你僅使用兩個(gè)棧實(shí)現(xiàn)先入先出隊(duì)列。隊(duì)列應(yīng)當(dāng)支持一般隊(duì)列支持的所有操作（、、、）：
pushpoppeekempty實(shí)現(xiàn)?類：
MyQueue
void push(int x)將元素 x 推到隊(duì)列的末尾int pop()從隊(duì)列的開頭移除并返回元素int peek()返回隊(duì)列開頭的元素boolean empty()如果隊(duì)列為空，返回 ；否則，返回truefalse說明：
- 你?只能?使用標(biāo)準(zhǔn)的棧操作 —— 也就是只有?,?,?, 和??操作是合法的。
push to toppeek/pop from topsizeis empty- 你所使用的語言也許不支持棧。你可以使用 list 或者 deque（雙端隊(duì)列）來模擬一個(gè)棧，只要是標(biāo)準(zhǔn)的棧操作即可。
OJ鏈接?【leetcode232.用棧實(shí)現(xiàn)隊(duì)列】
分析：用兩個(gè)棧實(shí)現(xiàn)隊(duì)列先進(jìn)先出的特點(diǎn)。
與用隊(duì)列實(shí)現(xiàn)棧相似，但有所不同的是將push添加的數(shù)據(jù)從一個(gè)棧中轉(zhuǎn)入另一個(gè)棧（遵循后進(jìn)先出原則）就成為逆序，所以當(dāng)想要pop時(shí)，只需將存入數(shù)據(jù)的棧中元素轉(zhuǎn)入到空棧中去，進(jìn)行依次釋放即可。
當(dāng)未釋放完卻想要繼續(xù)pop添加元素時(shí)，我們添加到最開始增加元素的棧中去等待另一個(gè)棧中元素全部pop完后繼續(xù)進(jìn)行上述方法，將添加新元素的棧中元素按照棧先進(jìn)后出原則轉(zhuǎn)入另一個(gè)棧進(jìn)行釋放即可。
?
總結(jié)：將兩個(gè)棧分別看作pushst（添加棧）popst（釋放棧）。如果想要添加元素就放入pushst中去，想要釋放元素先要將pushst中的元素放入popst中去，再進(jìn)行釋放。
注意：如果中途有push添加元素，只有將popst中的元素釋放為空后才可以繼續(xù)從pushst中給予元素給popst繼續(xù)釋放?。?！
#include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int STDataType; typedef struct Stack { STDataType* a; int top; int capacity; }ST; void STInit(ST* ps); void STDestroy(ST* ps); void STPush(ST* ps, STDataType x); void STPop(ST* ps); int STSize(ST* ps); bool STEmpty(ST* ps); STDataType STTop(ST* ps); void STInit(ST* ps) { assert(ps); ps->a = NULL; ps->capacity = 0; ps->top = 0; } void STDestroy(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = ps->capacity = 0; } void STPush(ST* ps, STDataType x) { assert(ps); if (ps->top == ps->capacity) { int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity); if (tmp == NULL) { perror("realloc"); exit(-1); } ps->a = tmp; ps->capacity = newCapacity; } ps->a[ps->top] = x; ps->top++; } void STPop(ST* ps) { assert(ps); assert(ps->top > 0); --ps->top; } int STSize(ST* ps) { assert(ps); return ps->top; } bool STEmpty(ST* ps) { assert(ps); return ps->top == 0; } STDataType STTop(ST* ps) { assert(ps); assert(ps->top > 0); return ps->a[ps->top - 1]; } typedef struct { ST pushst; ST popst; } MyQueue; MyQueue* myQueueCreate() { MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue)); STInit(&obj->pushst); STInit(&obj->popst); return obj; } void myQueuePush(MyQueue* obj, int x) { STPush(&obj->pushst, x); } 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); } int myQueuePop(MyQueue* obj) { int front = myQueuePeek(obj); STPop(&obj->popst); return front; } bool myQueueEmpty(MyQueue* obj) { return STEmpty(&obj->pushst) && STEmpty(&obj->popst); } void myQueueFree(MyQueue* obj) { STDestroy(&obj->pushst); STDestroy(&obj->popst); free(obj); } /** * Your MyQueue struct will be instantiated and called as such: * MyQueue* obj = myQueueCreate(); * myQueuePush(obj, x); * int param_2 = myQueuePop(obj); * int param_3 = myQueuePeek(obj); * bool param_4 = myQueueEmpty(obj); * myQueueFree(obj); */此題依舊沒有接口，需要我們自己添加完成，但是相同的方法我們就不再過多強(qiáng)調(diào)，題不是很難，但是層層嵌套還是比較繞的。
設(shè)計(jì)循環(huán)隊(duì)列
設(shè)計(jì)你的循環(huán)隊(duì)列實(shí)現(xiàn)。循環(huán)隊(duì)列是一種線性數(shù)據(jù)結(jié)構(gòu)，其操作表現(xiàn)基于 FIFO（先進(jìn)先出）原則并且隊(duì)尾被連接在隊(duì)首之后以形成一個(gè)循環(huán)。它也被稱為"環(huán)形緩沖器"。
循環(huán)隊(duì)列的一個(gè)好處是我們可以利用這個(gè)隊(duì)列之前用過的空間。在一個(gè)普通隊(duì)列里，一旦一個(gè)隊(duì)列滿了，我們就不能插入下一個(gè)元素，即使在隊(duì)列前面仍有空間。但是使用循環(huán)隊(duì)列，我們能使用這些空間去存儲(chǔ)新的值。
你的實(shí)現(xiàn)應(yīng)該支持如下操作：
MyCircularQueue(k)： 構(gòu)造器，設(shè)置隊(duì)列長(zhǎng)度為 k 。Front: 從隊(duì)首獲取元素。如果隊(duì)列為空，返回 -1 。Rear: 獲取隊(duì)尾元素。如果隊(duì)列為空，返回 -1 。enQueue(value): 向循環(huán)隊(duì)列插入一個(gè)元素。如果成功插入則返回真。deQueue(): 從循環(huán)隊(duì)列中刪除一個(gè)元素。如果成功刪除則返回真。isEmpty(): 檢查循環(huán)隊(duì)列是否為空。isFull(): 檢查循環(huán)隊(duì)列是否已滿。
?
提示：
- 所有的值都在 0?至 1000 的范圍內(nèi)；
- 操作數(shù)將在 1 至 1000 的范圍內(nèi)；
- 請(qǐng)不要使用內(nèi)置的隊(duì)列庫(kù)。
????????OJ鏈表?【leetcode 622.設(shè)計(jì)循環(huán)隊(duì)列】
那我們用數(shù)組還是用鏈表來實(shí)現(xiàn)循環(huán)隊(duì)列好呢？?
無論使用鏈表還是數(shù)組，當(dāng)內(nèi)容為空時(shí)兩個(gè)指針指向的位置都在最開始，而每增加一個(gè)數(shù)據(jù)Rear都往后走一個(gè)位置（Rear指向的是最后一個(gè)內(nèi)容的下一個(gè)節(jié)點(diǎn)處），所以當(dāng)我們?nèi)?duì)尾數(shù)據(jù)時(shí)，假設(shè)使用鏈表就非常的不好尋找（除非使用雙向鏈表或者別的方法進(jìn)行標(biāo)記），但是數(shù)組卻非常好尋找隊(duì)尾的元素內(nèi)容。所以我們使用數(shù)組來實(shí)現(xiàn)循環(huán)列表。（但是鏈表非常好進(jìn)行循環(huán)找頭）各有利弊?。?！
第二個(gè)問題：當(dāng)循環(huán)隊(duì)列為空和全滿時(shí)，Rear指針與Front指針全部指向同一個(gè)位置，我們應(yīng)該如何區(qū)分？?
解法一：我們可以設(shè)置一個(gè)size來記錄數(shù)據(jù)個(gè)數(shù)。
解法二：我們可以在設(shè)置數(shù)組大小時(shí)多開一個(gè)空間不去使用 front == Rear 就是空，Rear的下一個(gè)為Front即為滿。
?
使用數(shù)組時(shí)，我們需要注意當(dāng)rear指向最后一個(gè)時(shí)，在循環(huán)隊(duì)列前面還有空余的情況下，如何讓rear指針回到最初呢？
方法一：我們可以使用if判斷，如果rear指向最后時(shí)，我們可以讓其直接等于0.
方法二：比較巧妙，我們可以用?obj->rear?%= (obj->k+1);進(jìn)行操作。
同理front方法一樣。
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->front = obj->rear = 0; obj->k = k; return obj; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->front == obj->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); 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 { return obj->a[(obj->rear + obj->k) % (obj->k + 1)]; } } void myCircularQueueFree(MyCircularQueue* obj) { free(obj->a); free(obj); } /** * Your MyCircularQueue struct will be instantiated and called as such: * MyCircularQueue* obj = myCircularQueueCreate(k); * bool param_1 = myCircularQueueEnQueue(obj, value); * bool param_2 = myCircularQueueDeQueue(obj); * int param_3 = myCircularQueueFront(obj); * int param_4 = myCircularQueueRear(obj); * bool param_5 = myCircularQueueIsEmpty(obj); * bool param_6 = myCircularQueueIsFull(obj); * myCircularQueueFree(obj); */在函數(shù)myCircularQueueRear中，我們需要得到rear前一個(gè)的數(shù)組內(nèi)容。一般情況都非常好表示，但有一種情況需要我們?nèi)≌遄谩?img src="https://imgs.yssmx.com/Uploads/2023/08/684308-16.png" alt="萬字精講——數(shù)據(jù)結(jié)構(gòu)棧與隊(duì)列必會(huì)OJ練習(xí),算法,開發(fā)語言,c語言,數(shù)據(jù)結(jié)構(gòu)" referrerpolicy="no-referrer" />
當(dāng)rear已經(jīng)指向第一個(gè)時(shí)，怎樣才能返回元素4呢？
方法一：當(dāng)rear為0時(shí)，我們直接可以讓其返回k下標(biāo)的內(nèi)容。（比較低級(jí)）
方法二：?return obj->a[(obj->rear + obj->k) % (obj->k + 1)];我們可以使用算數(shù)巧妙地表示最后末尾地元素。
這道題的特殊情況比較多情況比較復(fù)雜，寫代碼時(shí)我們應(yīng)該將問題考慮周全?。。?/strong>文章來源：http://www.zghlxwxcb.cn/news/detail-684308.html
以上是本次OJ題目分享全部?jī)?nèi)容，感謝大家觀看，一鍵三連是對(duì)博主最大的支持?。?！謝謝???文章來源地址http://www.zghlxwxcb.cn/news/detail-684308.html
到了這里，關(guān)于萬字精講——數(shù)據(jù)結(jié)構(gòu)棧與隊(duì)列必會(huì)OJ練習(xí)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
