题目：

232. 用栈实现队列 - 力扣（LeetCode）

这题跟我们之前写过的 用队列实现栈 很像，感兴趣的可以自行了解一下。

题目内容

准备工作

这题明确说明了需要用栈来实现队列，介于C语言没有队列的库，所以在此之前我们需要用调用之前学的栈，详见栈

我们如果之前写过的话，直接复制过来就可以了，由于重点是讲用栈实现队列，所以这里就不过多了解栈了。

typedef int STDataType;
struct Stack
{STDataType* a;int top;       // 栈顶int capacity;  // 容量，方便增容
};//typedef struct Stack ST;
typedef struct Stack Stack;void StackInit(Stack* pst);
void StackDestroy(Stack* pst);// 性质就决定在栈顶出入数据
void StackPush(Stack* pst, STDataType x);
void StackPop(Stack* pst);
STDataType StackTop(Stack* pst);bool StackEmpty(Stack* pst);
int StackSize(Stack* pst);void StackInit(Stack* pst)
{assert(pst);pst->a = (STDataType*)malloc(sizeof(STDataType) * 4);pst->top = 0;pst->capacity = 4;
}void StackDestroy(Stack* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->capacity = pst->top = 0;
}// 性质就决定在栈顶出入数据
void StackPush(Stack* pst, STDataType x)
{assert(pst);if (pst->top == pst->capacity){STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType)*pst->capacity * 2);if (tmp == NULL){printf("realloc fail\n");exit(-1); // 结束整个程序}pst->a = tmp;pst->capacity *= 2;}pst->a[pst->top] = x;pst->top++;
}void StackPop(Stack* pst)
{assert(pst);assert(!StackEmpty(pst));pst->top--;
}STDataType StackTop(Stack* pst)
{assert(pst);assert(!StackEmpty(pst));return pst->a[pst->top - 1];
}bool StackEmpty(Stack* pst)
{assert(pst);return pst->top == 0;
}int StackSize(Stack* pst)
{assert(pst);return pst->top;
}

看懂题

这样之后，我们有些小伙伴觉得自己英语不好，看不懂那些函数名，从而放弃这题，其实这里和英语好不好是没有太多关系的。注意看：

我们通过返回值大概了解了，题目中函数的含义。

创建结构体

“typedef struct”这个函数，有过对数据结构的基础认识，看到“struct”肯定是创建结构体。创建出的结构体决定了我们之下来的解题思路。所以我们先来了解一下实现这题的基本思路：

用栈实现队列的基本思路

我们如此反复倒数据，每次到最后一个元素就把它pop掉，所以我们避免不了要用到两个指针，指向两个链表的指针。如此一来“typedef struct”这个函数就容易实现了。

typedef struct 
{//定义两个栈指针Stack* pop;Stack* push;
} MyQueue;

创建空间

“MyQueue* myQueueCreate() ”我们有了结构体，一定要初始化，不初始化会导致结构体内部的值不确定，容易出错。现在最新的“vs”如果不初始化，都编译不了了。

 MyQueue* myQueueCreate() 
{MyQueue* ps = (MyQueue*)malloc(sizeof(MyQueue));if(ps == NULL){perrof("malooc:");excit(-1);}//初始化StackInit(&obj->pop);StackInit(&obj->push);return ps;
}

入栈

这个只要我们把push里的数据导入pop里就行了。

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

出栈

上图分析了，这个要分有无数据两种情况讨论。

int myQueuePop(MyQueue* obj) 
{if(StackEmpty(&obj->pop)){//倒数据while(!StackEmpty(&obj->push)){StackPush(&obj->pop, StackTop(&obj->push));StackPop(&obj->push);}}else{StackTop(&obj->pop);}
}

获取元素

这里还是要分两种情况，但是我们可以取巧一点：我们假设，pop有数据的时候，我们直接取顶，或者直接调用上文写的出栈函数；pop无数据的时候，我们就倒数据，就行了。

int myQueuePeek(MyQueue* obj) {if (StackEmpty(&obj->pop)){while (!StackEmpty(&obj->push)){StackPush(&obj->pop, StackTop(&obj->push));StackPop(&obj->push);}}return StackTop(&obj->pop);
}

这里我们再来看上文的出栈，发现这里其实可以相互调用的。

int myQueuePop(MyQueue* obj) 
{   int top = myQueuePeek(obj);StackPop(&obj->popST);return top;
}

这样就简化了代码。

判空

两个队列同时为空

bool myQueueEmpty(MyQueue* obj) 
{return StackEmpty(&obj->push) && StackDestory(&obj->pop);
}

释放空间

释放两个链表的同时，不要忘记释放两个指针，避免内存泄漏。

void myQueueFree(MyQueue* obj) 
{StackDestory(&obj->push);StackDestory(&obj->push);free(ps);ps = NULL;
}

总结

我们可以发现原理（几幅图就能搞定）都不难，主要是代码的实现，需要注意许多细节，一定要注意避免内存泄漏。

欢迎大家点赞和评论。