前言：本节博客分享了用栈实现队列效果的思路以及代码，有需要借鉴即可。
1.题目及链接
2.思路分析
如果要用栈实现队列，我们直到栈是先入后出的一个效果，所以我们可以用两个栈，这样逆转两次数不就是入栈之前数组的顺序嘛。下面是一些图辅助理解：
3.代码示例
#include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> //用数组的方式实现栈结构 typedef int STDateType; typedef struct Stack { STDateType* arr; int top; int capacity; }ST; //初始化与销毁 void StackInit(ST* ps); void StackDestroy(ST* ps); //入栈出栈 void StackPush(ST* ps,STDateType x); STDateType StackTop(ST* ps); void StackPop(ST* ps); //统计与判断 bool StackEmpty(ST* ps); int StackSize(ST* ps); void StackInit(ST* ps) { assert(ps); ps->arr = NULL; ps->capacity = ps->top = 0; } void StackDestroy(ST* ps) { assert(ps); free(ps->arr); ps->arr = NULL; ps->capacity = ps->top = 0; ps = NULL; } void StackPush(ST* ps, STDateType x) { assert(ps); if (ps->capacity == ps->top) { //初始值的情况 int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; STDateType* temp = (STDateType*)realloc(ps->arr, newcapacity * sizeof(STDateType)); if (temp == NULL) { perror("malloc fail!"); exit(-1); } ps->arr = temp; ps->capacity = newcapacity; } ps->arr[ps->top++] = x; } void StackPop(ST* ps) { assert(ps); assert(ps->top > 0); ps->top--; } STDateType StackTop(ST* ps) { assert(ps); return ps->arr[ps->top - 1]; } bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; } int StackSize(ST* ps) { assert(ps); return ps->top; } typedef struct { ST pushtack; ST poptack; } MyQueue; MyQueue* myQueueCreate() { //首先要创建一个队列结构体 MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue)); //对队列结构体中的栈做初始化调整 StackInit(&obj->pushtack); StackInit(&obj->poptack); //返回 return obj; } //将元素 x 推到队列的末尾 void myQueuePush(MyQueue* obj, int x) { //插入数据 StackPush(&obj->pushtack,x); } //返回队列开头的元素 int myQueuePeek(MyQueue* obj) { //分两种情况:1.poptack为空2.poptack不为空 if(StackEmpty(&obj->poptack))//为空需要导数据 { while(!StackEmpty(&obj->pushtack)) { int top = StackTop(&obj->pushtack);//取出push数据 StackPop(&obj->pushtack);//删除pop数据 StackPush(&obj->poptack,top);//放入push } } //poptack不为空 return StackTop(&obj->poptack); } //从队列的开头移除并返回元素 int myQueuePop(MyQueue* obj) { int front = myQueuePeek(obj);//取出 StackPop(&obj->poptack);//删除 return front;//返回 } //如果队列为空，返回 true ；否则，返回 false bool myQueueEmpty(MyQueue* obj) {//两个都为空 return StackEmpty(&obj->pushtack)&&StackEmpty(&obj->poptack); } //释放 void myQueueFree(MyQueue* obj) { StackDestroy(&obj->pushtack); StackDestroy(&obj->poptack); 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); */
完。
