一.题目

用两个队列实现一个栈

二.相关知识点

1.区别与联系

相同点：
（1）栈和队列均为控制访问点的线性表；

（2）栈和队列都允许在端点处进行数据的插入和删除；

不同点：
（1）栈遵循“后进先出（LIFO）”的原则，只能在栈顶进行数据的插入和删除，实现栈时用顺序表比较好；

（2）队列遵循“先进先出（FIFO）”的原则，只能在队列的尾部插入元素，头部删除元素，实现队列时用链表比较好。

这里就不给大家详细赘述了，详细的栈和队列知识点在前面的博客里也写过链接如下：

栈相关知识点: link.

队列相关知识点：link.

三.题目分析

看到这个题，我们就要想到栈和队列的不同，由于栈的性质是“后进先出”的，用两个队列模拟实现栈的时候就需要两个队列的元素进行互通，来实现栈的这一特性；所以我们定义两个队列分别为q1和q2。

四.图解说明及操作规则

图（1）：当栈里面插入元素“abcd”的时候，元素a在栈底（最后出去），d在栈顶（最先出去）；

图（2）：将元素“abc”从q1中头删，然后再q2中尾插进来之后，头删q1中的元素“d”，就相当于实现了栈顶元素的出栈；

图（3）：同理，将元素“ab”从q2中头删，然后尾插到q1中，然后再头删q2中的元素“c”;

图（4）：同理，删除元素“b”;

图（5）：当栈又插入一个元素“e”时，此时元素“a”不能从队列中删除，而是将元素“a”插入q2中，再删除q1中的元素“e”,最后再删除元素“a”。

说明：其中红色框代表该队列中的元素出队列，该队列为空。

规则：

如何入栈：
直接向q2里边入
如何出栈：
如果q2不空，将q2除了最后一个数据外，剩余数据放到q1里，这时候q2仅仅剩下一个数据，这时候就可以出来
如果q2为空，代表着值都在q1里，将q1除了最后一个数据外，剩余数据放到q2里，这时候q1仅剩下一个数据，这时候可以出来。

五.完整代码

代码如下：

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include "2022.3.7 两个队实现栈.h"//初始化
void my_Init_two_queue_stack(struct Two_queue_stack* tqs)
{Init_LQueue(&tqs->q1);Init_LQueue(&tqs->q2);
}//入栈
bool my_Push(PTwo_queue_stack tqs, ELEM_TYPE val)
{return Push(&tqs->q2, val);
}//出栈（还需要一个输出参数，帮助我将出队的值带出来）
bool my_Pop(PTwo_queue_stack tqs, ELEM_TYPE* rtval)
{//assertif (my_IsEmpty(tqs))//确保了自己模拟实现的这个栈里面一定有值，要么在左边，要么在右{return false;}if (!IsEmpty(&tqs->q2))//q2不空  直接出（仅剩下一个元素，其他的全部挪到另一边）{int len = Get_length(&tqs->q2);while (len > 1){ELEM_TYPE tmp;Pop(&tqs->q2, &tmp);Push(&tqs->q1, tmp);len--;}return Pop(&tqs->q2, rtval);}else//q2为空  确定值都在q1里面{int len = Get_length(&tqs->q1);while (len > 1){ELEM_TYPE tmp;Pop(&tqs->q1, &tmp);Push(&tqs->q2, tmp);len--;}return Pop(&tqs->q1, rtval);}}//获取栈顶元素值（还需要一个输出参数，帮助我将出队的值带出来）
bool my_Top(PTwo_queue_stack tqs, ELEM_TYPE* rtval)
{//assertif (my_IsEmpty(tqs))//确保了自己模拟实现的这个栈里面一定有值，要么在左边，要么在右{return false;}if (!IsEmpty(&tqs->q2))//q2不空  直接出（仅剩下一个元素，其他的全部挪到另一边）{int len = Get_length(&tqs->q2);while (len > 1){ELEM_TYPE tmp;Pop(&tqs->q2, &tmp);Push(&tqs->q1, tmp);len--;}Pop(&tqs->q2, rtval);Push(&tqs->q1, *rtval);return true;}else//q2为空  确定值都在q1里面{int len = Get_length(&tqs->q1);while (len > 1){ELEM_TYPE tmp;Pop(&tqs->q1, &tmp);Push(&tqs->q2, tmp);len--;}Pop(&tqs->q1, rtval);Push(&tqs->q2, *rtval);return true;}
}//判空
bool my_IsEmpty(PTwo_queue_stack tqs)
{if (IsEmpty(&tqs->q1) && IsEmpty(&tqs->q2)){return true;}return false;
}//有效元素个数
int my_Get_length(PTwo_queue_stack tqs)
{return Get_length(&tqs->q1) + Get_length(&tqs->q2);
}//打印
void my_Show(PTwo_queue_stack tqs)
{Show(&tqs->q1);Show(&tqs->q2);
}//清空
void my_Clear(PTwo_queue_stack tqs)
{Clear(&tqs->q1);Clear(&tqs->q2);
}//销毁
void my_Destroy(PTwo_queue_stack tqs)
{Destroy(&tqs->q1);Destroy(&tqs->q2);
}