前言

????????我們已經學習了棧和隊列，也都實現了它們各自的底層接口，那么接下我們就要開始棧和隊列的專項刷題訓練。

---

1. 題目：使用隊列實現棧

題目描述：

?題目鏈接：

隊列實現棧https://leetcode.cn/problems/implement-stack-using-queues/

?2. 思路

????????隊列的結構是先進先出，題目的要求是，讓我們利用隊列的底層接口來實現棧，不可以改變隊列的底層邏輯，所以如果你的思路是逆置隊列這個鏈表，那這個思路就被pass掉了。

? ? ? ? ?那我們要如何利用隊列尾進頭出的特性來實現棧的尾進尾出呢？題目中給了我們兩個隊列，我們要使用這兩個隊列實現棧。

? ? ? ? 入棧操作好說，問題在于出棧問題，思路是這樣的：我們有兩個隊列，一個隊列用于存儲數據，另外一個隊列（空隊列）用于拷貝數據，將原隊列的前n-1個數據拷貝到空隊列中，然后再將原隊列剩余的最后一個元素出隊列，這樣就模擬實現了棧的尾出。

?

3. 分析?

?????????根據上述的思路分析，隊列實現棧，入棧不需要什么特殊操作例如我們入棧：1、2、3、4、5，出棧呢就是：5、4、3、2、1。

????????上述的思路已經介紹了解決辦法，也是非常簡單的，但有人可能會問：那這樣算法的效率豈不是很低？這種方法的效率確實低，但是這道題目考察的并不是效率的問題，而實性質問題，這也是一道經典的面試題目。這道題目并不難，但它考察對數據結構的理解，各各接口的實現中有很多需要注意的細節。

????????首先這道題目是并沒有給現成的隊列，使用C語言解決需要我們現成造輪子，這也是C語言刷題的弊端，有很多題目都需要造輪子。那么這里我們就可以直接復制前邊我們實現的隊列。

?接下來就是我們開始注意實現接口：

?????????首先題目中給了我們兩個隊列，為了便于傳參和使用，我們可以定義一個結構體：

typedef struct {
Que q1;    //注意這里定于的隊列類型一定要與自己定義的隊列結構體類型對應
Que q2;
} MyStack;

?這里我們在前邊介紹結構體時提到過，匿名結構體。

?3.1 創建棧

MyStack* myStackCreate() {}

?題目給出的接口如上，那這里我們要怎么創建我們的棧呢？是這樣嗎？

MyStack* myStackCreate() {MyStack st;//…return &st;
}

?????????對函數和指針比較熟悉的同學可能就已經發現不行，為什么不行？這里就牽扯到了函數相關的知識，函數內創建的變量都是存儲在棧區，出了函數就會被銷毀，內存已經被銷毀，返回指針還有什么意義呢？所以這里需要使用malloc函數，動態內存分配開辟的空間在堆區，程序結束前不主動釋放就一直存在。所以上述的創建變量的方法不可取。

正確的方法：

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

?????????這里的pst->q1,就等價于我們在創建的隊列的結構體變量：Que q；在調用接口時需要傳地址過去。

3.2入棧

????????接下來就是入棧，題目中給了我們兩個隊列，為了后續出棧操作我們需要確保一個隊列為空，用于拷貝數據，所以我們入棧時需要在不為空的隊列入。

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

如果兩個都為空那就隨便選一個都可以。

3.3 出棧

????????在進行出棧操作的時候，我們需要判斷哪一個隊列為空，然后將非空隊列的前n-1個元素依次拷貝到空隊列當中。這里我們可以先假設隊列1為空，然后在判斷隊列1是否為空，如果不為空那就是隊列2為空，進行修改。這個假設的方法還是很實用的。

?拷貝過程如下：

????????注意這里是拷貝，不是將原隊列的節點插入到空隊列，而是通過隊頭數據這個函數接口來將數據傳過去，然后入隊（調用入隊接口），入隊之后及時更新隊頭（出隊）。

?

?

int myStackPop(MyStack* obj) {Que* Empty=&obj->q1;Que* NoEmpty=&obj->q2;if(!IsEmpty(&obj->q1)){Empty=&obj->q2;NoEmpty=&obj->q1;}while(QueueSize(NoEmpty)>1){QueuePush(Empty,QueueFront(NoEmpty));QueuePop(NoEmpty);}int top=QueueFront(NoEmpty);//最后保存非空隊列最后一個隊列節點的數據，便于返回QueuePop(NoEmpty);          //最后一個元素出隊。return top;
}

?3.4 棧頂數據

?????????棧頂數據接口實現就簡單了，我們前邊對隊列進行實現時，有隊頭和隊尾數據的接口，我們可以直接調用。

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

?3.5 判空和 “ 棧 ” 的銷毀

?????????判空就很簡單，如果兩個隊列都為空，那么這個 “ 棧 ” 也就為空。

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

?????????“ 棧 ”的銷毀，這里就不能直接free掉obj了，如果直接釋放那我們程序中的兩個隊列就會丟失無法釋放，所以在釋放掉obj之前，我們需要先將兩個隊列銷毀。

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

?4. 題解

?完整代碼如下：

typedef int Datatype;
typedef struct QueueNode
{struct QueueNode* next;Datatype data;}QueueNode;
typedef struct Queue
{QueueNode* head;QueueNode* tail;int size;
}Que;
//初始化隊列
void QueueInit(Que* pq);
//入隊
void QueuePush(Que* pq, Datatype x);
//出隊
void QueuePop(Que* pq);
//隊頭數據
Datatype QueueFront(Que* pq);
//隊尾數據
Datatype QueueBlack(Que* pq);
//判空
bool IsEmpty(Que* pq);
//隊列大小
int QueueSize(Que* pq);
//銷毀隊列
void DestoryQueue(Que* pq);void QueueInit(Que* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}
void QueuePush(Que* pq, Datatype x)
{assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));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(!IsEmpty(pq));if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QueueNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->size--;
}
Datatype QueueFront(Que* pq)
{assert(pq);assert(!IsEmpty(pq));return pq->head->data;
}
Datatype QueueBlack(Que* pq)
{assert(pq);assert(!IsEmpty(pq));return pq->tail->data;
}
bool IsEmpty(Que* pq)
{assert(pq);return (pq->head == NULL);
}
int QueueSize(Que* pq)
{assert(pq);return pq->size;
}
void DestoryQueue(Que* pq)
{assert(pq);QueueNode* cur = pq->head;while (cur){QueueNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->size = 0;
}
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(!IsEmpty(&obj->q1)){QueuePush(&obj->q1,x);}else{QueuePush(&obj->q2,x);}
}int myStackPop(MyStack* obj) {Que* Empty=&obj->q1;Que* NoEmpty=&obj->q2;if(!IsEmpty(&obj->q1)){Empty=&obj->q2;NoEmpty=&obj->q1;}while(QueueSize(NoEmpty)>1){QueuePush(Empty,QueueFront(NoEmpty));QueuePop(NoEmpty);}int top=QueueFront(NoEmpty);QueuePop(NoEmpty);return top;
}int myStackTop(MyStack* obj) {if(!IsEmpty(&obj->q1)){return QueueBlack(&obj->q1);}else{return QueueBlack(&obj->q2);}
}bool myStackEmpty(MyStack* obj) {return (IsEmpty(&obj->q1)&&IsEmpty(&obj->q2));
}void myStackFree(MyStack* obj) {DestoryQueue(&obj->q1);DestoryQueue(&obj->q2);free(obj);
}

---

?

總結

? ? ? ? 本文隊列模擬實現棧，讓我們在實踐中深入思考了數據結構的本質和應用，為我們的編程能力和問題解決能力提供了鍛煉。本期內容到此結束，感謝閱讀！