題目一 用隊列實現棧

請你僅使用兩個隊列實現一個后入先出（LIFO）的棧，并支持普通棧的全部四種操作（push、top、pop 和 empty）。

實現 MyStack 類：

void push(int x) 將元素 x 壓入棧頂。
int pop() 移除并返回棧頂元素。
int top() 返回棧頂元素。
boolean empty() 如果棧是空的，返回 true ；否則，返回 false 。

注意：

你只能使用隊列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 這些操作。
你所使用的語言也許不支持隊列。 你可以使用 list （列表）或者 deque（雙端隊列）來模擬一個隊列 , 只要是標準的隊列操作即可。

來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/implement-stack-using-queues

?

我們先來分析下題目

要求用兩個隊列實現一個棧 并且實現四種操作

我們來看第一個Push操作

棧的特點是什么？ 先進后出

隊列的特點是什么？ 先進先出

來看圖

有思路了?

圖上是兩個隊列

我們假設 注意啊 是假設

第一行的圖 它就是一個棧

那么我們可以判斷出 它的數據插入順序就是 1 2 3 4?

這個時候隊列的頭就是棧的尾

如果我們這個時候需要刪除棧的頭數據應該怎么辦呢？

我們都知道隊列的數據只能是從頭開始出

也就是說 比如要將隊列前面的1 2 3 全部出完之后才能開始出 4

但是我們不可能會拋棄之前的數據啊

這個時候我們就想到了第二個隊列的用處了

只需要將我Pop的數據使用第二個隊列來接受就可以

實現起來的圖大概是這樣子

?

這個時候我們就能刪除掉頭數據了

如果需要再刪除一個怎么辦呢？

那么只需要將上面的操作再重復一次就好了

這個時候的插入數據只需要往不為空的隊列插入數據就可以了

要求首元素就是返回隊列的尾

要求尾元素就是返回隊列的頭

也就是兩個步驟

1.保持一個隊列為空，一個隊列存數據

2.出棧，把前面的數據倒入空隊列

接下來我們來實現代碼

把所有的隊列代碼以及接口函數拷貝進去

第一步?定義結構體

我們來看這個 我們應該怎么定義我們的Stack結構體呢？

既然是兩個隊列的實現的

那么是不是可以放兩個隊列的結構在里面？

仔細一想好像可行

我們來試試

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

畫個圖方便大家理解

三個結構體的關系一目了然

?第二步 實現創建（初始化）

MyStack* myStackCreate() {MyStack*pst = ( MyStack*)malloc(sizeof( MyStack));if(pst==NULL){perror("malloc fail");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*emptyQ = &obj->q1;Queue*nonemptyQ = &obj->q2;if(!QueueEmpty(&obj->q1)){emptyQ = &obj->q2;nonemptyQ=&obj->q1;}//倒數據while(QueueSize(nonemptyQ)>1){QueuePush(emptyQ,QueueFront(nonemptyQ));QueuePop(nonemptyQ);}//記錄刪除值 刪掉int top = QueueFront(nonemptyQ);QueuePop(nonemptyQ);return top;
}

第五步?返回頭的值

這里我們可以分兩種情況討論

如果1不為空就返回1的尾值

如果2不為空就返回2的尾值

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

第六步 判空

這步就很簡單，只需要判斷1和2是否都為空，都為空即空

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

第七步 釋放

這里要依次釋放銷毀，類似套娃

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

源碼

typedef int QDateType;
typedef struct QueueNode
{struct QueueNode* next;QDateType date;
}QNode;
typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;
//初始化
void QueueInit(Queue* pq);
//銷毀
void QueueDestroy(Queue* pq);
//隊進
void QueuePush(Queue* pq, QDateType x);
//隊出
void QueuePop(Queue* pq);
//判斷為空
bool QueueEmpty(Queue* pq);
//個數
int QueueSize(Queue* pq);
//隊尾
QDateType QueueBack(Queue* pq);
//對頭
QDateType QueueFront(Queue* pq);
//初始化
void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}
//銷毀
void QueueDestroy(Queue* pq)
{assert(pq);//兩個結構體依次銷毀 先銷毀QNodeQNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}//再置空Queuepq->head = pq->tail = NULL;pq->size = 0;
}
//隊進
void QueuePush(Queue* pq, QDateType x)
{assert(pq);//開辟新節點QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return;}//賦值newnode->next = NULL;newnode->date = x;//判斷是否為空if (pq->head == 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);//只有一個節點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--;
}
//判斷為空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}
//大小
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}
//隊尾
QDateType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->date;
}
//對頭
QDateType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->date;
}typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack*pst = ( MyStack*)malloc(sizeof( MyStack));if(pst==NULL){perror("malloc fail");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*emptyQ = &obj->q1;Queue*nonemptyQ = &obj->q2;if(!QueueEmpty(&obj->q1)){emptyQ = &obj->q2;nonemptyQ=&obj->q1;}//倒數據while(QueueSize(nonemptyQ)>1){QueuePush(emptyQ,QueueFront(nonemptyQ));QueuePop(nonemptyQ);}//記錄刪除值 刪掉int top = QueueFront(nonemptyQ);QueuePop(nonemptyQ);return top;
}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);
}

以上便是本文所有內容了，如有錯誤請各位大佬不吝賜教，感謝留言