我们上篇文章讲述了用两个栈实现队列 ，用过对上篇文章的学习后，我们再去学用两个队列实现栈就变得相对来说容易了很多。本篇文章会对用两个队列实现栈进行详解，希望会对你有所帮助。
一、队列实现栈的特点分析
1、1 具体分析
队列和栈在插入数据时，队列是从队尾进行插入，栈是从栈顶插入。但是他们的删除数据是不同的。我们知道队列的特点是：先新先出 ，删除数据是在对头进行删除，栈的特点是：先进后出，也就是在栈顶进行删除。
当我们用队列实现栈时，最根本的也是最重要的是需要解决删除的问题。我们用队列实现栈时，在队列中的删除就不是删除对头的元素了，我们需要根据栈的特点进行删除，也就是我们需要删除的是队尾的元素。
操作时，首先我们先往队列中插入元素。注意，我们插入元素时，应该往不为空的队列中插入元素，如果两个队列都为空，我们可以随意往一个队列中插入元素。为什么要往不为空的队列中插入元素呢？我们先接着往下看。我们是用队列模拟栈，此时我们想要删除的是栈顶的元素，也就是队尾的元素。我们需要把前size-1个元素移动到另一个空的对列中，然后再删除队列中的最后一个元素，也就是队尾元素。
这也是我们为什么插入元素时要往不为空的队列中插入的原因。因为我们需要一个空的队列进行来回导元素，从而达到删除队尾元素的目的。这时，插入操作和删除操作我们都是可以用队列去模拟实现出栈的效果了。插入和删除重复上面的操作就可以。
1、2 整体概括
通过我们上面的分析，用队列模拟实现栈和用栈模拟队列的思路大同小异。我们看用队列模拟栈的整体思路：
插入时往不为空的队列插入。第一次插入时，两个队列都为空，此时随便插入一个队列即可。
删除时，需要把不为空的队列中的元素前size-1个元素导入到空队列中。然后再删除剩下的一个元素。
返回栈顶的元素，也就是返回队尾的元素。
二、队列模拟实现栈代码的实现
我们这里用c语言实现，所以还要手撕一个队列的代码。当然C++容器中，有队列，可以直接用。大家熟悉思路后，可以用其它语言做一下本题，OJ链接：用队列实现栈 - OJ链接（LeetCode）。
2、1 手撕 队列 代码
queue.h
typedef int QDataType; typedef struct QNode { struct QNode* next; QDataType data; }QNode; typedef struct Queue { QNode* head; QNode* tail; int size; }Queue; void QueueInit(Queue* pq); void QueueDestory(Queue* pq); void QueuePush(Queue* pq, QDataType x); void QueuePop(Queue* pq); QDataType QueueFront(Queue* pq); QDataType QueueBack(Queue* pq); bool QueueEmpty(Queue* pq); int QueueSize(Queue* pq);
queue.c
void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; pq->size = 0; } void QueueDestory(Queue* 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(Queue* pq, QDataType x) { assert(pq); QNode* tmp = (QNode*)malloc(sizeof(QNode)); if (tmp == NULL) { perror("malloc failed"); exit(-1); } tmp->next = NULL; tmp->data = x; if (pq->head == pq->tail && pq->head == NULL) { pq->head = pq->tail = tmp; } else { pq->tail->next = tmp; pq->tail = tmp; } pq->size++; } void QueuePop(Queue* pq) { assert(pq); assert(pq->head != NULL); 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--; }
2、2 用队列模拟实现栈代码
typedef int QDataType; typedef struct QNode { struct QNode* next; QDataType data; }QNode; typedef struct Queue { QNode* head; QNode* tail; int size; }Queue; void QueueInit(Queue* pq); void QueueDestory(Queue* pq); void QueuePush(Queue* pq, QDataType x); void QueuePop(Queue* pq); QDataType QueueFront(Queue* pq); QDataType QueueBack(Queue* pq); bool QueueEmpty(Queue* pq); int QueueSize(Queue* pq); void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; pq->size = 0; } void QueueDestory(Queue* 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(Queue* pq, QDataType x) { assert(pq); QNode* tmp = (QNode*)malloc(sizeof(QNode)); if (tmp == NULL) { perror("malloc failed"); exit(-1); } tmp->next = NULL; tmp->data = x; if (pq->head == pq->tail && pq->head == NULL) { pq->head = pq->tail = tmp; } else { pq->tail->next = tmp; pq->tail = tmp; } pq->size++; } void QueuePop(Queue* pq) { assert(pq); assert(pq->head != NULL); 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(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->head->data; } QDataType QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->tail->data; } bool QueueEmpty(Queue* pq) { assert(pq); return pq->size == 0; } int QueueSize(Queue* pq) { assert(pq); return pq->size; } typedef struct { Queue q1; Queue q2; } MyStack; MyStack* myStackCreate() { MyStack* st=(MyStack*)malloc(sizeof(MyStack)); if(st==NULL) return false; QueueInit(&st->q1); QueueInit(&st->q2); return st; } void myStackPush(MyStack* obj, int x) { if(QueueSize(&obj->q1)!=0) { QueuePush(&obj->q1,x); } else { QueuePush(&obj->q2,x); } } int myStackPop(MyStack* obj) { Queue* tmp=&obj->q1; Queue* notmp=&obj->q2; if(QueueSize(notmp)==0) { tmp=&obj->q2; notmp=&obj->q1; } while(QueueSize(notmp)>1) { QueuePush(tmp,QueueFront(notmp)); QueuePop(notmp); } QDataType res=QueueFront(notmp); QueuePop(notmp); return res; } int myStackTop(MyStack* obj) { if(QueueSize(&obj->q1)!=0) return QueueBack(&obj->q1); else return QueueBack(&obj->q2); } bool myStackEmpty(MyStack* obj) { return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2); } void myStackFree(MyStack* obj) { QueueDestory(&obj->q1); QueueDestory(&obj->q2); free(obj); }
三、总结
以上就是整个用队列模拟实现栈的整个过程，主要是利用空队列删除队尾的元素。我们应该熟练掌握用队列模拟实现栈和用栈模拟实现队列，两者都是面试中的高频题目。本篇文章的讲解就到这里，希望以上对容对对你有所帮助，感谢阅读ovo~
