一、题目
原题链接：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);
