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