LeetCode刷題記錄

• 🌐 我的博客主頁：iiiiiankor
• 🎯 如果你覺得我的內容對你有幫助，不妨點個贊👍、留個評論?，或者收藏?，讓我們一起進步！
• 📝 專欄系列：LeetCode 刷題日志
• 🌱 文章內容來自我的學習與實踐經驗，如果你有任何想法或問題，歡迎隨時在評論區交流討論。讓我們一起探索更多的可能！🚀

---

?前言?

首先我們可以先復習一下相關性質：

• 棧：

棧：一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操作。進行數據插入和刪除操作的一端稱為棧頂，另一端稱為棧底。
棧中的數據元素遵守后進先出LIFO（Last In First Out）的原則。
壓棧：棧的插入操作叫做進棧/壓棧/入棧，入數據在棧頂。
出棧：棧的刪除操作叫做出棧。出數據也在棧頂
實現方法：1. 數組（順序表） 2.鏈表

• 隊列

隊列：只允許在一端進行插入數據操作，在另一端進行刪除數據操作的特殊線性表，隊列具有先進先出FIFO(First In First Out)
入隊列：進行插入操作的一端稱為隊尾
出隊列：進行刪除操作的一端稱為隊頭
實現：1.鏈表（更優）2.數組（較差）

??注意??

C語言中并不想C++或者Java等高級語言那樣，庫中有封裝好的棧和隊列
所以我們用C做這些題的時候，都必須先把棧或者隊列寫出來，才能做題！
這也是用C刷題的很惡心的地方
但是 也能鞏固我們的知識不是嘛？

🚀LeetCode225.用隊列實現棧

鏈接：LeetCode225.用隊列實現棧

一、🌟題目描述🌟

二、🎨分析🎨

我們知道，隊列是先進先出，而棧是后進先出，那么怎么用隊列實現棧呢？
我們通過畫圖來分析：

如果給你一個不為空的隊列，我們叫他noempty：

這個隊列是 按照 1 2 3 4 的順序放入的數據
所以 如果是隊列的話 那么出隊列的順序也是 1 2 3 4
但是如果想要實現棧，那么第一個出去的數據應該是4
我們怎么實現呢？
如果我們還有一個空的隊列，我們叫他empty
我們把1 2 3 放到empty里面，那么noempty里就只剩下了 4，如圖：

這樣，noempty的隊頭就是4 我們直接對noempty進行pop
然后 隊列的性質是先進先出，所以在empty中也是 原來的1 2 3順序
empty出隊列的順序也是1 2 3
所以 我們只需要把empty中的元素再倒回noempty中
我們再觀察noempty，是不是就完成了棧的后進先出的性質！！！
(因為 4 是最后進入的）

綜上所述，其實empty就是用來倒數據的！
因此我們要時刻保證一個是空隊列，另一個是非空隊列
這道題目實際上就是利用一個空隊列和隊列的相關性質，來實現棧的 后進先出的！

三、💥題解💥

棧"的結構定義

這里的“棧” 是我們目標實現的那個棧

• 結構需要包含兩個隊列

  注意： 此類型題目的結構比較復雜
  因為我們使用鏈表實現的棧，所以“棧”中包含的隊列的結構中還有

• 鏈表頭節點

• 鏈表尾節點

“棧”的結構

//這里是匿名結構體 因為有typedef 后面可以使用匿名結構體
typedef struct {//結構中包含兩個隊列Queue q1;Queue q2;
} MyStack;

隊列的結構：

typedef struct Queue {size_t size;//利用一個變量去標識隊列的大小QNode* head;//隊列的頭節點QNode* tail;//隊列的尾節點
}Queue;

Push接口

由于我們需要保持一個隊列為空，另一個隊列不為空
對于push接口，我們只需要判斷哪一個隊列不為空
然后向該隊列push數據就可以了

Pop接口

如果要pop數據，如1 2 3 4 5
模擬實現棧，所以要出棧，也就是刪除棧頂
而棧頂就是隊列的隊尾
所以要刪除5
只需要把前面一個個數據挪動到空隊列
直接讓5出隊就可以了

注意這里題目讓你返回pop掉的元素！

獲取棧頂元素

顯示棧頂元素
只需要找到不為空的隊列就可以了
這里我們不需要考慮如果兩個隊列都為空了怎么辦
只要完成他給的接口就可以了！
測試用例一定是正確合理的！ 不會出現空了還讓你調用這個函數的情況
： 測試用例就是看你邏輯正不正確！

判斷棧是否為空

因為我們的棧是用兩個隊列來實現的
所以 如果兩個隊列都為空，那么說明棧為空！

釋放free

1. 首先把結構中包含的兩個隊列釋放掉
2. 然后把該結構釋放掉

??總代碼??

// 用隊列實現棧typedef int QDataType;
//定義隊列節點的結構  
typedef struct QueueNode {struct QueueNode* next;QDataType val;//隊列中的數據
}QNode;//利用封裝一個結構
typedef struct Queue {size_t size;//利用一個變量去標識隊列的大小QNode* head;//隊列的頭節點QNode* tail;//隊列的尾節點
}Queue;//初始化
void QueueInit(Queue* pq);
//入隊列
void QueuePush(Queue* pq, QDataType x);
//出隊列
void QueuePop(Queue* pq);
//獲取隊頭元素
QDataType QueueFront(Queue* pq);
//獲取隊尾元素
QDataType QueueBack(Queue* pq);
//獲取隊列中元素個數
int QueueSize(Queue* pq);
//檢測隊列是否為空
bool QueueEmpty(Queue* pq);
//銷毀隊列
void QueueDestory(Queue* pq);//初始化
void QueueInit(Queue* pq)
{assert(pq);//頭節點和尾節點都設置為空即可pq->head = pq->tail = NULL;pq->size = 0;}
//入隊列
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){printf("malloc fail!");exit(-1);}newnode->next = NULL;newnode->val = x;//如果隊列為空if (pq->tail == NULL)//也可以使用head==NULL{pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;//更新尾部}pq->size++;
}
//出隊列
void QueuePop(Queue* pq)
{assert(pq);//如果只有一個節點if (pq->head->next == NULL)//這里需要用head的next{free(pq->head);pq->head = pq->tail = NULL;pq->size--;//隊列元素個數減一}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;pq->size--;}
}
//獲取隊頭元素
QDataType QueueFront(Queue* pq)
{assert(pq);//如果隊列為空 無法獲取！assert(!QueueEmpty(pq));return pq->head->val;
}
//獲取隊尾元素
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->val;
}
//獲取隊列中元素個數
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}
//檢測隊列是否為空
bool QueueEmpty(Queue* pq)
{assert(pq);//如果 head為空 返回真 否則返回假return pq->head == NULL;
}
//銷毀隊列
void QueueDestory(Queue* 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;
}/*****************************************/
/*  題解代碼   */
typedef struct {//結構中包含兩個隊列Queue q1;Queue q2;
} MyStack;//初始化
MyStack* myStackCreate() {//首先需要開辟一個stackMyStack* obj = (MyStack*)malloc(sizeof(MyStack));//然后對開辟的Mystack中的q1和q2初始化QueueInit(&obj->q1);QueueInit(&obj->q2);//然后需要返回objreturn obj;
}void myStackPush(MyStack* obj, int x) {//如果q1不為空 那么就向q1里面插入數據if (!QueueEmpty(&obj->q1)){QueuePush(&obj->q1, x);}else//否則就向q2里面插入數據{QueuePush(&obj->q2, x);}
}int myStackPop(MyStack* obj) {//首先需要判斷哪一個不為空//先假設q1為空 q2不為空Queue* empty = &obj->q1;Queue* noempty = &obj->q2;//如果假設錯了 就改一下if (!QueueEmpty(&obj->q1)){empty = &obj->q2;noempty = &obj->q1;}//然后就把非空隊列的數據導入到空隊列 知道非空隊列還有一個數據while (QueueSize(noempty) > 1){//把非空隊列的隊頭 push到空隊列QueuePush(empty, QueueFront(noempty));QueuePop(noempty);}//因為對于棧頂元素需要返回和刪除//所以先把棧頂元素記錄一下啊int top = QueueFront(noempty);QueuePop(noempty);return top;
}int myStackTop(MyStack* obj) {//既然是顯示棧頂元素//那就需要找到非空隊列//顯示非空隊列的隊尾就可以了//如果隊列q1不為空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) {//1. 釋放Mystackj里面包含的q1 和 q2 （他們里面也有malloc的節點）//2. 釋放 MystackQueueDestory(&obj->q1);QueueDestory(&obj->q2);free(obj);
}

🚀LeetCode232.用棧實現隊列

鏈接：LeetCode232.用棧實現隊列

一、🌟題目描述🌟

二、🎨分析🎨

思考：
這個題會不會和上一道題很類似？
我們知道 棧的性質是 后進先出，而隊列的性質是先進先出
那么怎么讓最先進去的最先出來呢？
畫圖分一下：

顯然 最先入棧的是：1，那么如何讓1 先出棧呢？
那么我們是不是可以這樣？
把左邊的棧的元素全部push到右邊的空棧，因為棧是從棧頂出棧
所以 入右邊的棧的順序是4-3-2-1
變成了這樣：

這時候，如果想溢出1，只需要pop一下右邊的棧就可以了！
然后，我們是不是還要把 剩下的元素倒回原來的左邊的棧呢？
注意，這里和上面那個題不一樣的地方就在這里！
如果我們把右邊的棧的數據倒回左邊的棧，變成這樣：

這時候如果再出棧，是不是還要重復把左邊的棧的數據 重新push到右邊的棧？
這無疑增加了工作量！
由于棧有著后進先出的特殊性質，所以 我們只要把左邊的棧的數據push到右邊的棧，右邊的棧中就可以不斷的pop（因為此時元素的順序已經顛倒了！，符合先進先出了）
所以，導入到右邊的棧之后，不需要再回來了！！！
然后 怎么push呢？，我們直接向左邊的棧中push就可以了！！
也就是說：左邊的棧用來push,我們叫做pushst,右邊的棧用來pop，我們叫做popst
如果，popst已經空了，那么再把pushst里面的數據push到popst 就可以了！

總結：

	- 棧的性質和隊列不一樣，因為隊列是先進先出
所以把一個數據從一個隊列push到另一個隊列之后，原來的元素順序不會發生改變
所以需要在倒回來- 而棧的性質不一樣，棧是后進先出
所以把`pushst`里的數據導入到`popst`之后，數據的順序發生顛倒
所以，由于已經顛倒過來，把`popst`里的數據進行pop，就相當于隊列的出隊！
而不需要再倒回`pushst`的原因是因為： 這時候的`popst`里的數據順序恰好是出隊順序
而如果重新導入`pushst`，那么再pop數據的時候，還需要把數據先push到`popst`中- 這樣，如果我們想push數據，直接push到`pushst`中，
當`popst`空的時候，把`pushst`中數據導入到`popst`中，從而實現繼續出隊！

也就是說： pushst控制入隊，popst控制出隊

這個結構就相當于

三、💥題解💥

模擬隊列的結構

包含兩個棧

//匿名結構體的使用 可以利用typedef！
typedef struct {ST pushst;ST popst;
} MyQueue;

初始化隊列

首先malloc一個 ‘隊列’
然后要初始化 隊列中的兩個棧
pushst用來push
popst用來pop

MyQueue* myQueueCreate() {MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));//初始化兩個棧StackInit(&obj->pushst);StackInit(&obj->popst);return obj;
}

Push

這樣其實 push就很簡單了
只需要向棧pushst里直接push就可以了！

void myQueuePush(MyQueue* obj, int x) {//入隊統一在push棧中入數據StackPush(&obj->pushst,x);
}

Pop

pop比較麻煩，但也很簡單
因為我們首先判斷popst是不是為空
如果為空，那么pushst中的數據push到popst
否則直接poppopst

int myQueuePop(MyQueue* obj) {//出棧 是對pop進行的//如果popst為空 那么首先把pushst里的數據導入到popstif(StackEmpty(&obj->popst)){while(!StackEmpty(&obj->pushst)){StackPush(&obj->popst,StackTop(&obj->pushst));StackPop(&obj->pushst);}}//需要記錄隊尾 并返回int qtail=StackTop(&obj->popst);//出隊StackPop(&obj->popst);//返回隊尾元素return qtail;}

獲取隊頭元素

由于popst的棧頂就相當于隊頭，所以直接返回popst的棧頂就可以了！
注意：需要判斷一下popst是不是為空！
如果為空 需要把pushst中的數據 先 push到popst

int myQueuePeek(MyQueue* obj) {//隊列的頭相當于 popst的棧頂//首先判斷是不是空 如果是空 導入到popstif(StackEmpty(&obj->popst)){while(!StackEmpty(&obj->pushst)){StackPush(&obj->popst,StackTop(&obj->pushst));StackPop(&obj->pushst);}}return StackTop(&obj->popst);
}

判斷是不是空

顯然如果兩個棧都為空 說明隊列為空

bool myQueueEmpty(MyQueue* obj) {//什么時候為空呢？//顯然 如果兩個棧都為空 說明隊列為空return StackEmpty(&obj->pushst) && StackEmpty(&obj->popst);
}

釋放

1. 首先釋放兩棧
2. 然后釋放隊列結構

void myQueueFree(MyQueue* obj) {//首先釋放兩個棧//然后釋放MyQueueStackDestory(&obj->pushst);StackDestory(&obj->popst);free(obj);
}

??總代碼??

typedef int STDataType;
typedef struct Stack {//動態開辟數組STDataType* a;int top;//棧頂int capacity;//容量
}ST;
//初始化
void StackInit(ST* ps);
//壓棧
void StackPush(ST* ps, STDataType x);
//出棧
void StackPop(ST* ps);
//獲取棧中有效元素個數
int StackSize(ST* ps);
//顯示棧頂元素
STDataType StackTop(ST* ps);
//檢測棧是否為空
bool StackEmpty(ST* ps);
//銷毀
void StackDestory(ST* ps);//初始化
void StackInit(ST* ps)
{assert(ps);ps->a = NULL;ps->capacity = ps->top = 0;
}
//壓棧
void StackPush(ST* ps, STDataType x)
{assert(ps);//首先檢查是不是需要擴容if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->a,sizeof(STDataType) * newCapacity);if (tmp == NULL){printf("realloc fail");exit(-1);}ps->capacity = newCapacity;ps->a = tmp;}ps->a[ps->top] = x;ps->top++;
}
//出棧
void StackPop(ST* ps)
{assert(ps);//有元素才能出棧assert(ps->top > 0);//只需要ps--就可以了ps->top--;}
//獲取棧中有效元素個數
int StackSize(ST* ps)
{assert(ps);return ps->top;
}
//獲取棧頂元素
STDataType StackTop(ST* ps)
{assert(ps);return ps->a[ps->top-1];
}
//檢測棧是否為空
bool StackEmpty(ST* ps)
{				assert(ps);return ps->top == 0;
}
//銷毀
void StackDestory(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;//ps->a 不用了 所以置空就可以了ps->capacity = ps->top = 0;
}//匿名結構體的使用 可以利用typedef！
typedef struct {ST pushst;ST popst;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));//初始化兩個棧StackInit(&obj->pushst);StackInit(&obj->popst);return obj;
}void myQueuePush(MyQueue* obj, int x) {//入隊統一在push棧中入數據StackPush(&obj->pushst,x);
}int myQueuePop(MyQueue* obj) {//出棧 是對pop進行的//如果popst為空 那么首先把pushst里的數據導入到popstif(StackEmpty(&obj->popst)){while(!StackEmpty(&obj->pushst)){StackPush(&obj->popst,StackTop(&obj->pushst));StackPop(&obj->pushst);}}//需要記錄隊尾 并返回int qtail=StackTop(&obj->popst);//出隊StackPop(&obj->popst);//返回隊尾元素return qtail;}int myQueuePeek(MyQueue* obj) {//隊列的頭相當于 popst的棧頂//首先判斷是不是空 如果是空 導入到popstif(StackEmpty(&obj->popst)){while(!StackEmpty(&obj->pushst)){StackPush(&obj->popst,StackTop(&obj->pushst));StackPop(&obj->pushst);}}return StackTop(&obj->popst);
}bool myQueueEmpty(MyQueue* obj) {//什么時候為空呢？//顯然 如果兩個棧都為空 說明隊列為空return StackEmpty(&obj->pushst) && StackEmpty(&obj->popst);
}void myQueueFree(MyQueue* obj) {//首先釋放兩個棧//然后釋放MyQueueStackDestory(&obj->pushst);StackDestory(&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);
*/

?感謝閱讀~ ?
??碼字不易，給個贊吧~??