---

题目描述

原题：232. 用栈实现队列

思路分析

有了前面的用队列实现栈的基础我们不难想到这题的基本思路，也就是用两个栈来实现队列，（栈的实现具体参考：栈及其接口的实现）

typedef struct {Stack PushSt;Stack PopSt;
} MyQueue;

PushSt用来插入数据
PopSt用来出数据

入队列那直接对PushSt进行入栈即可；

那也就我们只要进行出队列或去对头元素我们就需要将PushSt栈中的元素依次入栈到PopSt中，我们就可以就这个功能写一个专用的接口：

void PushStToPopSt(MyQueue* obj)
{if (StackEmpty(&obj->PopSt)){while(!StackEmpty(&obj->PushSt)){StackPush(&obj->PopSt,StackTop(&obj->PushSt));StackPop(&obj->PushSt);}}
}

这样实现这题就不难了：

开辟队列

如果这里用MyQueue q来创建队列，由于在函数内是个局部变量，所以会创建失败；

MyQueue* myQueueCreate() {MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));if(q == NULL){perror("malloc");exit(-1);}StackInit(&q->PushSt);StackInit(&q->PopSt);return q;
}

入队列

根据上面的分析，很容易写出：

void myQueuePush(MyQueue* obj, int x) {StackPush(&obj->PushSt,x);}

出队列

同上面的分析：

int myQueuePop(MyQueue* obj) {PushStToPopSt(obj);int ret = StackTop(&obj->PopSt);StackPop(&obj->PopSt);return ret;
}

代码展示

typedef int STDataType;// 支持动态增长的栈
typedef struct Stack
{STDataType* _a;int _top;  //栈顶指针int _capacity; //动态容量
}Stack;//栈的初始化
void StackInit(Stack* pst);//栈的销毁
void StackDestory(Stack* pst);//入栈
void StackPush(Stack* pst, STDataType x);//出栈
void StackPop(Stack* pst);//获取数据的个数
int StackSize(Stack* pst);    //考虑到内存和统一性问题我们这里也传一级指针//判空，1是空，0是非空
int StackEmpty(Stack* pst);//获取栈顶数据
STDataType StackTop(Stack* pst);//栈的初始化
void StackInit(Stack* pst)
{assert(pst);//这样会给后面扩容造成麻烦/*pst->_a = NULL;pst->_top = 0;pst->_capacity = 0;*/pst->_a = (STDataType*)malloc(sizeof(STDataType) * 4);pst->_top = 0;pst->_capacity = 4;
}//栈的销毁
void StackDestory(Stack* pst)
{assert(pst);free(pst->_a); //释放开辟的空间pst->_a = NULL;pst->_top = pst->_capacity = 0;
}//入栈
void StackPush(Stack* pst, STDataType x)
{//检查是否需要扩容if (pst->_top == pst->_capacity){pst->_capacity *= 2;STDataType* tmp = (STDataType*)realloc(pst->_a, sizeof(STDataType) * pst->_capacity);if (tmp == NULL){perror("relloc");exit(-1);}else{pst->_a = tmp;}}pst->_a[pst->_top] = x;pst->_top++;
}//出栈
void StackPop(Stack* pst)
{assert(pst);assert(pst->_top > 0);//只需要将top一走，可以不用初始化出栈的值//pst->_a[pst->_top] = 0;pst->_top--;
}//获取数据的个数
int StackSize(Stack* pst)   //考虑到内存和统一性问题我们这里也传一级指针
{assert(pst);return pst->_top;
}//判空，1是空，0是非空
int StackEmpty(Stack* pst)
{assert(pst);//return pst->_top == 0 ? 1 : 0;return !pst->_top;
}//获取栈顶数据
STDataType StackTop(Stack* pst)
{assert(pst);assert(pst->_top);return pst->_a[pst->_top-1];
}typedef struct {Stack PushSt;Stack PopSt;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));if(q == NULL){perror("malloc");exit(-1);}StackInit(&q->PushSt);StackInit(&q->PopSt);return q;
}void myQueuePush(MyQueue* obj, int x) {StackPush(&obj->PushSt,x);}void PushStToPopSt(MyQueue* obj)
{if (StackEmpty(&obj->PopSt)){while(!StackEmpty(&obj->PushSt)){StackPush(&obj->PopSt,StackTop(&obj->PushSt));StackPop(&obj->PushSt);}}
}int myQueuePop(MyQueue* obj) {PushStToPopSt(obj);int ret = StackTop(&obj->PopSt);StackPop(&obj->PopSt);return ret;
}int myQueuePeek(MyQueue* obj) {PushStToPopSt(obj);return StackTop(&obj->PopSt);
}bool myQueueEmpty(MyQueue* obj) {return StackEmpty(&obj->PushSt) && StackEmpty(&obj->PopSt);
}void myQueueFree(MyQueue* obj) {StackDestory(&obj->PushSt);StackDestory(&obj->PopSt);free(obj);
}/*** 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);
*/

也是通过了leetcode：

完

---