【Leedcode】棧和隊(duì)列必備的面試題（第二期）

---

---

一、題目（用兩個(gè)隊(duì)列實(shí)現(xiàn)棧）

Leedcode鏈接

---

---

---

這幾個(gè)接口使我們需要實(shí)現(xiàn)的我會(huì)一 一實(shí)現(xiàn)并講解！

---

二、思路+圖解

注意：這里會(huì)用到很多棧和隊(duì)列接口實(shí)現(xiàn)的一些知識(shí)，這里不再深究，如果想了解可以去下面兩個(gè)博客！
棧的接口模擬實(shí)現(xiàn) + 隊(duì)列的接口模擬實(shí)現(xiàn)

---

做本題需要的接口和結(jié)構(gòu)體聲明！

代碼如下（示例）：

typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QueueNode;typedef struct Queue
{QueueNode* head;QueueNode* tail;
}Queue;void QueueInit(Queue* pq);//初始化隊(duì)列
void QueueDestroy(Queue* pq);//銷(xiāo)毀隊(duì)列
void QueuePush(Queue* pq, QDataType x);//放入數(shù)據(jù)
void QueuePop(Queue* pq);//刪除數(shù)據(jù)
QDataType QueueFront(Queue* pq);//取頭數(shù)據(jù)
QDataType QueueBack(Queue* pq);//取尾數(shù)據(jù)
size_t QueueSize(Queue* pq);//計(jì)算數(shù)據(jù)個(gè)數(shù)
bool QueueEmpty(Queue* pq);//判斷隊(duì)列是不是空void QueueInit(Queue* pq)
{assert(pq);pq->head = NULL;pq->tail = NULL;
}void QueueDestroy(Queue* pq)//銷(xiāo)毀隊(duì)列
{assert(pq);//創(chuàng)建一個(gè)cur指針 指向隊(duì)列頭 用于挨個(gè)釋放空間QueueNode* cur = pq->head;//當(dāng)cur不為NULL 一直循環(huán)執(zhí)行  挨個(gè)釋放列表成員空間while (cur != NULL){QueueNode* next = cur->next;free(cur);cur = next;}//當(dāng)循環(huán)結(jié)束 將 head與tail 置為NULLpq->head = pq->tail = NULL;
}void QueuePush(Queue* pq, QDataType x)//放入數(shù)據(jù)
{assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));newnode->data = x;newnode->next = NULL; if (pq->head == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}}void QueuePop(Queue* pq)//刪除數(shù)據(jù)
{assert(pq);assert(!QueueEmpty(pq));QueueNode* next = pq->head->next;free(pq->head);if (pq->head == pq->tail){pq->tail = NULL;}pq->head = next; 
}QDataType QueueFront(Queue* pq)//取頭數(shù)據(jù)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}QDataType QueueBack(Queue* pq)//取尾數(shù)據(jù)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}
size_t QueueSize(Queue* pq)//計(jì)算數(shù)據(jù)個(gè)數(shù)
{assert(pq);assert(!QueueEmpty(pq));QueueNode* cur = pq->head;int n = 0;while (cur){cur = cur->next;n++;}return n;
}bool QueueEmpty(Queue* pq)//判斷隊(duì)列是不是空
{assert(pq);return pq->head == NULL && pq->tail == NULL;
}

---

1.定義兩個(gè)隊(duì)列

代碼如下（示例）：

typedef struct{Queue q1;Queue q2;
} MyStack;

---

2.初始化兩個(gè)隊(duì)列

---

---

代碼如下（示例）：

MyStack* myStackCreate() {MyStack* st = (MyStack*)malloc(sizeof(MyStack));QueueInit(&st->q1);QueueInit(&st->q2);return st;
}

---

3.往兩個(gè)隊(duì)列中放入數(shù)據(jù)

---

---

---

代碼如下（示例）：

void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(&obj->q1)){QueuePush(&obj->q1, x);}else{QueuePush(&obj->q2, x);}
}

---

4.兩個(gè)隊(duì)列出數(shù)據(jù)

---

---

---

---

代碼如下（示例）：

int myStackPop(MyStack* obj) {Queue* emptyQ = &obj->q1;Queue* nonemptyQ = &obj->q2;if(!QueueEmpty(&obj->q1)){nonemptyQ = &obj->q1;emptyQ = &obj->q2;}while(QueueSize(nonemptyQ)>1){QueuePush(emptyQ, QueueFront(nonemptyQ));QueuePop(nonemptyQ);}int ret = QueueFront(nonemptyQ);QueuePop(nonemptyQ);return ret;
}

---

5.顯示棧頂信息

代碼如下（示例）：

int myStackTop(MyStack* obj) {if(!QueueEmpty(&obj->q1)){return QueueBack(&obj->q1);}else{return QueueBack(&obj->q2);}
}

---

6.判斷棧或者隊(duì)列是否為空

代碼如下（示例）：

bool myStackEmpty(MyStack* obj) 
{return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

---

7.銷(xiāo)毀?；蛘哧?duì)列

---

代碼如下（示例）：

void myStackFree(MyStack* obj) 
{QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);
}

---

三、總代碼展示

代碼如下（示例）：

typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QueueNode;typedef struct Queue
{QueueNode* head;QueueNode* tail;
}Queue;void QueueInit(Queue* pq);//初始化隊(duì)列
void QueueDestroy(Queue* pq);//銷(xiāo)毀隊(duì)列
void QueuePush(Queue* pq, QDataType x);//放入數(shù)據(jù)
void QueuePop(Queue* pq);//刪除數(shù)據(jù)
QDataType QueueFront(Queue* pq);//取頭數(shù)據(jù)
QDataType QueueBack(Queue* pq);//取尾數(shù)據(jù)
size_t QueueSize(Queue* pq);//計(jì)算數(shù)據(jù)個(gè)數(shù)
bool QueueEmpty(Queue* pq);//判斷隊(duì)列是不是空void QueueInit(Queue* pq)
{assert(pq);pq->head = NULL;pq->tail = NULL;
}void QueueDestroy(Queue* pq)//銷(xiāo)毀隊(duì)列
{assert(pq);//創(chuàng)建一個(gè)cur指針 指向隊(duì)列頭 用于挨個(gè)釋放空間QueueNode* cur = pq->head;//當(dāng)cur不為NULL 一直循環(huán)執(zhí)行  挨個(gè)釋放列表成員空間while (cur != NULL){QueueNode* next = cur->next;free(cur);cur = next;}//當(dāng)循環(huán)結(jié)束 將 head與tail 置為NULLpq->head = pq->tail = NULL;
}void QueuePush(Queue* pq, QDataType x)//放入數(shù)據(jù)
{assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));newnode->data = x;newnode->next = NULL; if (pq->head == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}}void QueuePop(Queue* pq)//刪除數(shù)據(jù)
{assert(pq);assert(!QueueEmpty(pq));QueueNode* next = pq->head->next;free(pq->head);if (pq->head == pq->tail){pq->tail = NULL;}pq->head = next; 
}QDataType QueueFront(Queue* pq)//取頭數(shù)據(jù)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}QDataType QueueBack(Queue* pq)//取尾數(shù)據(jù)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}
size_t QueueSize(Queue* pq)//計(jì)算數(shù)據(jù)個(gè)數(shù)
{assert(pq);assert(!QueueEmpty(pq));QueueNode* cur = pq->head;int n = 0;while (cur){cur = cur->next;n++;}return n;
}bool QueueEmpty(Queue* pq)//判斷隊(duì)列是不是空
{assert(pq);return pq->head == NULL && pq->tail == NULL;
}//定義兩個(gè)隊(duì)列
typedef struct{Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {//函數(shù)內(nèi)定義變量出了函數(shù)就沒(méi)了，所以我們?cè)谶@里選擇用malloc開(kāi)辟動(dòng)態(tài)空間 并將這個(gè)空間的地址返回給函數(shù)MyStack* st = (MyStack*)malloc(sizeof(MyStack));//調(diào)用自己的隊(duì)列初始化函數(shù) 將定義的2個(gè)隊(duì)列初始化QueueInit(&st->q1);QueueInit(&st->q2);//函數(shù)要求 返回新開(kāi)辟的地址(棧地址)return st;
}void myStackPush(MyStack* obj, int x) {//往棧中放入數(shù)據(jù)if(!QueueEmpty(&obj->q1))//當(dāng)q1不是空的時(shí) 將數(shù)據(jù)放入q1隊(duì)列中{//調(diào)用隊(duì)列函數(shù)，自定義函數(shù)傳過(guò)來(lái)的是棧的指針，所以要&obj的地址指向q1QueuePush(&obj->q1, x);}else//當(dāng)q2不是空的時(shí) 將數(shù)據(jù)放入q1隊(duì)列中  由于這里是else 所以假設(shè)q1 q2都是空也會(huì)將數(shù)據(jù)放入q2隊(duì)列中{QueuePush(&obj->q2, x);}
}int myStackPop(MyStack* obj) {//emptyQ表示空隊(duì)列   nonEmptuQ 表示有元素隊(duì)列//先假設(shè)定義隊(duì)列 q1為空 q2 非空Queue* emptyQ = &obj->q1;Queue* nonemptyQ = &obj->q2;//然后調(diào)用判斷是否為空函數(shù)if(!QueueEmpty(&obj->q1))//如果隊(duì)列q1 非空進(jìn)入循環(huán){//向q1道歉 將q1改為非空  將q2改為空nonemptyQ = &obj->q1;emptyQ = &obj->q2;}//此時(shí) nonempyuQ 與 emptyQ 經(jīng)歷了修正 隊(duì)列nonempyuQ 是非空 emptyQ是空 （特殊情況下兩者都是空）while(QueueSize(nonemptyQ)>1)//循環(huán)條件 非空的nonemptyQ隊(duì)列數(shù)據(jù)個(gè)數(shù)最少是大于1就可以進(jìn)入循環(huán)，假設(shè)等于或小于1不進(jìn)入循環(huán){//將非空nonemptyQ隊(duì)列元素?cái)?shù)據(jù)放入，空emptyQ隊(duì)列中QueuePush(emptyQ, QueueFront(nonemptyQ));//放進(jìn)去一個(gè)就刪除一個(gè)非空nonemptyQ隊(duì)列元素QueuePop(nonemptyQ);}//當(dāng)循環(huán)結(jié)束來(lái)到這里nonempty內(nèi)只有一個(gè)元素，這個(gè)元素也表示的是棧頂?shù)脑?特殊情況下nonempty也是空的)int ret = QueueFront(nonemptyQ);QueuePop(nonemptyQ);//最后刪除這個(gè)元素（表達(dá)出棧行為）return ret;//函數(shù)要求返回這個(gè)被刪除的元素?cái)?shù)據(jù)
}
int myStackTop(MyStack* obj) {//顯示棧頂信息if(!QueueEmpty(&obj->q1))//棧頂不為空進(jìn)入{//返回q1隊(duì)列尾部數(shù)據(jù)return QueueBack(&obj->q1);}else{//返回q2隊(duì)列尾部數(shù)據(jù)return QueueBack(&obj->q2);}
}bool myStackEmpty(MyStack* obj) {//當(dāng)q1為空 并且 q2為空 則返回真 return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}void myStackFree(MyStack* obj) {//先將q1 和 q2 空間銷(xiāo)毀QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);//最后釋放obj空間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);
*/

---

總結(jié)

以上就是今天要講的內(nèi)容，本文為【Leedcode】棧和隊(duì)列必備的面試題（第二期）
如果我的博客對(duì)你有所幫助記得三連支持一下，感謝大家的支持！