題目：用隊(duì)列實(shí)現(xiàn)棧

思路

隊(duì)列的特點(diǎn)是先進(jìn)先出，而棧的特點(diǎn)是后進(jìn)先出。所以想要用隊(duì)列實(shí)現(xiàn)模擬棧，我們可以使用兩個隊(duì)列，一個隊(duì)列負(fù)責(zé)壓棧，一個隊(duì)列負(fù)責(zé)出棧。壓棧很簡單就是檢空再調(diào)用隊(duì)列的push就好，那出棧呢？這里可以利用另外一個空隊(duì)列，先把一部分?jǐn)?shù)據(jù)給空隊(duì)列，原來的隊(duì)列只保留最后一個數(shù)據(jù)就好，這時再對這個隊(duì)列出棧，再Pop掉。始終保持一個隊(duì)列有數(shù)據(jù)，一個隊(duì)列為空。兩個隊(duì)列相互交換數(shù)據(jù)，達(dá)到模擬實(shí)現(xiàn)棧的效果。

這里的結(jié)構(gòu)實(shí)際就是一個套娃，棧包含隊(duì)列，隊(duì)列里包含鏈表

具體實(shí)現(xiàn)

首先手搓一個隊(duì)列，如果是其他語言也可以直接調(diào)用庫，這里是用c語言。接著實(shí)現(xiàn)題目給的函數(shù)。

myStackCreate

MyStack* myStackCreate() {MyStack* pst=(MyStack*)malloc(sizeof(MyStack));if(pst==NULL){perror("Malloc Failed\n");return NULL;}QueueInit(&pst->q1);QueueInit(&pst->q2);return pst;
}

這里創(chuàng)建棧要想清楚結(jié)構(gòu)，有三層，其中兩層你已經(jīng)再隊(duì)列里完成。所以，這里我們還需要再創(chuàng)建一個棧，動態(tài)開辟一個指針，用這個指針來維護(hù)棧和實(shí)現(xiàn)各種功能

myStackPush

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

這里壓棧還是比較簡單，首先檢查一下隊(duì)列是否為空，如果為空就入隊(duì)另一個隊(duì)列。當(dāng)然剛開始入隊(duì)，兩個都為空。所以在檢查完一個隊(duì)列為空后，直接就入隊(duì)到另一個隊(duì)列就行了。不用再多余判斷了。

myStackPop

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

這里出棧是有點(diǎn)復(fù)雜，設(shè)計(jì)到兩個隊(duì)列相互轉(zhuǎn)化。所以，為了邏輯清晰。我們直接創(chuàng)建兩個新隊(duì)列，分別命名為empty和nonempty。這樣容易區(qū)分，不容易邏輯混亂。

這里我們可以直接選擇一個隊(duì)列賦值給empty，另一個隊(duì)列賦值給nonempty。在進(jìn)行檢空，如果不對，在進(jìn)行交換就行。接下來就是依次出隊(duì)，把頭部元素依次入隊(duì)到empty,依次Pop nonempty隊(duì)列。當(dāng)只剩一個數(shù)據(jù)，循環(huán)停止。退出循環(huán)后，把剩余的數(shù)據(jù)出隊(duì)，Pop隊(duì)列，返回。這樣就實(shí)現(xiàn)了后進(jìn)先出的效果。

myStackTop

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

這里可以檢空再調(diào)用QueueBack，這里也把這個函數(shù)體現(xiàn)的淋漓盡致。雖然，從隊(duì)列定義看，這個函數(shù)是不合理的。但是這個函數(shù)，再很多地方都會用到。所以我們不妨寫一下。c++STL中就也有這個函數(shù)。

myStackEmpty

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

這里返回的是兩個隊(duì)列的檢空，因?yàn)檫@個棧是由這兩兩個隊(duì)列實(shí)現(xiàn)的

myStackFree

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

這里釋放，可不能直接free棧。我們這里隊(duì)列還需要一個一個釋放。如果你直接釋放掉棧，那就會內(nèi)存泄漏。所以我們先調(diào)用下隊(duì)列的銷毀函數(shù)把兩個隊(duì)列釋放掉,再free棧，最后記得置空

代碼

typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;
typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;
void QueueInit(Queue* pq);
//銷毀隊(duì)列
void QueueDestroy(Queue* pq);
//隊(duì)尾入隊(duì)列
void QueuePush(Queue* pq, QDataType x);
//隊(duì)頭出隊(duì)列
void QueuePop(Queue* pq);
//獲取隊(duì)列頭部yuansu
QDataType QueueFront(Queue* pq);
//獲取隊(duì)列尾部元素
QDataType QueueBack(Queue* pq);
//獲取隊(duì)列中有效數(shù)據(jù)個數(shù)
int QueueSize(Queue* pq);
//檢測隊(duì)列是否為空（檢空）
bool QueueEmpty(Queue* pq);
void QueueInit(Queue* pq)
{pq->head = pq->tail = NULL;pq->size = 0;
}
void QueueDestroy(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;
}
void QueuePush(Queue* pq, QDataType x)
{QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("Malloc Failed\n");return;}newnode->next = NULL;newnode->data = x;if (pq->head == NULL){assert(pq->tail == NULL);pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}
void QueuePop(Queue* pq)
{assert(pq);assert(pq->head != NULL);/*QNode* next = pq->head->next;free(pq->head);pq->head = next;if (pq->head == NULL){pq->tail = NULL;}*/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(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack* pst=(MyStack*)malloc(sizeof(MyStack));if(pst==NULL){perror("Malloc Failed\n");return NULL;}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) {Queue* empty=&obj->q1;Queue* nonempty=&obj->q2;if(!QueueEmpty(&obj->q1)){empty=&obj->q2;nonempty=&obj->q1;}while(QueueSize(nonempty) > 1){QueuePush(empty,QueueFront(nonempty));QueuePop(nonempty);}int ret=QueueFront(nonempty);QueuePop(nonempty);return ret;
}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);obj=NULL;
}/*** 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é)

這里復(fù)雜的主要是結(jié)構(gòu)，在具體的函數(shù)實(shí)現(xiàn)上，如果你思路清晰，其實(shí)是比較簡單的。比較復(fù)雜的就是，出棧這個函數(shù)，需要多想一下

題目鏈接：225. 用隊(duì)列實(shí)現(xiàn)棧 - 力扣（LeetCode）