这时一道非常经典的题型，因为栈和队列的性质是相反的，队列的数据是先入先出，栈的数据是后入先出，那么怎样使用两个队列实现栈呢？
这是题目的要求，如果使用C语言来实现的话，只能自己写一个队列了，这里我就不详细讲解了
代码如下：
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) { assert(pq); pq->size = 0; pq->head = pq->tail = NULL; } 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* tmp = (QNode*)malloc(sizeof(QNode)); if (tmp == NULL) { perror("malloc fail"); exit(-1); } tmp->data = x; tmp->next = NULL; if (pq->tail == NULL) { pq->head = pq->tail = tmp; } else { pq->tail->next = tmp; pq->tail = tmp; } pq->size++; } void QueuePop(Que* pq) { assert(pq); assert(pq->head); 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(pq->head); return pq->head->data; } QDataType QueueBack(Que* pq) { assert(pq); assert(pq->head); return pq->tail->data; } bool QueueEmpty(Que* pq) { assert(pq); return pq->head == NULL; } int QueueSize(Que* pq) { assert(pq); return pq->size; }
实现思路：
在实现这个栈之前我们需要有一个具体思路，栈是后进先出，队列是先进后出，那么在插入上是没有区别的，在删除上就需要将对列的尾部删除，那么如何实现对列的尾部删除呢？这就需要将其中一个对列nonempty的数据导入到另一个对列empty，直到nonempty只剩一个数据，然后头删即可。
删除之后将nonempty和empty互换即可，必须保证其中一个队列为空。
1.栈的定义
题目要求是使用两个队列实现栈，那么就直接在栈的定义里面包含两个队列即可。
typedef struct { Que q1; Que q2; } MyStack;
2.栈的初始化
为栈malloc一块空间，在使用QueueInit实现两个队列的初始化。
MyStack* myStackCreate() { MyStack* obj=(MyStack*)malloc(sizeof(MyStack)); QueueInit(&obj->q1); QueueInit(&obj->q2); return obj; }
3.数据入栈
数据入栈需要将数据push到不为空的那个队列，使用QueueEmpty判断队列是否为空，再使用QueuePush尾插数据。
void myStackPush(MyStack* obj, int x) { if(!QueueEmpty(&obj->q1)) { QueuePush(&obj->q1,x); } else { QueuePush(&obj->q2,x); } }
4.数据出栈
这个是题目的难点，创建两个变量分别为nonempty(非空队列)和empty(空队列），在使用if判断q1和q2哪个为空。使用while循环来实现遍历插入和删除，结束条件为nonempty内的数据为1，也就是队列的尾部数据，在循环内使用QueuePush将nonempty的头部数据插入到empty，每次插入之后要删除掉原节点。到这里还需要注意的是，题目要求返回这个数据，所以要创建一个变量返回这个数据，最后再删除掉，始终保存一个队列为空。
int myStackPop(MyStack* obj) { Que* empty=&obj->q1; Que* nonempty=&obj->q2; if(!QueueEmpty(&obj->q1)) { nonempty=&obj->q1; empty=&obj->q2; } else { nonempty=&obj->q2; empty=&obj->q1; } //将前size-1个元素导入空队列 while(QueueSize(nonempty)>1) { QueuePush(empty,QueueFront(nonempty)); QueuePop(nonempty); } int ret= QueueFront(nonempty); QueuePop(nonempty); return ret; }
5.取栈顶数据
栈顶数据也就是队列的尾部数据，使用QueueBack直接取nonempty的尾部数据即可。
int myStackTop(MyStack* obj) { if(!QueueEmpty(&obj->q1)) { return QueueBack(&obj->q1); } else { return QueueBack(&obj->q2); } }
6.判断栈是否为空
栈由两个队列组成，直接使用QueueEmpty判断两个队列是否为空即可，配合&&，必须两个都为空才返回true。
bool myStackEmpty(MyStack* obj) { return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2); }
7.毁栈销
使用QueueDestroy销毁掉两个队列，再free掉栈的空间即可。
void myStackFree(MyStack* obj) { QueueDestroy(&obj->q1); QueueDestroy(&obj->q2); free(obj); }
完整代码 ：
typedef struct { Que q1; Que q2; } MyStack; MyStack* myStackCreate() { MyStack* obj=(MyStack*)malloc(sizeof(MyStack)); QueueInit(&obj->q1); QueueInit(&obj->q2); return obj; } 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)) { nonempty=&obj->q1; empty=&obj->q2; } else { nonempty=&obj->q2; empty=&obj->q1; } //将前size-1个元素导入空队列 while(QueueSize(nonempty)>1) { QueuePush(empty,QueueFront(nonempty)); QueuePop(nonempty); } int ret= QueueFront(nonempty); QueuePop(nonempty); return ret; } 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); }
今天的分享到这里就结束啦！谢谢老铁们的阅读，让我们下期再见。
