? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 創(chuàng)作不易，感謝友友們?nèi)B！！

一、前言

? ? ? ? 棧和隊列的相互實現(xiàn)是用兩個棧去實現(xiàn)隊列或者是用兩個隊列去實現(xiàn)棧，這樣其實是把問題復(fù)雜化的，實際中沒有什么應(yīng)用價值，但是通過他們的相互實現(xiàn)可以讓我們更加深入地理解棧和隊列的特點，而我也是用兩道相關(guān)的OJ題來分析這個過程！

二、用兩個隊列實現(xiàn)棧

力扣：隊列實現(xiàn)棧

2.1 思路

2.2 代碼實現(xiàn)

2.2.1 隊列的代碼

我們先把隊列的實現(xiàn)聲明放這

Queue.h

#include<stdbool.h>
#include<assert.h>
typedef int QDatatype;//方便后面修改存儲數(shù)據(jù)的數(shù)據(jù)類型
typedef struct QueueNode//隊列結(jié)點的數(shù)據(jù)結(jié)構(gòu)
{QDatatype data;//存儲數(shù)據(jù)struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* phead;//指向隊頭，用于出隊（頭刪）QNode* ptail;//指向隊尾，用于入隊（尾插）int size;//記錄有效元素個數(shù)
}Queue;//創(chuàng)建一個隊列相關(guān)結(jié)構(gòu)體
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);//獲取隊列中有效元素個數(shù)
bool QueueEmpty(Queue* pq);//判斷隊列是否為空
void QueueDestory(Queue* pq);//隊列的銷毀

2.2.2?結(jié)構(gòu)體的創(chuàng)建

封裝一個myStack結(jié)構(gòu)體管理兩個隊列

typedef struct MyStack
{Queue q1;Queue q2;
} MyStack;
//用兩個隊列實現(xiàn)棧，構(gòu)建一個結(jié)構(gòu)體去管理這兩個隊列

2.2.3 初始化棧

初始化棧，相當(dāng)于先構(gòu)建棧的結(jié)構(gòu)體變量，然后再初始化他的兩個隊列成員

MyStack* myStackCreate() //返回一個MySack類型的指針
{MyStack* obj = (MyStack*)malloc(sizeof(MyStack));if (obj == NULL){perror("malloc fail");exit(1);}
//如果開辟成功，對棧初始化相當(dāng)于對棧結(jié)構(gòu)體中的兩個隊列初始化QueueInit(&obj->q1);QueueInit(&obj->q2);return obj;
}

2.2.4 模擬壓棧

按照我們之前的思路，壓棧直接找到不為空的隊列尾插就行

void myStackPush(MyStack* obj, int x)
//壓棧前必須在不為空的隊列中壓棧
{if (!QueueEmpty(&obj->q1))//如果q1不為空壓q1QueuePush(&obj->q1, x);else//如果q1為空，則壓q2QueuePush(&obj->q2, x);
}

2.2.5 模擬出棧并返回棧頂元素

按照之前的思路，出棧就是先找到非空的隊列，移除到空的隊列上，只留下最后一個元素，再頭刪

int myStackPop(MyStack* obj)
//出棧，必須找到不為空的隊列，然后將該隊列的元素倒倒另一個隊列中，知道只剩最后一個元素的時候，就刪除
{//要找到不為空的隊列進(jìn)行操作，所以先假設(shè)一個為空一個不為空，如果給個條件判斷Queue* Emptyq = &obj->q1;Queue* NonEmptyq = &obj->q2;if (!QueueEmpty(&obj->q1))//錯了的話就認(rèn)個錯然后換回來{NonEmptyq = &obj->q1;Emptyq = &obj->q2;}//開始導(dǎo)數(shù)據(jù)while (QueueSize(NonEmptyq) > 1){//將隊列頭的元素倒進(jìn)去另一個隊列，在出棧QueuePush(Emptyq, QueueFront(NonEmptyq));//壓棧QueuePop(NonEmptyq);//倒入一個就將非空隊列出隊列一個}//倒完后只剩一個數(shù)據(jù)了，先記錄返回值再刪除int top = QueueFront(NonEmptyq);QueuePop(NonEmptyq);return top;
}

2.2.6 獲取棧頂元素

找到不為空的隊列，然后獲取隊列尾的元素，就是獲取棧頂元素

int myStackTop(MyStack* obj)
//找到不為空的隊列，然后獲取隊列尾的元素，相當(dāng)于獲取棧頂元素
{if (!QueueEmpty(&obj->q1))//如果q1不為空取q1隊尾return QueueBack(&obj->q1);else//如果q2不為空取q2隊尾return QueueBack(&obj->q2);
}

2.2.7 判斷棧是否為空

判斷棧是否為空，本質(zhì)上就是判斷兩個隊列是否為空

bool myStackEmpty(MyStack* obj) //棧為空當(dāng)且僅當(dāng)兩個隊列都為空
{return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

2.2.8 釋放棧

要先釋放掉棧的隊列成員的空間，然后再釋放棧的空間，并置空

void myStackFree(MyStack* obj) 
{//釋放obj前一定也要將q1和q2的空間釋放了QueueDestory(&obj->q1);QueueDestory(&obj->q2);free(obj);//obj = NULL;沒用，一級指針接受指針相當(dāng)于值傳遞//要手動在main函數(shù)中置空
}

值得注意的是，這邊給obj置空是沒有的，要想改變obj必須用二級指針，所以我們最后要釋放的話要在程序的最后自己手動釋放。?

2.3 全部代碼

2.3.1 queue.h

#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int QDatatype;//方便后面修改存儲數(shù)據(jù)的數(shù)據(jù)類型
typedef struct QueueNode//隊列結(jié)點的數(shù)據(jù)結(jié)構(gòu)
{QDatatype data;//存儲數(shù)據(jù)struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* phead;//指向隊頭，用于出隊（頭刪）QNode* ptail;//指向隊尾，用于入隊（尾插）int size;//記錄有效元素個數(shù)
}Queue;//創(chuàng)建一個隊列相關(guān)結(jié)構(gòu)體
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);//獲取隊列中有效元素個數(shù)
bool QueueEmpty(Queue* pq);//判斷隊列是否為空
void QueueDestory(Queue* pq);//隊列的銷毀

2.3.2 queue.c

#include"Queue.h"void QueueInit(Queue* pq)
{assert(pq);//判斷傳的是不是空指針pq->phead = pq->ptail = NULL;pq->size = 0;//因為隊列不像棧一樣，有一個top表示棧頂元素的下標(biāo)//所以如果我們想知道這個隊列的有效數(shù)據(jù)個數(shù)，就必須遍歷隊列//由于其先進(jìn)先出的特性，我們默認(rèn)只能訪問到頭元素和尾元素//所以必須訪問一個頭元素，就出隊列一次，這樣才能實現(xiàn)遍歷//但是這樣的代價太大了，為了方便，我們直接用size
}
void QueuePush(Queue* pq, QDatatype x)
{assert(pq);//入隊必須從隊尾入！QNode* newnode = (QNode*)malloc(sizeof(QNode));//創(chuàng)建一個新節(jié)點if (newnode == NULL)//如果新節(jié)點申請失敗，退出程序{perror("malloc fail");}//新節(jié)點創(chuàng)建成功，給新節(jié)點初始化一下newnode->data = x;newnode->next = NULL;//開始入隊//如果直接尾插的話，由于會用到ptail->next,所以得考慮隊列為空的情況if (pq->ptail == NULL)//如果為空，直接把讓新節(jié)點成為phead和ptail{//按道理來說，如果ptail為空，phead也應(yīng)該為空// 但是有可能會因為我們的誤操作使得phead不為空，這個時候一般是我們寫錯的問題//所以使用assert來判斷一下，有問題的話會及時返回錯誤信息assert(pq->phead == NULL);pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}void QueuePop(Queue* pq)
{assert(pq);//如果隊列為空，沒有刪除的必要assert(!QueueEmpty(pq));//隊列中的出隊列相當(dāng)于鏈表的頭刪//如果直接頭刪，那么如果隊列只有一個有效數(shù)據(jù)的話，那么我們將phead的空間釋放掉，但是沒有將ptail給置空//這樣會導(dǎo)致ptail成為一個野指針，所以我們需要考慮只有一個節(jié)點多個節(jié)點的情況if (pq->phead->next == NULL)//一個節(jié)點的情況,直接將這個節(jié)點釋放并置空即可{free(pq->phead);pq->phead = pq->ptail = NULL;//置空，防止野指針}else//多個節(jié)點的情況，直接頭刪{QNode* next = pq->phead->next;//臨時指針記住下一個節(jié)點free(pq->phead);pq->phead = next;//讓下一個節(jié)點成為新的頭}pq->size--;
}QDatatype QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//隊列如果為空，則不可能找得到隊列頭元素//隊列不為空的時候，直接返回phead指向的數(shù)據(jù)return pq->phead->data;
}QDatatype QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//隊列如果為空，則不可能找得到隊尾元素//隊列不為空的時候，直接返回ptail指向的數(shù)據(jù)return pq->ptail->data;
}int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}bool QueueEmpty(Queue* pq)//鏈表為空的情況，可以根據(jù)容量，也可以根據(jù)ptail==NULL&&phead==NULL
{assert(pq);return pq->phead == NULL && pq->ptail == NULL;
}void QueueDestory(Queue* pq)
{assert(pq);//判斷傳的是不是空指針//要逐個節(jié)點釋放QNode* pcur = pq->phead;while (pcur){QNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}

2.3.3 mystack.h

#include"Queue.h"typedef struct MyStack
{Queue q1;Queue q2;
} MyStack;
//用兩個隊列實現(xiàn)棧，構(gòu)建一個結(jié)構(gòu)體去管理這兩個隊列MyStack* myStackCreate();//初始化棧
void myStackPush(MyStack* obj, int x);//壓棧
int myStackPop(MyStack* obj);//出棧
int myStackTop(MyStack* obj);//獲取棧頂元素
bool myStackEmpty(MyStack* obj);//判斷棧是否為空
void myStackFree(MyStack* obj);//釋放棧

2.3.4 mystack.c

#include"MyStack.h"MyStack* myStackCreate() //返回一個MySack類型的指針
{MyStack* obj = (MyStack*)malloc(sizeof(MyStack));if (obj == NULL){perror("malloc fail");exit(1);}
//如果開辟成功，對棧初始化相當(dāng)于對棧結(jié)構(gòu)體中的兩個隊列初始化QueueInit(&obj->q1);QueueInit(&obj->q2);return obj;
}void myStackPush(MyStack* obj, int x)
//壓棧前必須在不為空的隊列中壓棧
{if (!QueueEmpty(&obj->q1))//如果q1不為空壓q1QueuePush(&obj->q1, x);else//如果q1為空，則壓q2QueuePush(&obj->q2, x);
}int myStackPop(MyStack* obj)
//出棧，必須找到不為空的隊列，然后將該隊列的元素倒倒另一個隊列中，知道只剩最后一個元素的時候，就刪除
{//要找到不為空的隊列進(jìn)行操作，所以先假設(shè)一個為空一個不為空，如果給個條件判斷Queue* Emptyq = &obj->q1;Queue* NonEmptyq = &obj->q2;if (!QueueEmpty(&obj->q1))//錯了的話就認(rèn)個錯然后換回來{NonEmptyq = &obj->q1;Emptyq = &obj->q2;}//開始導(dǎo)數(shù)據(jù)while (QueueSize(NonEmptyq) > 1){//將隊列頭的元素倒進(jìn)去另一個隊列，在出棧QueuePush(Emptyq, QueueFront(NonEmptyq));//壓棧QueuePop(NonEmptyq);//倒入一個就將非空隊列出隊列一個}//倒完后只剩一個數(shù)據(jù)了，先記錄返回值再刪除int top = QueueFront(NonEmptyq);QueuePop(NonEmptyq);return top;
}int myStackTop(MyStack* obj)
//找到不為空的隊列，然后獲取隊列尾的元素，相當(dāng)于獲取棧頂元素
{if (!QueueEmpty(&obj->q1))//如果q1不為空取q1隊尾return QueueBack(&obj->q1);else//如果q2不為空取q2隊尾return QueueBack(&obj->q2);
}bool myStackEmpty(MyStack* obj) //棧為空當(dāng)且僅當(dāng)兩個隊列都為空
{return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}void myStackFree(MyStack* obj) 
{//釋放obj前一定也要將q1和q2的空間釋放了QueueDestory(&obj->q1);QueueDestory(&obj->q2);free(obj);//obj = NULL;沒用，一級指針接受指針相當(dāng)于值傳遞//要手動在main函數(shù)中置空

三、用兩個棧實現(xiàn)隊列

力扣：用棧實現(xiàn)隊列

3.1 思路

3.2 代碼實現(xiàn)

3.2.1 棧的代碼

這里先把棧的聲明放這里

stack.h

#pragma once
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>typedef int STDataType;
//支持動態(tài)增長的棧
typedef struct Stack
{STDataType* a;int top;//棧頂int capacity;//棧容量
}Stack;void StackInit(Stack* ps);//初始化棧
void StackPush(Stack* ps, STDataType x);//入棧
void StackPop(Stack* ps);//出棧
STDataType StackTop(Stack* ps);//獲取棧頂元素
int StackSize(Stack* ps);//獲取棧中有效元素個數(shù)
bool StackEmpty(Stack* ps);//檢測棧是否為空，為空返回true
void StackDestory(Stack* ps);//銷毀棧

3.2.2 結(jié)構(gòu)體的創(chuàng)建

?根據(jù)前面的思路，一個棧專門用來入棧，一個棧專門用來出棧

typedef struct  MyQueue
{Stack Pushst;//專門用來入棧Stack Popst;//專門用來出棧
} MyQueue;MyQueue* myQueueCreate();//初始化隊列
void myQueuePush(MyQueue* obj, int x);//模擬入隊
int myQueuePop(MyQueue* obj);//模擬出隊，并返回出去的頭元素
int myQueuePeek(MyQueue* obj);//獲取隊列頭元素并返回
bool myQueueEmpty(MyQueue* obj);//判斷隊列是否為空
void myQueueFree(MyQueue* obj);//銷毀隊列

3.2.3 初始化隊列并返回節(jié)點

?初始化隊列本質(zhì)上就是對兩個棧進(jìn)行初始化

MyQueue* myQueueCreate() 
{MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));if (obj == NULL){perror("malloc fail");exit(1);}//對隊列初始化其實就是對里面的兩個棧初始化StackInit(&obj->Pushst);StackInit(&obj->Popst);return obj;
}

3.2.4 模擬入隊

入隊就很簡單了，直接往第一個棧里面入棧就行

void myQueuePush(MyQueue* obj, int x)
{StackPush(&obj->Pushst, x);
}

3.2.5 獲取隊列頭的元素并返回

隊列頭的元素要在第二個棧去獲取，但在獲取前還得確保第二個棧有元素，如果沒有，就得先把第一個棧倒過去

int myQueuePeek(MyQueue* obj)
//獲取隊列頭元素有兩種情況
//1、一種是popst不為空，直接返回其top下標(biāo)的元素就行了
//2、一種是popst為空，這時候需要將pushst中的數(shù)據(jù)全部倒過去，再重復(fù)情況1
{if (StackEmpty(&obj->Popst)){while (!StackEmpty(&obj->Pushst)){//挪數(shù)據(jù)就是一邊給popst入棧，一邊給pushst出棧StackPush(&obj->Popst, StackTop(&obj->Pushst));StackPop(&obj->Pushst);}}return StackTop(&obj->Popst);
}

3.2.6 模擬出隊，并返回出去的頭元素

出隊也要確保第二個棧不為空，但其實我們有了上面這個函數(shù)，直接調(diào)用一次就相當(dāng)于是把我們把這個操作給完成了，所以我們直接接受上面那個函數(shù)的返回值然后直接pop就行

int myQueuePop(MyQueue* obj)
{
//跟myQueuePeek一樣有兩種情況，但是我們調(diào)用了這個函數(shù)相當(dāng)于是幫我們判斷過了，此時直接刪就可以了int top = myQueuePeek(obj);StackPop(&obj->Popst);return top;
}

3.2.7 判斷隊列是否為空

隊列是否為空，本質(zhì)上就是兩個棧是否為空

bool myQueueEmpty(MyQueue* obj) 
{return StackEmpty(&obj->Popst) && StackEmpty(&obj->Pushst);
}

3.2.8 銷毀隊列?

隊列銷毀，本質(zhì)上就是兩個棧的銷毀，但是要在最后把隊列的結(jié)構(gòu)體的釋放掉

void myQueueFree(MyQueue* obj) 
{StackDestory(&obj->Popst);StackDestory(&obj->Pushst);free(obj);//沒用obj = NULL;
}

注意的是這邊接受obj的是一級指針，相當(dāng)于值傳遞，這里置空沒什么意義，要在外面手動置空?

3.3 全部代碼

3.3.1 stack.h

#pragma once
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>typedef int STDataType;
//支持動態(tài)增長的棧
typedef struct Stack
{STDataType* a;int top;//棧頂int capacity;//棧容量
}Stack;void StackInit(Stack* ps);//初始化棧
void StackPush(Stack* ps, STDataType x);//入棧
void StackPop(Stack* ps);//出棧
STDataType StackTop(Stack* ps);//獲取棧頂元素
int StackSize(Stack* ps);//獲取棧中有效元素個數(shù)
bool StackEmpty(Stack* ps);//檢測棧是否為空，為空返回true
void StackDestory(Stack* ps);//銷毀棧

3.3.2 stack.c

#include"Stack.h"void StackInit(Stack* ps)
{ps->a = NULL;ps->top = ps->capacity = 0;
}void StackPush(Stack* ps, STDataType x)
{assert(ps);//判斷是否需要擴(kuò)容if (ps->top == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* temp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);if (temp == NULL){perror("realloc fail");exit(1);}ps->a = temp;ps->capacity = newcapacity;}//壓棧ps->a[ps->top++] = x;
}void StackPop(Stack* ps)
{assert(ps);//如果棧為空，則沒有刪除的必要assert(!StackEmpty(ps));ps->top--;
}STDataType StackTop(Stack* ps)
{assert(ps);//如果棧為空，不可能有棧頂元素assert(!StackEmpty(ps));return ps->a[ps->top - 1];
}int StackSize(Stack* ps)
{assert(ps);return ps->top;
}bool StackEmpty(Stack* ps)
{assert(ps);return ps->top == 0;
}void StackDestory(Stack* ps)
{free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}

3.3.3 myqueue.h

#include"Stack.h"typedef struct  MyQueue
{Stack Pushst;//專門用來入棧Stack Popst;//專門用來出棧
} MyQueue;MyQueue* myQueueCreate();//初始化隊列并返回節(jié)點
void myQueuePush(MyQueue* obj, int x);//模擬入隊
int myQueuePop(MyQueue* obj);//模擬出隊，并返回出去的頭元素
int myQueuePeek(MyQueue* obj);//獲取隊列頭元素并返回
bool myQueueEmpty(MyQueue* obj);//判斷隊列是否為空
void myQueueFree(MyQueue* obj);//銷毀隊列

3.3.4 myqueue.c

#include"MyQueue.h"MyQueue* myQueueCreate() 
{MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));if (obj == NULL){perror("malloc fail");exit(1);}//對隊列初始化其實就是對里面的兩個棧初始化StackInit(&obj->Pushst);StackInit(&obj->Popst);return obj;
}void myQueuePush(MyQueue* obj, int x)
{StackPush(&obj->Pushst, x);
}int myQueuePop(MyQueue* obj)
{
//跟myQueuePeek一樣有兩種情況，但是我們調(diào)用了這個函數(shù)相當(dāng)于是幫我們判斷過了，此時直接刪就可以了int top = myQueuePeek(obj);StackPop(&obj->Popst);return top;
}int myQueuePeek(MyQueue* obj)
//獲取隊列頭元素有兩種情況
//1、一種是popst不為空，直接返回其top下標(biāo)的元素就行了
//2、一種是popst為空，這時候需要將pushst中的數(shù)據(jù)全部倒過去，再重復(fù)情況1
{if (StackEmpty(&obj->Popst)){while (!StackEmpty(&obj->Pushst)){//挪數(shù)據(jù)就是一邊給popst入棧，一邊給pushst出棧StackPush(&obj->Popst, StackTop(&obj->Pushst));StackPop(&obj->Pushst);}}return StackTop(&obj->Popst);
}bool myQueueEmpty(MyQueue* obj) 
{return StackEmpty(&obj->Popst) && StackEmpty(&obj->Pushst);
}void myQueueFree(MyQueue* obj) 
{StackDestory(&obj->Popst);StackDestory(&obj->Pushst);free(obj);//沒用obj = NULL;
}