1.前言?
通過前面隊列的實現和詳解大家對隊列應該有一定熟悉了，現在上強度開始做題吧
隊列詳解：http://t.csdnimg.cn/dvTsW
2.OJ題目訓練225. 用隊列實現棧
題目分析
請你僅使用兩個隊列實現一個后入先出（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（雙端隊列）來模擬一個隊列?, 只要是標準的隊列操作即可。
顧名思義，題目很好理解，那么該如何用隊列實現棧呢，單純用一個隊列，那完全是不可能實現棧的，那么我們就要思考如果多一個隊列可不可以實現：
方法
如圖是兩個隊列和一個棧按順序放入數據（1，2，3，4）
如果要實現棧，那么我們第一個拿出的數據就應該是4（后進先出），而如果是隊列，第一個拿出的數據則是1（先進先出）
所以我們應該利用好q2（第二個隊列）來實現棧相同的效果，實現可以把除4（最后放入隊列的數），其他數均放置入q2。
再把q1的4給輸出，就能達到棧的效果了
最后輸出q1滯空，這樣實現一個空隊列，一個非空隊列來進行不斷的交換傳輸數據
注意要點
- 本題目需要借助原本以寫過的代碼來進行完成，所以請優先查看本文頭部的隊列教學
- 兩個隊列應該明確好：空隊列輸入數據，非空輸出數據
附源代碼
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue //由于每次操作的函數都需要傳遞頭和尾指針，所以直接封裝更方便
{QNode* head;QNode* tail;int size;
}Que;void QueueInit(Que* pq);
void QueueDestroy(Que* pq);
void QueuePush(Que* pq, QDataType x);
void QueuePop(Que* pq);
QDataType QueueFront(Que* pq);
QDataType QueueBack(Que* pq);
bool QueueEmpty(Que* pg);
int QueueSize(Que* pg);void QueueInit(Que* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;}void QueueDestroy(Que* 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(Que* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");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(!QueueEmpty(pq));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(Que* pq) //頭出
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}QDataType QueueBack(Que* pq) //尾出
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;}
bool QueueEmpty(Que* pq)
{assert(pq);return pq->head == NULL;}
int QueueSize(Que* pq)
{assert(pq);return pq->size;
}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(!QueueEmpty(&obj->q1)){QueuePush(&obj->q1,x);}else{QueuePush(&obj->q2,x);}
}int myStackPop(MyStack* obj)
{Que* empty = &obj->q1;Que* nonEmpty = &obj->q2;if(!QueueEmpty(&obj->q1)){empty = &obj->q2;nonEmpty = &obj->q1;}while(QueueSize(nonEmpty)>1) //把非空隊列的對頭導入空隊列{QueuePush(empty,QueueFront(nonEmpty)); //將非空的隊列值轉移到空隊列中QueuePop(nonEmpty);}int top = QueueFront(nonEmpty); //取出頭數據再刪除QueuePop(nonEmpty);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);
}/*** 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);
*/
