题目编号0018 用队列实现栈
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
注意：
你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/implement-stack-using-queues
我们先来分析下题目
要求用两个队列实现一个栈 并且实现四种操作
我们来看第一个Push操作
栈的特点是什么？ 先进后出
队列的特点是什么？ 先进先出
来看图
图上是两个队列
我们假设 注意啊 是假设
第一行的图 它就是一个栈
那么我们可以判断出 它的数据插入顺序就是 1 2 3 4 5
这个时候队列的头就是栈的尾
如果我们这个时候需要删除栈的头数据应该怎么办呢？
我们都知道队列的数据只能是从头开始出
也就是说 比如要将队列前面的1 2 3 4全部出完之后才能开始出 5
但是我们不可能会抛弃之前的数据啊
这个时候我们就想到了第二个队列的用处了
只需要将我Pop的数据使用第二个队列来接受就可以
实现起来的图大概是这样子
这个时候我们就能删除掉头数据了
如果需要再删除一个怎么办呢？
那么只需要将上面的操作再重复一次就好了
这个时候的插入数据只需要往不为空的队列插入数据就可以了
要求首元素就是返回队列的尾
要求尾元素就是返回队列的头
这里我做个思维导图给大家看看
接下来我们来实现代码
把所有的队列代码以及接口函数拷贝进去
第一步 定义结构体
我们来看这个 我们应该怎么定义我们的Stack结构体呢？
既然是两个队列的实现的
那么是不是可以放两个队列的结构在里面？
仔细一想好像可行
我们来试试
代码表示如下
typedef struct { Queue q1; Queue q2; } MyStack;
第二步 实现创建（初始化）
void myStackPush(MyStack* obj, int x) { if(QueueEmpty(obj->q1)) { QueuePush(&obj->q2,x); } else { QueuePush(&obj->q1,x); } }
代码表示如上
这里我们需要判断哪个队列不为空
哪个不为空就插入哪里
第三步 删除接口函数
终于来到最难的一步了
我们先写出两个指针来判断空和非空
如果说我们的判断不正确的话 那么我们就将这两个指针翻转一下就好了
代码整体表现不变
assert(obj); // 我们假设队列q1为空 Queue* Empty = &obj->q1; Queue* NonEmpty = &obj->q2; // 如果队列1不为空的话 我们只需要将这两个指针的位置互换一下就可以 if(QueueEmpty(obj->q1)) { ; } else { Queue* Empty = &obj->q2; Queue* NonEmpty = &obj->q1; }
大家来感受下上面这段代码奇妙的地方
我们可以省略下面一大段的else代码
之后我们开始一个个的迁移数据
直到最后一个的时候我们记录下这个数据再删除
int myStackPop(MyStack* obj) { assert(obj); // 我们假设队列q1为空 Queue* Empty = &obj->q1; Queue* NonEmpty = &obj->q2; // 如果队列1不为空的话 我们只需要将这两个指针的位置互换一下就可以 if(QueueEmpty(&obj->q1)) { ; } else { Empty = &obj->q2; NonEmpty = &obj->q1; } // 一个一个转移元素 while(QueueSize(NonEmpty)>1) { QueuePush(Empty,QueueFront(NonEmpty)); QueuePop(NonEmpty); } // 记录下删除值 删除掉 int pop = QueueFront(NonEmpty); QueuePop(NonEmpty); return pop }
第四步 返回头的值
这里我们可以分两种情况讨论
如果1为空就返回2的尾值
如果2为空就返回1的尾值
int myStackTop(MyStack* obj) { // 断言 assert(obj); // 返回不为空的那个队列的尾值 if(QueueEmpty(&obj->q1)) { return QueueBack(&obj->q2); } else { return QueueBack(&obj->q1); } }
总结
发现问题一
这里一定要注意一个大坑！！
看看下面这段代码 有没有什么问题？
这里！！！！ 仔细看
我们再定义了空和非空之后 又在语句块里面定义了一个空和非空
这里问题就很大了
语句块里面是不会改变Empty和NonEmpty的值的
而且更关键的是它不会报错！！！！
（害我debug了半个小时）
所以说大家再写代码的时候尽量将所有需要用的变量在开头定义一遍
在后面不能再定义了！
发现问题二
这里还要有要注意的一点
指针指向的东西不一定是指针
这点属于我的个人理解偏差
就比如说
我们在代码中写出了以下代码
obj->q1
这里获取的其实是q1这个结构体
要想将其作为参数传给指针的话必须要先传地址
源码
#include<stdio.h> #include<stdlib.h> #include<math.h> #include<assert.h> #include<stdbool.h> typedef int QueueNodeType; typedef struct QueueNode { struct QueueNode * next; QueueNodeType val; }QueueNode; typedef struct Queue { struct QueueNode* head; struct QueueNode* tail; }Queue; void QueueInit(Queue* pq); void QueuePush(Queue* pq, QueueNodeType x); void QueuePop(Queue* pq); void QueueDestroy(Queue* pq); void QueuePrint(Queue* pq); QueueNodeType QueueFront(Queue* pq); int QueueSize(Queue* pq); bool QueueEmpty(Queue* pq); QueueNodeType QueueBack(Queue* pq) { // 断言 assert(pq); assert(pq->tail); // 返回尾值 return pq->tail->val; } void QueueInit(Queue* pq) { assert(pq); pq->head = NULL; pq->tail = NULL; } struct QueueNode* Buynewnode() { struct QueueNode* newnode = (struct QueueNode*)malloc(sizeof(struct QueueNode)); assert(newnode); return newnode; } void QueuePush(Queue* pq ,QueueNodeType x) { assert(pq); struct QueueNode* newnode = Buynewnode(); assert(newnode); // 赋值 newnode->val = x; newnode->next = NULL; // 判断头尾指针是否为空 if (pq->head==NULL) { pq->head = pq->tail = newnode; } // 赋值并链接 else { pq->tail->next = newnode; pq->tail = newnode; } } void QueueDestroy(Queue* pq) { // 断言不为空 assert(pq); //assert(pq->head); // 删除数据 释放空间 头指针向后移动 // 这里肯定要循环删除的 注意循环的条件 while (pq->head) { // 保存下一位 struct QueueNode* cur = pq->head->next; // 删除迭代 free(pq->head); pq->head = cur; } // 要注意 这里画图看看 删除掉最后一个节点的时候尾指针变空指针了 所以要对尾指针也进行赋值 pq->tail = NULL; } void QueuePop(Queue* pq) { //断言 assert(pq); assert(pq->head); //每次删除一个 如果头指针指向空了 尾指针也要置空(野指针) // 保存下一位 struct QueueNode* cur = pq->head->next; // 删除迭代 free(pq->head); pq->head = cur; if (pq->head==NULL) { pq->tail = NULL; } } void QueuePrint(Queue* pq) { //判断不为空 assert(pq); //肯定还是用循环 打印一个删除一个 注意条件 while (pq->head) { printf("%d-> ", pq->head->val); // 在删除的时候head已经迭代了 我们不用管 QueuePop(pq); //在最后的时候 } // 形象表示下 这里加个空指针 可以不打 printf("NULL\n"); } QueueNodeType QueueFront(Queue* pq) { // 断言 assert(pq); assert(pq->head); // 返回 return pq->head->val; } int QueueSize(Queue* pq) { // 断言 assert(pq); // 遍历 遇到NULL结束 开始就遇到NULL返回0 int n = 0; struct QueueNode* cur = pq->head; while (cur) { cur = cur->next; n++; } return n; } bool QueueEmpty(Queue* pq) { //断言 assert(pq); return pq->head == NULL; } typedef struct { Queue q1; Queue q2; } MyStack; MyStack* myStackCreate() { // 使用动态内存开辟来返回值 MyStack* obj = (MyStack*)malloc(sizeof(MyStack)); // 很重要 这里还要对q1 q2进行初始化 QueueInit(&obj->q1); QueueInit(&obj->q2); return obj; // 返回这个指针 想想看可不可以不用动态内存 怎么办？ const？ } void myStackPush(MyStack* obj, int x) { assert(obj); if (QueueEmpty(&obj->q1)) { QueuePush(&obj->q2,x); } else { QueuePush(&obj->q1,x); } } int myStackPop(MyStack* obj) { assert(obj); // 我们假设队列q1为空 Queue* Empty = &obj->q1; Queue* NonEmpty = &obj->q2; // 如果队列1不为空的话 我们只需要将这两个指针的位置互换一下就可以 if(QueueEmpty(&obj->q1)) { ; } else { Empty = &obj->q2; NonEmpty = &obj->q1; } // 一个一个转移元素 while(QueueSize(NonEmpty)>1) { QueuePush(Empty,QueueFront(NonEmpty)); QueuePop(NonEmpty); } // 记录下删除值 删除掉 int pop = QueueFront(NonEmpty); QueuePop(NonEmpty); return pop; } bool myStackEmpty(MyStack* obj) { //断言 assert(obj); // 两个队列都为空就是空 return QueueEmpty(&obj->q2) && QueueEmpty(&obj->q1); } int myStackTop(MyStack* obj) { // 断言 assert(obj); // 返回不为空的那个队列的尾值 if(QueueEmpty(&obj->q1)) { return QueueBack(&obj->q2); } else { return QueueBack(&obj->q1); } } void myStackFree(MyStack* obj) { QueueDestroy(&obj->q1); QueueDestroy(&obj->q2); free(obj); } /** * Your MyStack struct will be instantiated and called as such: * MyStack* obj = myStackCreate(); * myStackPush(obj, x); * int param_2 = myStackPop(obj); * int param_3 = myStackTop(obj); * bool param_4 = myStackEmpty(obj); * myStackFree(obj); */
