leetcode 232.用栈实现队列
前言:用两个栈实现一个队列，模拟实现队列的功能。
💥🎈个人主页:Dream_Chaser～ 🎈💥
✨✨刷题专栏:http://t.csdn.cn/UlvTc
💨💨本篇内容:力扣上栈与队列面试题目
来源:232. 用栈实现队列 - 力扣（LeetCode）
📌结构体类型的声明(MyQueue)
使用栈来模式队列的行为，如果仅仅用一个栈，是一定不行的，所以需要两个栈一个输入栈(pushst)，一个输出栈(popst)
typedef struct { ST pushst;//输入栈 ST popst;//输出栈 } MyQueue;//自定义队列结构体
1️⃣队列的初始化(myQueueCreate)
图解:
代码实现:
MyQueue* myQueueCreate() { //使用malloc函数为MyQueue结构体分配内存空间,定义一个MyQueue* 的指针指向这块空间 MyQueue* obj =(MyQueue*)malloc(sizeof(MyQueue)); // 若分配失败 if(obj == NULL) {//则打印错误信息 perror("malloc fail"); return NULL;//返回NULL } STInit(&obj->pushst);//初始化输入栈 STInit(&obj->popst);//初始化输出栈 return obj;//返回指向这个结构体的指针 }
2️⃣元素入队列(myQueuePush)
图解：在push数据的时候，只要数据放进输入栈就好
void myQueuePush(MyQueue* obj, int x) { STPush(&obj->pushst , x);//往队列导入元素 }
3️⃣获得队首元素(myQueuePeek)
假设我们需要在正常的队列中获取头部元素，那么应该怎么在这个自定义的队列中获得呢？
那么就应该想清楚(Output stack)输出栈的出栈顺序，由下图可以看出，输入栈(Input stack)出栈顺序是:3 2 1,那么(Output stack)输出栈的入栈顺序是: 3 2 1,自然的，(Output stack)输出栈的出栈顺序就应该为1 2 3，那么(Output stack)输出栈的这个元素1就是队列的队首元素。
这个函数的功能，先判断输出栈为空的前提下，循环条件是输入栈不为空,STPush()的功能就是把输入栈的元素，一个一个导入到输出栈，再一个一个把输入栈的元素弹出。直到输入栈为空栈时结束循环，返回此时的输出栈栈顶元素。
int myQueuePeek(MyQueue* obj) { if(STEmpty(&obj->popst))//若输出栈为空 { //结束条件是把输入栈元素全部挪动到输出栈为止 while(!STEmpty(&obj->pushst))//输入栈不为空 { //获得输入栈头部元素,挪动到输出栈 STPush(&obj->popst,STTop(&obj->pushst)); STPop(&obj->pushst);//弹出输入栈元素 } } //返回此时的输出栈栈顶元素 return STTop(&obj->popst); }
4️⃣元素出队列(myQueuePop)
错误操作:假设输入栈数据没有全部导入到输出栈里，那么最终的出栈顺序会混乱的。
正确操作:
所以在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入），再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。
代码实现的部分需要注意的：
可以看出myQueuePop的实现，直接复用了myQueuePeek() ,要不然，对stEmpty判空的逻辑又要重写一遍。
代码实现:
int myQueuePop(MyQueue* obj) { int front = myQueuePeek(obj);//代码复用,获得队列头部元素 STPop(&obj->popst);//弹出元素 return front;//获得队列的头部元素 }
5️⃣判空(myQueueEmpty)
如果进栈和出栈都为空的话，说明模拟的队列为空了。
bool myQueueEmpty(MyQueue* obj) { return STEmpty(&obj->pushst) && STEmpty(&obj->popst); }//判断队列是否为空，需要输入栈和输出栈两个同时为空，才会返回true
6️⃣销毁队列(myQueueFree)
和队列实现栈同样道理，需要先释放两个栈的空间，再释放结构体的空间，这样才确保不会内存泄露
//队列空间的释放 void myQueueFree(MyQueue* obj) { STDestroy(&obj->pushst);//释放输入栈 STDestroy(&obj->popst);//释放输出栈 free(obj);//释放自定义的队列 }
总代码:
#include<stdlib.h> #include<assert.h> #include<stdbool.h> #include<stdio.h> typedef int STDataType; typedef struct Stack { STDataType* a; int top;//栈顶的位置 int capacity;//栈的容量 }ST; void STInit(ST* pst); void STDestroy(ST* pst); void STPush(ST* pst,STDataType x); void STPop(ST* pst); STDataType STTop(ST* pst); bool STEmpty(ST* pst); int STSize(ST*pst); void STInit(ST* pst) { assert(pst); pst->a = NULL;//栈底 //top不是下标 //pst->top=-1;//指向栈顶元素 pst->top = 0;//指向栈顶元素的下一个位置 pst->capacity = 0; } void STDestroy(ST* pst) { assert(pst); free(pst->a); pst->a = NULL; } void STPush(ST* pst,STDataType x) { if (pst->top == pst->capacity) { int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;//true,4.false,括2倍 STDataType* tmp = (STDataType*)realloc(pst->a, newCapacity * sizeof(STDataType));//返回值地址相等就是原地扩容，不同就是异地扩 if (tmp == NULL) { perror("realloc fail"); return; } pst->a = tmp;//返回的是realloc出来的内存块的地址 pst->capacity = newCapacity;//把扩容后的空间大小赋值给栈容量 } pst->a[pst->top] = x;//先放值 pst->top++;//再++ } void STPop(ST* pst) { assert(pst); assert(!STEmpty(pst)); pst->top--; } STDataType STTop(ST* pst) { assert(pst); assert(!STEmpty(pst)); return pst->a[pst->top - 1]; } bool STEmpty(ST* pst)//栈为空返回true,不为空返回false { //assert(pst); //if (pst->top == 0) //{ // return true; //} //else //{ // return false; //} return pst->top == 0; } int STSize(ST* pst) { assert(pst); return pst->top; } typedef struct { ST pushst;//输入栈 ST popst;//输出栈 } MyQueue;//自定义队列 MyQueue* myQueueCreate() { //使用malloc函数为MyQueue结构体分配内存空间,定义一个MyQueue* 的指针指向这块空间 MyQueue* obj =(MyQueue*)malloc(sizeof(MyQueue)); // 若分配失败 if(obj == NULL) {//则打印错误信息 perror("malloc fail"); return NULL;//返回NULL } STInit(&obj->pushst);//初始化输入栈 STInit(&obj->popst);//初始化输出栈 return obj;//返回指向这个结构体的指针 } void myQueuePush(MyQueue* obj, int x) { STPush(&obj->pushst , x);//往队列导入元素 } int myQueuePop(MyQueue* obj) { int front = myQueuePeek(obj);//代码复用,获得队列头部元素 STPop(&obj->popst);//弹出元素 return front;//获得队列的头部元素 } int myQueuePop(MyQueue* obj) { if(STEmpty(&obj->popst))//若输出栈为空 { //结束条件是把输入栈元素全部挪动到输出栈为止 while(!STEmpty(&obj->pushst))//输入栈不为空 { //获得输入栈头部元素,挪动到输出栈 STPush(&obj->popst,STTop(&obj->pushst)); STPop(&obj->pushst);//弹出输入栈元素 } } //返回此时的输出栈头部元素 int front= STTop(&obj->popst); STPop(&obj->popst);//弹出元素 return front;//获得队列的头部元素 } int myQueuePeek(MyQueue* obj) { if(STEmpty(&obj->popst))//若输出栈为空 { //结束条件是把输入栈元素全部挪动到输出栈为止 while(!STEmpty(&obj->pushst))//输入栈不为空 { //获得输入栈头部元素,挪动到输出栈 STPush(&obj->popst,STTop(&obj->pushst)); STPop(&obj->pushst);//弹出输入栈元素 } } //返回此时的输出栈头部元素 return STTop(&obj->popst); } bool myQueueEmpty(MyQueue* obj) { return STEmpty(&obj->pushst) && STEmpty(&obj->popst); }//判断队列是否为空，需要输入栈和输出栈两个同时为空，才会返回true //队列空间的释放 void myQueueFree(MyQueue* obj) { //和队列实现栈同样道理，需要先释放两个栈的空间，再释放结构体的空间，这样才确保不会内存泄露 STDestroy(&obj->pushst);//释放输入栈 STDestroy(&obj->popst);//释放输出栈 free(obj);//释放自定义的队列 }
代码执行:
本文结束，如有错误，欢迎指正，感谢你的来访！🚩
