【初阶数据结构与算法】栈和队列leetcode刷题之用栈实现队列，用队列实现栈
文章目录
- 一、用栈实现队列
- 1.大致思路分析
- 2.用栈实现队列的结构以及初始化
- 3.入队列
- 4.出队列并返回原队头元素
- 5.返回队头元素
- 6.队列判空和队列销毁
- 7.完整题解代码
- 二、用队列实现栈
- 1.大致思路分析
- 2.用队列实现栈的结构和初始化
- 3.入栈
- 4.出栈
- 5.取栈顶元素
- 6.判空和销毁栈
- 7.完整题解
在本节的题目中都会用到数据结构栈和队列，由于我们目前没有介绍C++，以C语言的形式来做，所以我们需要把我们之前实现好的栈和队列复制进去再做，等以后我们讲到C++部分就可以使用STL，不用自己手动写栈和队列了
一、用栈实现队列
题目链接：https://leetcode.cn/problems/implement-queue-using-stacks/description/
1.大致思路分析
我们先来看看题目描述：
题目的大致含义就是要求我们使用两个栈模拟实现一个队列，要求要支持一个队列的基本操作，这些操作大致都写在上面说明了，关键我们要构思一下怎么用两个栈实现队列的操作
我们都知道栈的特点是先进后出，而队列是先进先出，刚好是相反的，是不是可以从这个方面下手，一个栈和队列是相反的，那么两个栈反复倒腾呢？是不是就能“负负得正”？我们画图来实践一下：
根据上面我们画的图例，发现我们的想法确实奏效，虽然一个栈和队列的性质刚好相反，但是经过两个栈的倒腾，刚好负负得正，实现先进先出
但是上面也只是我们的大致思路，我们只讨论了第一入队列的情况，那么下一次我们入队列要把数据放在哪个栈中呢？
很明显就是栈1，因为栈2现在的顺序是正确的，只要正常的出栈，那么就可以模拟出队列的顺序，所以不能扰乱栈2的顺序
所以我们可以得出，栈1就是我们用来入队列，而栈2则负责出队列操作，当栈2的元素已经出完之后，我们就可以再次把栈1的所有元素再放进栈2，然后再由栈2来出队列，栈1来入队列，如此循环就基本实现了队列的功能，接下来我们就一个函数一个函数分析：
2.用栈实现队列的结构以及初始化
这个新队列的结构在题目中也已经提到，就是两个栈，所以我们定义两个栈作为这个新队列的结构，但是我们注意，根据刚刚的分析我们知道，其中一个栈用来入队列，另一个专门用来出队列，所以我们可以取stpush和stpop来进行分辨，如下：
typedef struct
{
ST stpush;
ST stpop;
} MyQueue;
初始化方法也很简单，就是我们申请一个这样的节点大小的空间，然后分别调用栈的初始化函数来对两个栈初始化，如下：
MyQueue* myQueueCreate()
{
MyQueue* pq = (MyQueue*)malloc(sizeof(MyQueue));
if(pq == NULL)
{
perror("malloc");
return NULL;
}
STInit(&pq->stpush);
STInit(&pq->stpop);
return pq;
}
3.入队列
在之前我们分析过，两个栈中stpush这个栈用来专门入数据，也就是入队列，所以我们在入队列函数中直接将数据入到stpush栈中，如下：
void myQueuePush(MyQueue* obj, int x)
{
STPush(&obj->stpush, x);
}
4.出队列并返回原队头元素
stpop栈用来专门出队列的，实现出队列的逻辑就是，如果stpop栈不为空，那么我们直接就先保存；原队头元素，然后让stpop出栈，然后返回保存的队头
但是如果sttop栈为空，我们就需要先把stpush栈中的元素全部放到stpop栈中，放完之后再进行上面的操作，如下：
int myQueuePop(MyQueue* obj)
{
if(STEmpty(&obj->stpop))
{
while(!STEmpty(&obj->stpush))
{
int top = STTop(&obj->stpush);
STPop(&obj->stpush);
STPush(&obj->stpop, top);
}
}
int top = STTop(&obj->stpop);
STPop(&obj->stpop);
return top;
}
5.返回队头元素
返回队头元素的逻辑跟上面的出队列操作差不多，如果stpop不为空那么直接返回栈顶元素，如果stpop为空那么就先把stpush中的元素移动到stpop栈中，然后再去返回栈顶元素，跟上面出栈操作的唯一区别就是不用出栈，只用去取栈顶元素，如下：
int myQueuePeek(MyQueue* obj)
{
if(STEmpty(&obj->stpop))
{
while(!STEmpty(&obj->stpush))
{
int top = STTop(&obj->stpush);
STPop(&obj->stpush);
STPush(&obj->stpop, top);
}
}
return STTop(&obj->stpop);
}
6.队列判空和队列销毁
我们用两个栈实现的队列要判空的话，必须保证两个栈同时为空队列才为空，否则就不是空，如下：
bool myQueueEmpty(MyQueue* obj)
{
return STEmpty(&obj->stpush) && STEmpty(&obj->stpop);
}
队列销毁的本质也就是销毁里面的两个栈，但是由于我们的MyQueue这个指针也是我们动态申请的，也要释放掉，然后置空，如下：
void myQueueFree(MyQueue* obj)
{
STDestroy(&obj->stpush);
STDestroy(&obj->stpop);
free(obj);
obj = NULL;
}
7.完整题解代码
注意，这里所有关于栈的实现的代码就不再贴出来了，否则就太长了，可以自行把实现的栈放在题目之前，那么出来栈部分的完整题解如下：
typedef struct
{
ST stpush;
ST stpop;
} MyQueue;
MyQueue* myQueueCreate()
{
MyQueue* pq = (MyQueue*)malloc(sizeof(MyQueue));
if(pq == NULL)
{
perror("malloc");
return NULL;
}
STInit(&pq->stpush);
STInit(&pq->stpop);
return pq;
}
void myQueuePush(MyQueue* obj, int x)
{
STPush(&obj->stpush, x);
}
int myQueuePop(MyQueue* obj)
{
if(STEmpty(&obj->stpop))
{
while(!STEmpty(&obj->stpush))
{
int top = STTop(&obj->stpush);
STPop(&obj->stpush);
STPush(&obj->stpop, top);
}
}
int top = STTop(&obj->stpop);
STPop(&obj->stpop);
return top;
}
int myQueuePeek(MyQueue* obj)
{
if(STEmpty(&obj->stpop))
{
while(!STEmpty(&obj->stpush))
{
int top = STTop(&obj->stpush);
STPop(&obj->stpush);
STPush(&obj->stpop, top);
}
}
return STTop(&obj->stpop);
}
bool myQueueEmpty(MyQueue* obj)
{
return STEmpty(&obj->stpush) && STEmpty(&obj->stpop);
}
void myQueueFree(MyQueue* obj)
{
STDestroy(&obj->stpush);
STDestroy(&obj->stpop);
free(obj);
obj = NULL;
}
二、用队列实现栈
题目链接：https://leetcode.cn/problems/implement-stack-using-queues/description/
1.大致思路分析
我们先来看看题目描述：
这道题和上道题类似，就是使用两个队列实现一个栈的各种操作，这道题要比上一题难，因为在上一题中，我们的思路就是“负负得正”，通过两个栈的互相倒腾就可以还原队列的入队列出队列操作，但是这题不行，我们画个图看看：
根据上图的分析，我们知道了完全使用上一题的思路行不通，因为栈通过两次倒腾后，里面的元素顺序会反过来，但是队列通过两次倒腾后，里面元素的顺序还是不变
所以我们要换个思路，我们先来看看出栈的思路： 我们把数据入到队列1中，然后移动到队列2时，不全部挪过去，只留下一个，如图：
这个时候我们发现队列1中留下的，对应到栈上不正是我们的栈顶元素吗？我们在出栈的时候就可以把队列1中剩下的一个元素出队列，4是最后入栈的，最后第一个出栈，符合我们栈的性质
那么为了保险起见，我们再试一次，先假设我们实现的栈出栈一次，就是把4删掉，让剩下的1,2,3再来模拟一次出栈，如图：
此时我们发现队列2中留下的正好是新的栈顶元素，让队列2出队列就刚好对应了出栈操作，所以我们的出栈思路大致是正确的
但是我们发现，队列1和队列2是反复倒腾的，没有哪个是专门出栈，哪个专门入栈的，所以我们接下来要分清怎么判断哪个队列什么时候用来入栈，什么时候用来出栈
经过规律总结我们发现，当我们要出栈的时候，有一个队列总是空着的，另一个队列里面才装有数据，我们在操作时就是让不为空的队列将size-1个元素挪到空队列里面去，然后不为空的队列就只剩下一个元素出队列即可模拟实现出栈
那么我们入栈的时候，就是往不为空的队列中去入，所以我们在写入栈和出栈操作时最重要的就时判断出哪个队列空，哪个队列不为空，才方便进行操作，那么接下来我们就一个函数一个函数分析：
2.用队列实现栈的结构和初始化
题目明确要求我们使用两个队列实现一个栈，所以栈的结构实际上就是两个队列，如下：
typedef struct
{
Queue q1;
Queue q2;
} MyStack;
初始化也很简单，首先动态开辟一个MyStack大小的空间，然后就只需要调用队列的初始化方法分别初始化两个队列即可，如下：
MyStack* myStackCreate()
{
MyStack* st = (MyStack*)malloc(sizeof(MyStack));
if(st == NULL)
{
perror("malloc");
return NULL;
}
QueueInit(&st->q1);
QueueInit(&st->q2);
return st;
}
3.入栈
我们刚刚分析过了，我们入栈就是往不为空的队列中去入，所以我们在入栈时只需要判断一下哪个栈不为空即可，如下：
void myStackPush(MyStack* obj, int x)
{
if(!QueueEmpty(&obj->q1))
{
QueuePush(&obj->q1, x);
}
else
{
QueuePush(&obj->q2, x);
}
}
4.出栈
我们的出栈操作刚刚也重点分析了，就是先找出哪个是空队列，哪个是非空队列，然后将非空队列中size-1个数据挪动到空队列中，然后非空队列剩下的一个元素就是我们要出栈的元素，题目要求出栈前返回栈顶元素，所以我们创建一个变量用来保存栈顶元素，最后用来返回即可，如下：
int myStackPop(MyStack* obj)
{
//假设q1队列为空，另一个队列非空
Queue* empty = &obj->q1;
Queue* noempty = &obj->q2;
//如果q1非空，那么q2就是空队列，q1是非空队列
if(!QueueEmpty(&obj->q1))
{
empty = &obj->q2;
noempty = &obj->q1;
}
//找到size减1的大小
int sum = QueueSize(noempty) - 1;
//循环地把非空队列的元素移动到空队列中
while(sum--)
{
int top = QueueFront(noempty);
QueuePop(noempty);
QueuePush(empty, top);
}
//最后保存一下非空队列的栈顶元素
//然后就可以出队列了，也就是出栈
int top = QueueFront(noempty);
QueuePop(noempty);
return top;
}
5.取栈顶元素
取栈顶元素其实就是取非空队列中的队尾元素，如下：
int myStackTop(MyStack* obj)
{
if(!QueueEmpty(&obj->q1))
{
return QueueBack(&obj->q1);
}
else
{
return QueueBack(&obj->q2);
}
}
6.判空和销毁栈
只有两个队列同时为空，我们的栈才为空，如下：
bool myStackEmpty(MyStack* obj)
{
return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}
销毁栈就只需要调用队列的销毁函数，分别销毁掉两个队列即可，不要忘了最后把整个栈的结构也销毁掉，如下：
void myStackFree(MyStack* obj)
{
QueueDestroy(&obj->q1);
QueueDestroy(&obj->q2);
free(obj);
obj = NULL;
}
7.完整题解
注意，这里所有关于队列的实现的代码就不再贴出来了，否则就太长了，可以自行把实现的队列放在题目之前，那么除了栈部分的完整题解如下：
typedef struct
{
Queue q1;
Queue q2;
} MyStack;
MyStack* myStackCreate()
{
MyStack* st = (MyStack*)malloc(sizeof(MyStack));
if(st == NULL)
{
perror("malloc");
return NULL;
}
QueueInit(&st->q1);
QueueInit(&st->q2);
return st;
}
void myStackPush(MyStack* obj, int x)
{
if(!QueueEmpty(&obj->q1))
{
QueuePush(&obj->q1, x);
}
else
{
QueuePush(&obj->q2, x);
}
}
int myStackPop(MyStack* obj)
{
//假设q1队列为空，另一个队列非空
Queue* empty = &obj->q1;
Queue* noempty = &obj->q2;
//如果q1非空，那么q2就是空队列，q1是非空队列
if(!QueueEmpty(&obj->q1))
{
empty = &obj->q2;
noempty = &obj->q1;
}
//找到size减1的大小
int sum = QueueSize(noempty) - 1;
//循环地把非空队列的元素移动到空队列中
while(sum--)
{
int top = QueueFront(noempty);
QueuePop(noempty);
QueuePush(empty, top);
}
//最后保存一下非空队列的栈顶元素
//然后就可以出队列了，也就是出栈
int top = QueueFront(noempty);
QueuePop(noempty);
return top;
}
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);
obj = NULL;
}
那么今天的刷题就分享到这里，有什么疑问欢迎提出，下一篇我们还有一个重点的题目设计循环队列，讲完后我们就可以进入二叉树的学习了，敬请期待吧！
bye~