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);
*/
