LeetCode刷题(8)【栈&队列】用栈实现队列(C语言) |
您所在的位置：网站首页 › 用一个栈实现队列 › LeetCode刷题(8)【栈&队列】用栈实现队列(C语言) |
LeetCode刷题(8)【栈&队列】用栈实现队列(C语言)
|
用栈实现队列 232. 用栈实现队列 - 力扣（LeetCode） (leetcode-cn.com) 类似题目——用队列实现栈 LeetCode刷题(7)【栈&队列】用队列实现栈(C语言)_半生瓜のblog-CSDN博客 思路：
用栈实现队列要比用队列实现栈要简单一些，我们不用来回在两个栈里面导数据，只需要导一次，然后在依次出栈就成功实现队列的出队操作了。
结论： 入数据往push栈里面入出数据从pop栈里面出，如果里面有数据，直接出，没有就把push栈里面的数据导过来，然后再出。代码实现： typedef int StackDataType; typedef struct Stack { StackDataType* arry; int top;//指向栈顶 int capacity;//栈的容量——能放几个数据 }Stack; //初始化 void StackInit(Stack* ps) { assert(ps); ps->arry = (StackDataType*)malloc(sizeof(StackDataType)*4); if (ps->arry == NULL) { printf("malloc fail"); exit(-1); } ps->capacity = 4; ps->top = 0; } //销毁 void StackDestory(Stack* ps) { assert(ps); free(ps->arry); ps->arry = NULL; ps->top = ps->capacity =0 ; } //入栈 void StackPush(Stack* ps, StackDataType x) { assert(ps); //满了 if (ps->top == ps->capacity) { StackDataType* tmp = (StackDataType*)realloc(ps->arry, ps->capacity * 2 * sizeof(StackDataType)); if (tmp == NULL) { printf("realloc fail"); exit(-1); } else { ps->arry = tmp; ps->capacity *= 2; } } ps->arry[ps->top] = x; ps->top++; } //出栈 void StackPop(Stack* ps) { assert(ps); //如果栈空了调用top，直接终止程序报错 assert(ps->top > 0); ps->top--; } //返回栈顶元素 StackDataType StackTop(Stack* ps) { assert(ps); assert(ps->top > 0); return ps->arry[ps->top - 1]; } //返回栈中元素个数 int StackSize(Stack* ps) { assert(ps); return ps->top; } //是否为空 bool StackEmpty(Stack* ps) { assert(ps); return ps->top == 0;//真为空，假为非空。 } // typedef struct { Stack pushST; Stack popST; } MyQueue; /** Initialize your data structure here. */ MyQueue* myQueueCreate() { MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue)); if(q == NULL) { printf("malloc is fail!"); return; } StackInit(&q->pushST); StackInit(&q->popST); return q; } /** Push element x to the back of queue. */ void myQueuePush(MyQueue* obj, int x) { //入数据就往pushST里面入 StackPush(&obj->pushST,x); } /** Removes the element from in front of queue and returns that element. */ int myQueuePop(MyQueue* obj) { //类似于下面的peek // if(StackEmpty(&obj->popST)) // { // while(!StackEmpty(&obj->pushST)) // { // StackPush(&obj->popST,StackTop(&obj->pushST)); // StackPop(&obj->pushST); // } // } // int top = StackTop(&obj->popST); /// //或者直接调用下面的myQueuePeek函数直接获取popST的栈顶元素 //保存给top之后删除，然后return int top = myQueuePeek(obj); StackPop(&obj->popST); return top; } /** Get the front element. */ int myQueuePeek(MyQueue* obj) { //出数据要从popST里面出 //如果popST里面是空的 //就要先从pushST里面拿 if(StackEmpty(&obj->popST)) { //把pushST里面的元素导到popST里面 //然后取第一个 while(!StackEmpty(&obj->pushST)) { //取pushST最上面的元素依次压进popST StackPush((&obj->popST),StackTop(&obj->pushST)); StackPop(&obj->pushST); } } return StackTop(&obj->popST); } /** Returns whether the queue is empty. */ bool myQueueEmpty(MyQueue* obj) { return StackEmpty(&obj->popST) && StackEmpty(&obj->pushST); } 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); */ |
【本文地址】