题目编号0019 用两个栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：
你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/implement-queue-using-stacks
整体分析
我们先来分析题目 跟我们昨天刷的题目区别不大
先来画图看看两个栈是什么样子的
这里进栈的顺序分别是 1 2 3 4 5
我们将这些数据迁移到另一个栈之中试试
我们可以发现 这里的数据竟然倒过来了！
那么我们取数据的顺序就变成了
1 2 3 4 5
我们发现这就刚好是跟队列删取数据的顺序一样了
所以说我们可以这样子设计这两个栈
接下来我们知道了这两个栈的基本结构了 我们来做题目试试
我们先来看第一个
第一步 初始化
我们先来看 我们创建的结构体是什么样子的
typedef struct { ST tpush; ST tpop; } MyQueue;
typedef struct Stack { StackType* a; //储存数据的大小 int Top; //栈顶 int Capacity; //数组容量大小 }ST;
这里是两个结构体的套用
MyQueue myQueue = new MyQueue();
MyQueue* myQueueCreate() { MyQueue* obj = (MyQueue* myQueue)malloc(sizeof(MyQueue)); StackInit(&obj->tpush); StackInit(&obj->tpop); return obj; }
要求我们这样子 返回一个指针
那么这一步很简单 我们使用动态内存开辟一块空间就好了
之后返回一个指针指向这块空间
第二步 插入
void myQueuePush(MyQueue* obj, int x) { }
这一步我们也讲的很明白了 插入往第一个里面插
所以说我们有以下代码
void myQueuePush(MyQueue* obj, int x) { } 1 2 3 这一步我们也讲的很明白了 插入往第一个里面插 所以说我们有以下代码
直接这样子就可以了
第三步 删除
再来上图
我们一边取第一个栈的头元素放置到第二个栈中
一边删除第一个栈中的元素
知道第一个栈为空为止
代码表示如下
int myQueuePop(MyQueue* obj) { if(StackEmpty(&obj->tpop)) { while(!StackEmpty(&obj->tpush)) { StackPush(&obj->tpop,StackTop(&obj->tpush)); StackPop(&obj->tpush); } } int front = StackTop(&obj->tpop); StackPop(&obj->tpop); return front; }
第四步 返回头元素
这个很简单和删除差不多
先将所有的元素移动到第二个栈当中 返回栈的头值就可以
直接上代码
int myQueuePeek(MyQueue* obj) { if(StackEmpty(&obj->tpop)) { while(!StackEmpty(&obj->tpush)) { StackPush(&obj->tpop,StackTop(&obj->tpush)); StackPop(&obj->tpush); } } return StackTop(&obj->tpop); }
第五步 判断是否为空
这一步也很简单
两个都为空就是空了
直接上代码
bool myQueueEmpty(MyQueue* obj) { return StackEmpty(&obj->tpush) && StackEmpty(&obj->tpop); }
第六步 释放内存
这一步要注意了！！！
我们需要先释放开辟的两个栈的内存
之后再释放我们开辟的队列的内存
代码表示如下
void myQueueFree(MyQueue* obj) { StackDestroy(&obj->tpush); StackDestroy(&obj->tpop); free(obj); obj=NULL; }
代码运行结果如下
总结
并没有什么特别的难点
写的也比较顺利
收获应该是巩固了队列和栈的基本知识
源代码
#include<stdio.h> #include<stdlib.h> #include<stdbool.h> #include<math.h> #include<assert.h> typedef char StackType; typedef struct Stack { StackType* a; //储存数据的大小 int Top; //栈顶 int Capacity; //数组容量大小 }ST; void StackInit(ST* p); void StackPush(ST* p, StackType x); void StackPop(ST* p); int StackSize(ST* p); StackType StackTop(ST* p); // 判断栈是否为空 如果为空 返回True 如果为假 返回False bool StackEmpty(ST* p); void StackDestroy(ST* p); void StackInit(ST* p) { assert(p); p->a = NULL; p->Top = 0; p->Capacity = 0; } void StackPush(ST* p, StackType x) { assert(p); if (p->Top==p->Capacity) { int NewCapacity = p->Capacity == 0 ? 4: p->Capacity * 2; StackType* Tmp = realloc(p->a,NewCapacity*sizeof(StackType)); if (Tmp==NULL) { perror("StackPush realloc"); } else { p->Capacity = NewCapacity; p->a = Tmp; } } p->a[p->Top] = x; p->Top++; } void StackPop(ST* p) { assert(p); assert(p->Top > 0); p->Top--; } void StackPrint(ST* p) { assert(p); while (p->Top>0) { printf("%d ", p->a[p->Top - 1]); StackPop(p); } } int StackSize(ST* p) { assert(p); return p->Top; } bool StackEmpty(ST* p) { assert(p); return p->Top==0; } void StackDestroy(ST* p) { assert(p); free(p->a); p->a == NULL; p->Capacity = 0; p->Top = 0; } StackType StackTop (ST* p) { assert(p); assert(p->Top > 0); return p->a[p->Top - 1]; } typedef struct { ST tpush; ST tpop; } MyQueue; MyQueue* myQueueCreate() { MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue)); StackInit(&obj->tpush); StackInit(&obj->tpop); return obj; } void myQueuePush(MyQueue* obj, int x) { //要求传递的参数是指针 所以说要用数组来接受 StackPush(&obj->tpush,x); } int myQueuePop(MyQueue* obj) { if(StackEmpty(&obj->tpop)) { while(!StackEmpty(&obj->tpush)) { StackPush(&obj->tpop,StackTop(&obj->tpush)); StackPop(&obj->tpush); } } int front = StackTop(&obj->tpop); StackPop(&obj->tpop); return front; } int myQueuePeek(MyQueue* obj) { if(StackEmpty(&obj->tpop)) { while(!StackEmpty(&obj->tpush)) { StackPush(&obj->tpop,StackTop(&obj->tpush)); StackPop(&obj->tpush); } } return StackTop(&obj->tpop); } bool myQueueEmpty(MyQueue* obj) { return StackEmpty(&obj->tpush) && StackEmpty(&obj->tpop); } void myQueueFree(MyQueue* obj) { StackDestroy(&obj->tpush); StackDestroy(&obj->tpop); free(obj); obj=NULL; } /** * Your MyQueue struct will be instantiated and called as such: * MyQueue* obj = myQueueCreate(); * myQueuePush(obj, x); * int param_2 = myQueuePop(obj); * int param_3 = myQueuePeek(obj); * bool param_4 = myQueueEmpty(obj); * myQueueFree(obj); */
