一、题目
原题链接:
232. 用栈实现队列 - 力扣(LeetCode)
函数原型:
typedef struct //我的队列结构定义
{
} MyQueue;
MyQueue* myQueueCreate() //我的队列创建及其初始化
void myQueuePush(MyQueue* obj, int x) //我的队列入队
int myQueuePop(MyQueue* obj) //我的队列出队
int myQueuePeek(MyQueue* obj) //我的队列取队头数据
bool myQueueEmpty(MyQueue* obj) //我的队列判空
void myQueueFree(MyQueue* obj) //我的队列销毁
二、思路
1.“我的队列”结构定义
利用两个栈实现队列,因此使用一个结构体,结构体成员包含两个栈s1、s2。
2.“我的队列”创建及其初始化
函数原型返回值类型是“我的队列”结构体指针,因此需要动态申请一个“我的队列”结构体内存空间,并用“我的队列”指针变量接收。随后,调用栈的初始化函数,初始化“我的队列”结构体中的两个栈。
3.“我的队列”入队
由于栈和队列都是从尾部存储数据,因此“我的队列”入队只需将数据入栈进入一个栈即可。
此处选择栈s1作为入栈对象。
4.“我的队列”出队
由于栈删除数据是从尾部删除,而队列删除数据是从头部删除,所以要删除“我的队列”的数据,需要利用栈s1和s2来倒一下数据。先将栈s1中的前n-1个数据入栈到s2中,栈s1的栈底元素直接出栈,无需入栈到栈s2中。然后再将栈s2中的数据全部入栈到栈s1中,由此来实现“我的队列”出队。
5.“我的队列”取队头元素
由于取队头元素是在数据头部进行操作,而栈只能从数据尾部进行操作,因此仍然需要利用两个栈倒一下数据。先将栈s1中的前n-1个数据入栈到栈s2中,然后将栈底元素返回,再将栈s2中的数据重新入栈到s1中,由此来实现“我的队列”取队头元素。
6.“我的队列”判空
由于“我的队列”使用栈s1存储数据的,因此判断“我的队列”是否为空,只要判断栈s1是否为空即可。
7.“我的队列”销毁
先调用栈销毁函数将“我的队列”结构体中的两个栈销毁,再用free函数动态清理掉“我的队列”
三、代码
//栈的结构定义
typedef int STDataType;
typedef struct Stack{
STDataType *a;
int top;
int capacity;
}ST;
//栈的初始化
void STInit(ST* pst)
{
pst->a=NULL;
pst->top=0;
pst->capacity=0;
}
//栈的扩容
void checkcapacity(ST* pst)
{
if(pst->top==pst->capacity)
{
int newcapacity=pst->capacity==0?4:pst->capacity*4;
STDataType* tmp=(STDataType*)realloc(pst->a,sizeof(STDataType)*newcapacity);
if(tmp==NULL)
{
perror("realloc fail");
exit(-1);
}
pst->a=tmp;
pst->capacity=newcapacity;
}
}
//入栈
void STPush(ST* pst,STDataType x)
{
assert(pst);
checkcapacity(pst);
pst->a[pst->top++]=x;
}
//出栈
void STPop(ST* pst)
{
assert(pst);
assert(pst->top);//空栈
pst->top--;
}
//取栈顶元素
STDataType STTop(ST* pst)
{
assert(pst);
assert(pst->top);//空栈
return pst->a[pst->top-1];
}
//判断栈是否为空
bool STEmpty(ST* pst)
{
return pst->top==0;
}
//销毁栈
void STDestroy(ST* pst)
{
assert(pst);
free(pst->a);
pst->a=NULL;
pst->top=0;
pst->capacity=0;
}
//我的队列
typedef struct {
ST s1;
ST s2;
} MyQueue;
//我的队列的创建及其初始化
MyQueue* myQueueCreate() {
MyQueue* myqueue=(MyQueue*)malloc(sizeof(MyQueue));
if(myqueue==NULL)
{
perror("malloc fail");
exit(-1);
}
STInit(&myqueue->s1);
STInit(&myqueue->s2);
return myqueue;
}
//我的队列入队
void myQueuePush(MyQueue* obj, int x) {
STPush(&obj->s1,x);
}
//我的队列出队
int myQueuePop(MyQueue* obj) {
while(obj->s1.top>1)
{
STPush(&obj->s2,STTop(&obj->s1));
STPop(&obj->s1);
}
int tmp=STTop(&obj->s1);
STPop(&obj->s1);
while(obj->s2.top>0)
{
STPush(&obj->s1,STTop(&obj->s2));
STPop(&obj->s2);
}
return tmp;
}
//我的队列取队头元素
int myQueuePeek(MyQueue* obj) {
while(obj->s1.top>1)
{
STPush(&obj->s2,STTop(&obj->s1));
STPop(&obj->s1);
}
int tmp=STTop(&obj->s1);
while(obj->s2.top>0)
{
STPush(&obj->s1,STTop(&obj->s2));
STPop(&obj->s2);
}
return tmp;
}
//我的队列判空
bool myQueueEmpty(MyQueue* obj) {
return STEmpty(&obj->s1);
}
//我的队列销毁
void myQueueFree(MyQueue* obj) {
STDestroy(&obj->s1);
STDestroy(&obj->s2);
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);