前言
用"栈实现队列",力扣中一道oj题,可以帮助刚接触"栈"和"队列"的新手更好的理解栈和队列这两种结构.
题目来源于力扣:
题目链接:https://leetcode.cn/problems/implement-queue-using-stacks/
难度:简单
目录
- 前言
- 一、队列的各接口:
- 1.1 类型的声明(MyQueue):
- 1.2 初始化(myQueueCreate):
- 1.3 入队列(myQueuePush)
- 1.4 出队列(myQueuePop)
- 1.5 队列的判空(myQueueEmpty)
- 1.6 返回队首元素(myQueuePeek):
- 1.7 队列的销毁(myQueueFree):
- 二、总代码:
一、队列的各接口:
1.1 类型的声明(MyQueue):
//模拟队列类型的声明
typedef struct {ST stackpush; //用于模拟队列的 入队操作ST stackpop; //用于模拟队列的 出队操作
} MyQueue;
这里是借助两个栈用于模拟队列.
①:stackpush 模拟队列的入队
②:stackpop 模拟队列的出队
1.2 初始化(myQueueCreate):
该队列是由两个栈实现的,所以重点关注两个栈的初始化即可.
步骤:
- 申请两个栈大小的空间.
申请失败时判断一下. - 对队列中的两个栈,一次调用他们的初始化函数.(这个千万别漏掉了,牛牛漏掉之后找了好久的问题)
//队列的初始化
MyQueue* myQueueCreate() {//给队列开辟空间MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));if(obj==NULL){perror("obj malloc fail");}//一定要记得这里要初始化(别漏掉了哦)InitST(&obj->stackpush);InitST(&obj->stackpop);return obj;
}
1.3 入队列(myQueuePush)
对于入队列的模拟实现很简单,只需要将数据压入栈(模拟入队列:stackpush)即可.
void myQueuePush(MyQueue* obj, int x) {assert(obj);STPush(&obj->stackpush,x);
}
1.4 出队列(myQueuePop)
函数要求:
将队首元素出队,并且返回刚刚出队的队首元素.
模拟出队相对复杂一些.
- 初始状态下或者
stackpop(模拟出队的栈)数据出队列到空时,里面是没有数据的,所以先判断stackpop是否有数据.
有数据:则直接获取stackpop的栈顶元素作为队首元素.
无数据:将数据从模拟入队列栈全部倒过来.(倒数据) - 获取
stackpop的栈顶元素作为队首元素,使用top变量记录下来.(因为后面要执行出栈操作). - 出栈(模拟出队列),并返回
top变量.
int myQueuePop(MyQueue* obj) {assert(obj);if(STEmpty(&obj->stackpop))//如果栈(stackpop模拟出队列的栈)为空,则向栈(stackpush模拟入队列的栈)要数据{//下面循环结束的条件是不为空while(!STEmpty(&obj->stackpush))//将数据从模拟入队列栈全部倒过来{//将栈(stackpush模拟入队)的栈顶元素依次压入栈(stackpop模拟出栈)STPush(&obj->stackpop,STTop(&obj->stackpush));STPop(&obj->stackpush);}}int top=STTop(&obj->stackpop);//记录用来模拟出队列的栈的栈顶元素;STPop(&obj->stackpop);return top;
}
1.5 队列的判空(myQueueEmpty)
当两个栈中都没有元素时,则队列为空.
//写法1
bool myQueueEmpty(MyQueue* obj) {if(STEmpty(&obj->stackpush)&&STEmpty(&obj->stackpop))//如果都为空,则为空栈{return true;}else return false;
}
//写法2.
bool myQueueEmpty(MyQueue* obj) {return STEmpty(&obj->stackpush) && STEmpty(&obj->stackpop);
}
1.6 返回队首元素(myQueuePeek):
stackpop不为空时,则队首元素就是stackpop的栈顶元素.stackpop为空时,则队首元素就是stackpush的栈底元素.
所以这里也需要倒数据.
int myQueuePeek(MyQueue* obj) {assert(obj);if(STEmpty(&obj->stackpop))//如果栈(stackpop模拟出队列)为空,则向栈(stackpush模拟入队列)要数据{while(!STEmpty(&obj->stackpush)){//将栈(stackpush模拟入队)的栈顶元素依次压入栈(stackpop模拟出队列)STPush(&obj->stackpop,STTop(&obj->stackpush));STPop(&obj->stackpush);}}int top=STTop(&obj->stackpop);//记录用来模拟出队列的栈的栈顶元素;return top;
}
与myQueuePop(出队列)函数比较,此函数只是将队首元素返回,并没有指向pop出队操作.
所以我们在实现myQueuePop函数时可以复用一下myQueuePeek函数.
int myQueuePop(MyQueue* obj) {int top=myQueuePeek(obj);STPop(&obj->stackpop);return top;
}
1.7 队列的销毁(myQueueFree):
- 释放两个栈初始化开辟的空间
- 释放队列申请的空间.
void myQueueFree(MyQueue* obj) {STDestory(&obj->stackpush);STDestory(&obj->stackpop);free(obj);
}
二、总代码:
前面的代码是栈的实现,由于c语言不能像c++那样直接调用库.
typedef int stacktype;typedef struct stack//定义栈的类型
{stacktype* data;int top;int capacaity;
}ST;
void InitST(ST* ps);//初始化栈
void STPush(ST* ps, stacktype x);//压栈
void STPop(ST* ps);//出栈
bool STEmpty(ST* ps);//判断是否为空栈
stacktype STTop(ST* ps);//返回栈顶元素
void STDestory(ST* ps);//栈的销毁void InitST(ST* ps)//初始化栈
{assert(ps);ps->top = -1;ps->capacaity = 4;ps->data = (stacktype*)malloc(ps->capacaity * sizeof(stacktype));}void STPush(ST* ps, stacktype x)//压栈
{assert(ps);if (ps->top+1 == ps->capacaity){ps->capacaity *= 2;ST* tmp = (stacktype*)realloc(ps->data, ps->capacaity * sizeof(stacktype));if(tmp == NULL){printf("增容失败\n");}ps->data = tmp;}ps->top++;ps->data[ps->top] = x;}void STPop(ST* ps)//出栈
{assert(ps);assert(!STEmpty(ps));ps->top--;
}bool STEmpty(ST* ps)//判断是否为空栈,是空返回真
{assert(ps);if (ps->top == -1){return true;}return false;
}
stacktype STTop(ST* ps)//返回栈顶元素
{assert(ps);return ps->data[ps->top];
}
void STDestory(ST* ps)//销毁栈
{assert(ps);free(ps->data);ps->data = NULL;ps->top = -1;ps->capacaity = 0;
}//模拟队列类型的声明
typedef struct {ST stackpush;ST stackpop;
} MyQueue;//队列的初始化
MyQueue* myQueueCreate() {MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));if(obj==NULL){perror("obj malloc fail");}//一定要记得这里要初始化InitST(&obj->stackpush);InitST(&obj->stackpop);return obj;
}void myQueuePush(MyQueue* obj, int x) {assert(obj);STPush(&obj->stackpush,x);
}int myQueuePop(MyQueue* obj) {assert(obj);if(STEmpty(&obj->stackpop))//如果栈(stackpop模拟出栈)为空,则向栈(stackpush模拟入栈)要数据{while(!STEmpty(&obj->stackpush)){//将栈(stackpush模拟入队)的栈顶元素依次压入栈(stackpop模拟出栈)STPush(&obj->stackpop,STTop(&obj->stackpush));STPop(&obj->stackpush);}}int top=STTop(&obj->stackpop);//记录用来模拟出队列的栈的栈顶元素;STPop(&obj->stackpop);return top;
}bool myQueueEmpty(MyQueue* obj) {if(STEmpty(&obj->stackpush)&&STEmpty(&obj->stackpop))//如果都为空,则为空栈{return true;}else return false;//return STEmpty(&obj->stackpush)&&STEmpty(&obj->stackpop);
}int myQueuePeek(MyQueue* obj) {if(STEmpty(&obj->stackpop))//如果栈(stackpop模拟出栈)为空,则向栈(stackpush模拟入栈)要数据{while(!STEmpty(&obj->stackpush)){//将栈(stackpush模拟入队)的栈顶元素依次压入栈(stackpop模拟出栈)STPush(&obj->stackpop,STTop(&obj->stackpush));STPop(&obj->stackpush);}}int top=STTop(&obj->stackpop);//记录用来模拟出队列的栈的栈顶元素;return top;//return STTop(&obj->stackpop);
}void myQueueFree(MyQueue* obj) {STDestory(&obj->stackpush);STDestory(&obj->stackpop);free(obj);
}运行结果:
