LeetCode | 232. 用栈实现队列
解题思路：
- 此题可以用两个栈实现，一个栈进行入队操作，另一个栈进行出队操作
- 出队操作： 当出队的栈不为空是，直接进行出栈操作，如果为空，需要把入队的栈元素全部导入到出队的栈，然后再进行出栈操作
- 入数据，往
pushST入 - 出数据，看
popST有没有数据，有的话直接出，如果popST没有数据，把pushST数据导入到popST，然后再出数据
代码实现：
#include<stdio.h> #include<stdlib.h> #include<stdbool.h> #include<assert.h> typedef int STDataType; typedef struct Stack { STDataType* a; int capacity; int top; }ST; void StackInit(ST* ps); // 入栈 void StackPush(ST* ps, STDataType x); // 出栈 void StackPop(ST* ps); // 获取栈顶元素 STDataType StackTop(ST* ps); // 获取栈中有效元素个数 int StackSize(ST* ps); // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 bool StackEmpty(ST* ps); // 销毁栈 void StackDestroy(ST* ps); void StackInit(ST* ps) { assert(ps); ps->a = NULL; ps->capacity = ps->top = 0; } void StackPush(ST* ps, STDataType x) { assert(ps); if (ps->capacity == ps->top) { STDataType newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity); if (tmp == NULL) { perror("realloc fail!\n"); return; } ps->capacity = newcapacity; ps->a = tmp; } ps->a[ps->top] = x; ps->top++; } // 出栈 void StackPop(ST* ps) { assert(ps); assert(ps->top > 0); ps->top--; } // 获取栈顶元素 STDataType StackTop(ST* ps) { assert(ps); assert(ps->top > 0); return ps->a[ps->top - 1]; } // 获取栈中有效元素个数 int StackSize(ST* ps) { assert(ps); return ps->top; } // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; } // 销毁栈 void StackDestroy(ST* ps) { assert(ps); ps->a = NULL; ps->capacity = ps->top = 0; } typedef struct { ST pushst; ST popst; } MyQueue; MyQueue* myQueueCreate() { MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue)); StackInit(&obj->pushst); StackInit(&obj->popst); return obj; } void myQueuePush(MyQueue* obj, int x) { StackPush(&obj->pushst,x); } int myQueuePeek(MyQueue* obj) { if(!StackEmpty(&obj->popst)) { return StackTop(&obj->popst); } else { while(!StackEmpty(&obj->pushst)) { StackPush(&obj->popst,StackTop(&obj->pushst)); StackPop(&obj->pushst); } return StackTop(&obj->popst); } } int myQueuePop(MyQueue* obj) { int front = myQueuePeek(obj); StackPop(&obj->popst); return front; } bool myQueueEmpty(MyQueue* obj) { return StackEmpty(&obj->pushst) && StackEmpty(&obj->popst); } void myQueueFree(MyQueue* obj) { StackDestroy(&obj->popst); StackDestroy(&obj->pushst); free(obj); }
