前言
我们已经学习了栈和队列，也都实现了它们各自的底层接口，那么接下我们就要开始栈和队列的专项刷题训练。
1. 题目：使用队列实现栈
题目描述：
题目链接：
2. 思路
队列的结构是先进先出，题目的要求是，让我们利用队列的底层接口来实现栈，不可以改变队列的底层逻辑，所以如果你的思路是逆置队列这个链表，那这个思路就被pass掉了。
那我们要如何利用队列尾进头出的特性来实现栈的尾进尾出呢？题目中给了我们两个队列，我们要使用这两个队列实现栈。
入栈操作好说，问题在于出栈问题，思路是这样的：我们有两个队列，一个队列用于存储数据，另外一个队列（空队列）用于拷贝数据，将原队列的前n-1个数据拷贝到空队列中，然后再将原队列剩余的最后一个元素出队列，这样就模拟实现了栈的尾出。
3. 分析
根据上述的思路分析，队列实现栈，入栈不需要什么特殊操作例如我们入栈：1、2、3、4、5，出栈呢就是：5、4、3、2、1。
上述的思路已经介绍了解决办法，也是非常简单的，但有人可能会问：那这样算法的效率岂不是很低？这种方法的效率确实低，但是这道题目考察的并不是效率的问题，而实性质问题，这也是一道经典的面试题目。这道题目并不难，但它考察对数据结构的理解，各各接口的实现中有很多需要注意的细节。
首先这道题目是并没有给现成的队列，使用C语言解决需要我们现成造轮子，这也是C语言刷题的弊端，有很多题目都需要造轮子。那么这里我们就可以直接复制前边我们实现的队列。
接下来就是我们开始注意实现接口：
首先题目中给了我们两个队列，为了便于传参和使用，我们可以定义一个结构体：
typedef struct { Que q1; //注意这里定于的队列类型一定要与自己定义的队列结构体类型对应 Que q2; } MyStack;
这里我们在前边介绍结构体时提到过，匿名结构体。
3.1 创建栈
MyStack* myStackCreate() { }
题目给出的接口如上，那这里我们要怎么创建我们的栈呢？是这样吗？
MyStack* myStackCreate() { MyStack st; //… return &st; }
对函数和指针比较熟悉的同学可能就已经发现不行，为什么不行？这里就牵扯到了函数相关的知识，函数内创建的变量都是存储在栈区，出了函数就会被销毁，内存已经被销毁，返回指针还有什么意义呢？所以这里需要使用malloc函数，动态内存分配开辟的空间在堆区，程序结束前不主动释放就一直存在。所以上述的创建变量的方法不可取。
正确的方法：
MyStack* myStackCreate() { MyStack* pst=(MyStack*)malloc(sizeof(MyStack)); QueueInit(&pst->q1); QueueInit(&pst->q2); return pst; }
这里的pst->q1,就等价于我们在创建的队列的结构体变量：Que q；在调用接口时需要传地址过去。
3.2入栈
接下来就是入栈，题目中给了我们两个队列，为了后续出栈操作我们需要确保一个队列为空，用于拷贝数据，所以我们入栈时需要在不为空的队列入。
void myStackPush(MyStack* obj, int x) { if(!IsEmpty(&obj->q1)) { QueuePush(&obj->q1,x); } else { QueuePush(&obj->q2,x); } }
如果两个都为空那就随便选一个都可以。
3.3 出栈
在进行出栈操作的时候，我们需要判断哪一个队列为空，然后将非空队列的前n-1个元素依次拷贝到空队列当中。这里我们可以先假设队列1为空，然后在判断队列1是否为空，如果不为空那就是队列2为空，进行修改。这个假设的方法还是很实用的。
拷贝过程如下：
注意这里是拷贝，不是将原队列的节点插入到空队列，而是通过队头数据这个函数接口来将数据传过去，然后入队（调用入队接口），入队之后及时更新队头（出队）。
int myStackPop(MyStack* obj) { Que* Empty=&obj->q1; Que* NoEmpty=&obj->q2; if(!IsEmpty(&obj->q1)) { Empty=&obj->q2; NoEmpty=&obj->q1; } while(QueueSize(NoEmpty)>1) { QueuePush(Empty,QueueFront(NoEmpty)); QueuePop(NoEmpty); } int top=QueueFront(NoEmpty);//最后保存非空队列最后一个队列节点的数据，便于返回 QueuePop(NoEmpty); //最后一个元素出队。 return top; }
3.4 栈顶数据
栈顶数据接口实现就简单了，我们前边对队列进行实现时，有队头和队尾数据的接口，我们可以直接调用。
int myStackTop(MyStack* obj) { if(!IsEmpty(&obj->q1)) { return QueueBlack(&obj->q1); } else { return QueueBlack(&obj->q2); } }
3.5 判空和 “ 栈 ” 的销毁
判空就很简单，如果两个队列都为空，那么这个 “ 栈 ” 也就为空。
bool myStackEmpty(MyStack* obj) { return (IsEmpty(&obj->q1)&&IsEmpty(&obj->q2)); }
“ 栈 ”的销毁，这里就不能直接free掉obj了，如果直接释放那我们程序中的两个队列就会丢失无法释放，所以在释放掉obj之前，我们需要先将两个队列销毁。
void myStackFree(MyStack* obj) { DestoryQueue(&obj->q1); DestoryQueue(&obj->q2); free(obj); }
4. 题解
完整代码如下：
typedef int Datatype; typedef struct QueueNode { struct QueueNode* next; Datatype data; }QueueNode; typedef struct Queue { QueueNode* head; QueueNode* tail; int size; }Que; //初始化队列 void QueueInit(Que* pq); //入队 void QueuePush(Que* pq, Datatype x); //出队 void QueuePop(Que* pq); //队头数据 Datatype QueueFront(Que* pq); //队尾数据 Datatype QueueBlack(Que* pq); //判空 bool IsEmpty(Que* pq); //队列大小 int QueueSize(Que* pq); //销毁队列 void DestoryQueue(Que* pq); void QueueInit(Que* pq) { assert(pq); pq->head = pq->tail = NULL; pq->size = 0; } void QueuePush(Que* pq, Datatype x) { assert(pq); QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); if (newnode == NULL) { perror("malloc"); 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(!IsEmpty(pq)); if (pq->head->next == NULL) { free(pq->head); pq->head = pq->tail = NULL; } else { QueueNode* next = pq->head->next; free(pq->head); pq->head = next; } pq->size--; } Datatype QueueFront(Que* pq) { assert(pq); assert(!IsEmpty(pq)); return pq->head->data; } Datatype QueueBlack(Que* pq) { assert(pq); assert(!IsEmpty(pq)); return pq->tail->data; } bool IsEmpty(Que* pq) { assert(pq); return (pq->head == NULL); } int QueueSize(Que* pq) { assert(pq); return pq->size; } void DestoryQueue(Que* pq) { assert(pq); QueueNode* cur = pq->head; while (cur) { QueueNode* next = cur->next; free(cur); cur = next; } pq->head = pq->tail = NULL; pq->size = 0; } 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(!IsEmpty(&obj->q1)) { QueuePush(&obj->q1,x); } else { QueuePush(&obj->q2,x); } } int myStackPop(MyStack* obj) { Que* Empty=&obj->q1; Que* NoEmpty=&obj->q2; if(!IsEmpty(&obj->q1)) { Empty=&obj->q2; NoEmpty=&obj->q1; } while(QueueSize(NoEmpty)>1) { QueuePush(Empty,QueueFront(NoEmpty)); QueuePop(NoEmpty); } int top=QueueFront(NoEmpty); QueuePop(NoEmpty); return top; } int myStackTop(MyStack* obj) { if(!IsEmpty(&obj->q1)) { return QueueBlack(&obj->q1); } else { return QueueBlack(&obj->q2); } } bool myStackEmpty(MyStack* obj) { return (IsEmpty(&obj->q1)&&IsEmpty(&obj->q2)); } void myStackFree(MyStack* obj) { DestoryQueue(&obj->q1); DestoryQueue(&obj->q2); free(obj); }
总结
本文队列模拟实现栈，让我们在实践中深入思考了数据结构的本质和应用，为我们的编程能力和问题解决能力提供了锻炼。本期内容到此结束，感谢阅读！
