两个队列实现栈
. - 力扣（LeetCode）
如何用两个队列实现栈的操作呢？
弹出
我们知道栈的特点是后进先出，而队列的特点是先进先出。如何用两个队列实现数据的先进后出。首先我们先抽象一个一个栈用来思考我们该怎么实现
我们先假设栈中插入了五个数据，五个数据都放在队列 q1 中。
当我们要 pop 数据时，由于栈是后进先出的，所以删除的数据是 5 ，而5在队列中又是后插入的，这时候我们就要想办法让 5 到 q1 的队头去，好像除了把前面的四个数据挪到 q2 中也没其他的办法了。于是我们重复取 q1 对头数据尾插到 q2 中，直到 q1 只剩一个数据，
这时候 q1 中 5 就在队头了，我们取出 q1 队头数据，然后 q1 pop，返回5就完成了，但是如果这时候又要删除一个数据该怎么办？
这次我们要弹出的就是 4 了，这时候思路就和上面一样了，先把前三个数据都挪到 q1 中，然后4就到了队头，这时候就可以 pop 掉4了。
这时候我们就能知道如何用队列实现栈的弹出操作了，首先我们一定要有一个空的队列，数据只保存在一个队列中，然后要弹出栈顶元素的时候，就把前面的数据都挪到空队列中，剩下一个数据弹出就行了。这里的关键就是要有一个空队列。
插入
插入数据我们就不用挪动数据了，我们直接插入到有数据的队列的队尾，不要去动空队列，这样才能保证删除数据有地方可以挪，同时也不会改变数据的先后顺序。
这两个关键操作的思路有了之后，我们就能试着实现一下了。
定义和初始化
首先我们要把之前实现的队列的代码复制粘贴到oj中， 定义栈我们直接用两个队列来定义，定义的时候要思考一下用队列还是用队列的指针，由于之前我们实现的队列的接口都是用的队列的指针作为参数，所以我们直接用队列指针。在初始化的函数中，由于他是要返回这个栈的指针的，所以我们要用malloc来定义，而不能定义局部变量,同时在初始化的时候q1和q2也要malloc出来。
typedef struct {
Queue*q1;
Queue*q2;
} MyStack;
MyStack* myStackCreate() {
MyStack*obj=(MyStack*)malloc(sizeof(MyStack));
if(obj==NULL)
{
perror("malloc fail");
exit(-1);
}
obj->q1=(Queue*)malloc(sizeof(Queue));
obj->q2=(Queue*)malloc(sizeof(Queue));
QueueInit(obj->q1);
QueueInit(obj->q2);
return obj;
}插入
插入函数我们前面分析了要找空的队列插入，如果两个队列都是空队列的话，就随便找一个都行。
void myStackPush(MyStack* obj, int x) {
if(QueueEmpty(obj->q2))//q2为空push到q1
{
QueuePush(obj->q1,x);
}
else
{
QueuePush(obj->q2,x);
}
}删除
删除操作我们首先要找到空队列和有数据的队列是哪一个，如何挪动数据直到只剩一个，然后返回并删除,同时要注意断言两个队列不能同时为空.
int myStackPop(MyStack* obj) {
Queue*empty=obj->q1;
Queue*nonempty=obj->q2;
if(QueueEmpty(obj->q2))
{
empty=obj->q2;
nonempty=obj->q1;
}
while(QueueSize(nonempty)>1)
{
int tmp=QueueFront(nonempty);
QueuePop(nonempty);
QueuePush(empty,tmp);
}
int ret=QueueFront(nonempty);
QueuePop(nonempty);
return ret;
}取栈顶元素
取栈顶元素我们就找到存数据的队列，取队尾数据并返回。
int myStackTop(MyStack* obj) {
if(QueueEmpty(obj->q1))
{
return QueueBack(obj->q2);
}
return QueueBack(obj->q1);
}判空
如果两个队列都为空就返回真，否则返回假.
bool myStackEmpty(MyStack* obj) {
return QueueEmpty(obj->q1)&&QueueEmpty(obj->q2);
}
销毁
销毁我们首先要调用接口销毁两个队列，如何释放q1和q2，最后释放 obj
void myStackFree(MyStack* obj) {
QueueInit(obj->q1);
QueueInit(obj->q2);
free(obj->q1);
free(obj->q2);
free(obj);
}
两个栈实现队列
. - 力扣（LeetCode）
实现思路
我们上面用队列实现栈的思路也可以用来参考这个题目。
删除
首先假设我们的队列里插入了1，2，3，4。我们先把这四个数据压栈在一个栈中。
这时候当我们想要 pop 一个数据是该怎么做呢？第一步肯定还是挪动数据，假设我们把前3个数据都挪到 s2 中，这时候s1中就只剩下 1 了，这时候对 s1 pop就能实现队列的删除了
但是我们如果又要删除一个数据呢，这次要删除的应该是 2 ，我们还需要挪动数据吗？好像并不需要挪动数据了，而且我们上一步甚至都不用把 1 留在 s1 ，我们可以把 1 也挪到 s2 中，而把s1变成一个空的栈，
这样我们队列每次pop的时候就直接 pop s2的栈顶元素就行了。为什么呢，我们前面用栈实现队列的时候每次都要倒数据，这是因为队列转移数据时是不会改变数据的顺序的，他是先进先出，反过来说先进到q1的数据必然会先进到q2 .而栈则不一样，栈是先进后出的，意思就是我们将数据从s1全部挪到s2时，数据的顺序就反过来了，这时候这个栈的出栈顺序 就是队列的删除顺序了。
什么时候又要开始挪数据，就是当 s2 为空的时候，如果又要删除的话，我们就会把新插入到 s1 的数据有全部挪到s2中。
插入
上面的删除操作好像都是在一个栈里完成的，当我们删除一个元素的时候，数据就已经全部挪到s2中了，这时候如果要插入数据，是插入到s1还是s2中呢，显而易见不能插入到s2中，所以我们把数据插入到s1中，连续插入会有影响吗？ 肯定是不会的。
这时候插入到s1中时，就相当于我们一开始假设的情况了，当s2数据被删完了，如果还要删除数据，这时候就又会把s1的数据全部挪到 s2 中
取队头
队头数据就是即将要被删除的元素，所以很简单我们直接取s2的栈顶元素就行了，如果s2为空，我们就要先把s1的数据全部挪到s2之后取s2的栈顶元素。
取队尾
队尾的元素就是最新插入的元素，当然取s1的栈顶元素，如果s1为空呢？s1为空就把s2的数据又全部挪到s1中，这时候顺序又回到了插入的顺序，s1的栈顶就是最新插入的元素也就是队尾元素。
这时候我们就知道了该如何实现了，首先两个栈一个专门用来插入数据，一个专门用来删除数据，当操作某一个栈时栈为空，就需要挪动数据，所以我们可以专门写一个函数来实现两个栈的数据挪动。
定义和初始化
首先把之前实现的栈的代码复制粘贴到oj中，定义和初始化的代码很简单
typedef struct {
Stack spush;
Stack spop;
} MyQueue;
MyQueue* myQueueCreate() {
MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));
STInit(&obj->spush);
STInit(&obj->spop);
return obj;
}
插入
我们前面分析了只要是插入操作就对spush栈插入。那么我们直接调用实现的栈的接口就行了
void myQueuePush(MyQueue* obj, int x) {
StackPush(&obj->spush,x);
}
挪动栈的数据
这个函数就跟前面我们实现的交换队列一样，只是队列只要挪动n-1个数据，而这里要全部挪过去
//挪动两个栈的元素
void SwapStack(ST* src,ST* dest)
{
assert(!StackEmpty(src)||!StackEmpty(dest));
while(StackSize(src))
{
int tmp=StackTop(src);
StackPush(dest,tmp);
StackPop(src);
}
}
删除
删除操作是对spop进行操作的，所以首先我们要对spop判空，如果为空就要调用挪动函数把spush的数据挪到spop中再删除
int myQueuePop(MyQueue* obj) {
if(StackEmpty(obj->spop))
{
SwapStack(&obj->spush,&obj->spop);
}
int ret=StackTop(&obj->spop);
StackPop(&obj->spop);
return ret;
}取队头数据
取队头数据要取spop的栈顶元素，所以首先也是要对spop判空，如果为空也是要挪动数据的，函数与删除的函数基本一样，但是不用弹出栈顶元素。
int myQueuePeek(MyQueue* obj) {
if(StackEmpty(obj->spop))
{
SwapStack(&obj->spush,&obj->spop);
}
int ret=StackTop(&obj->spop);
return ret;
}
取队尾数据
队尾数据即最新插入的元素，就是spush的栈顶元素，如果s1为空，就要先把s2的数据挪到s1中再取s1的栈顶元素。但是这里的oj没有要我们实现这个接口。
队列判空
只有两个栈同时为空队列才是空。
bool myQueueEmpty(MyQueue* obj) {
return StackEmpty(&obj->spush)&&StackEmpty(&obj->spop);
}释放内存
释放内存我们首先要释放两个栈的内存，调用接口就行，释放完两个栈之后再free掉obj。
void myQueueFree(MyQueue* obj) {
STDestroy(&obj->spush);
STDestroy(&obj->spop);
free(obj);
}
