232. 用栈实现队列 - 力扣（LeetCode）
总体思路
思路：由于C语言阶段没有相对应的栈库，所以我们需要手搓一个栈，再在此基础上来实现这道题，题目所由多个接口函数所构成 ，在开始写代码前，我们需要在自己的队列结构中创建两个栈变量，因为经过分析我们发现，我们定义两个栈分别进行删除和插入操作是非常完美的。
typedef struct {
Stack Pushl;
Stack Popl;
} MyQueue;再有了这个之后，我们需要为他开辟空间，从而进行下面的操作，这里使用malloc开辟空间，并且初始化结构体中的两个栈，当然如果你构造的结构体里面是两个指针的话，首先会出现野指针问题，因为指针不赋值的话就是野指针了，还有就是你定义的是指针，你用malloc开辟空间时并没有开辟了空间，反而是开辟了指针。这里如果你非得想用指针的话，在下面的初始化接口中还得传递二级指针，因为你想改变这个指针嘛！这里为了简单，所以我们定义的是两个常量。
MyQueue* myQueueCreate() {
MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));
StackInit(&obj->Pushl);
StackInit(&obj->Popl);
return obj;
}
然后我们继续实现接口函数，我们来看插入函数，对插入来说，我们左侧就单纯执行插入
void myQueuePush(MyQueue* obj, int x) {
StackPush(&obj->Pushl,x);
}接下来我们写的并不是删除，我们写的是peek()这个接口，也就是返回顶部元素，对上图来说如果右侧有值的话，并且也没有删除的话，那栈顶就是1，那就直接取就好了是吧，但是如果右侧为空时，我们得先判断左侧是否有值，如果有，得把值给右侧。然后再取右侧的栈顶。
int myQueuePeek(MyQueue* obj) {
if(StackEmpty(&obj->Popl))
{
while(!StackEmpty(&obj->Pushl))
{
int top=STTop(&obj->Pushl);
StackPop(&obj->Pushl);
StackPush(&obj->Popl,top);
}
}
return STTop(&obj->Popl);
}接下来就是pop函数了，还是那句话，就是如果pop有值，就直接删除，倘若没有值，就看左侧，如果左侧有值就移动到右侧，再删除，这段话是不是有点耳熟，跟上面peek函数功能中有些类似，所以借用peek函数。
int myQueuePop(MyQueue* obj) {
int top=myQueuePeek(obj);
StackPop(&obj->Popl);
return top;
}对与判断他是否为空和销毁，判断是否为空呢，就是左右两侧必须都为空才为空，销毁时，记得先销毁结构体中的两个栈常量。
bool myQueueEmpty(MyQueue* obj) {
return StackEmpty(&obj->Pushl)&&StackEmpty(&obj->Popl);
}
void myQueueFree(MyQueue* obj) {
StackDestroy(&obj->Pushl);
StackDestroy(&obj->Popl);
free(obj);
}在oj中呢，是不用写头文件的
代码
//支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;//栈
int capacity;//容量
}Stack;
//初始化栈
void StackInit(Stack* ps);
//入栈
void StackPush(Stack* ps, STDataType data);
//出栈
void StackPop(Stack* ps);
//获取栈中有效元素个数
int StackSize(Stack* ps);
//检测栈中是否为空，如果为空返回非零结果，如果不为空返回0
int StackEmpty(Stack* ps);
//获取栈顶元素
STDataType STTop(Stack* ps);
//销毁栈
void StackDestroy(Stack* ps);
//初始化栈
void StackInit(Stack* ps)
{
assert(ps);
ps->a = NULL;
ps->capacity = ps->top = 0;
}
//入栈
void StackPush(Stack* ps, STDataType data)
{
assert(ps);
if (ps->capacity == ps->top)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
if (tmp == NULL)
{
perror("realloc fail");
return;
}
ps->a = tmp;
ps->capacity = newcapacity;
}
ps->a[ps->top++] = data;
}
//出栈
void StackPop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
zzzzz
ps->top--;
}
//获取栈中有效元素个数
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
//检测栈中是否为空，如果为空返回非零结果，如果不为空返回0
int StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}
//获取栈顶元素
STDataType STTop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->a[ps->top - 1];
}
//销毁栈
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = ps->top = 0;
}
typedef struct {
Stack Pushl;
Stack Popl;
} MyQueue;
MyQueue* myQueueCreate() {
MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));
StackInit(&obj->Pushl);
StackInit(&obj->Popl);
return obj;
}
void myQueuePush(MyQueue* obj, int x) {
StackPush(&obj->Pushl,x);
}
int myQueuePop(MyQueue* obj) {
int top=myQueuePeek(obj);
StackPop(&obj->Popl);
return top;
}
int myQueuePeek(MyQueue* obj) {
if(StackEmpty(&obj->Popl))
{
while(!StackEmpty(&obj->Pushl))
{
int top=STTop(&obj->Pushl);
StackPop(&obj->Pushl);
StackPush(&obj->Popl,top);
}
}
return STTop(&obj->Popl);
}
bool myQueueEmpty(MyQueue* obj) {
return StackEmpty(&obj->Pushl)&&StackEmpty(&obj->Popl);
}
void myQueueFree(MyQueue* obj) {
StackDestroy(&obj->Pushl);
StackDestroy(&obj->Popl);
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);
*/
