前言
进入栈和队列之后必须马上开始我的练习.
下面是两个力扣的简单题目.
分别是用栈实现队列
和用队列实现栈
这两道题倒是都不难,但是对于刚刚进入栈和队列学习的朋友还是有些意思和锻炼的😎.
总的来说,值得一搞.
防止有人忘记了:
栈: 后来的先出.
队列: 像排队一样先来先出.
用栈实现队列
栈实现队列
大致思路
通过两个栈来实现队列的功能函数实现,
如顺序输入:
12345
我们栈是54321顺序出
队列是12345顺序出
我们可以用两个栈将12345的输入12345输出
比如一个栈存储12345,我们把这些数据一个个输入到另一个栈中那么另一个栈就存储了54321.这样我们从另一个栈读取数据时就是12345的读取了,也就符合了我们对队列的需要.
当然我们用c来实现这个问题的时候我们需要栈的函数接口博主就分享给大家
typedef int STDateType; typedef struct Stack { int top; int capacity; STDateType* date; }ST; void StackInit(ST* stack) { stack->date = malloc(sizeof(ST) * 4); stack->capacity = 4; stack->top = 0; } void StackDestroy(ST* stack) { free(stack->date); stack->date = NULL; stack->top = stack->capacity = 0; } void StackPush(ST* stack, STDateType x) { assert(stack); if (stack->top == stack->capacity) { STDateType* new = realloc(stack->date, (size_t)stack->capacity * 2); if (new == NULL) { perror("StackPush new \n"); exit(-1); } else { stack->date = new; } } stack->date[stack->top] = x; stack->top++; } void StackPop(ST* stack) { assert(stack); if (stack->top >0 ) { stack->top--; } else { printf("栈为空不能删除\n"); return; } } STDateType StackTop(ST* stack) { assert(stack); assert(stack->top > 0); return stack->date[stack->top-1]; } int StackSize(ST* stack) { assert(stack); return stack->top; } bool StackEmpty(ST* stack) { assert(stack); return stack->top == 0; }
这些函数接口都在我之前的博客👉栈和队列(跑路人笔记)中有讲解.
正确代码
typedef struct { ST push; ST pop; } MyQueue; MyQueue* myQueueCreate() { MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue)); StackInit(&obj->push); StackInit(&obj->pop); return obj; } void myQueuePush(MyQueue* obj, int x) { assert(obj); StackPush(&obj->push,x); } int myQueuePop(MyQueue* obj) { assert(obj); if(StackEmpty(&obj->pop)) { while(!StackEmpty(&obj->push)) { int top = StackTop(&obj->push); StackPush(&obj->pop,top); StackPop(&obj->push); } } int ret = StackTop(&obj->pop); StackPop(&obj->pop); return ret; } int myQueuePeek(MyQueue* obj) { assert(obj); if(StackEmpty(&obj->pop)) { while(!StackEmpty(&obj->push)) { int top = StackTop(&obj->push); StackPush(&obj->pop,top); StackPop(&obj->push); } } return StackTop(&obj->pop); } bool myQueueEmpty(MyQueue* obj) { assert(obj); if(StackEmpty(&obj->push)&&StackEmpty(&obj->pop)) { return true; } else { return false; } } void myQueueFree(MyQueue* obj) { assert(obj); StackDestroy(&obj->pop); StackDestroy(&obj->push); 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); */
函数功能及注意点讲解
typedef struct { ST push; ST pop; } MyQueue; MyQueue* myQueueCreate() { MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue)); assert(obj); StackInit(&obj->push); StackInit(&obj->pop); return obj; }
(ST是栈结构的变量结构体)结构体里一个用于接收数据一个用于删除和推出数据.
MyQueue* myQueueCreate();
这个函数是用来我们队列部分的创建和初始化.然后将我们创建好的变量返回
值得注意的是
obj需要在堆区开辟,不然出了函数就没有了.
StackInit是我们自己的栈函数传参时要记得取地址.
obj的空指针判断可以有也可以没有因为后面的会有对obj的判空🤪.
void myQueuePush(MyQueue* obj, int x) { assert(obj); StackPush(&obj->push,x); } int myQueuePop(MyQueue* obj) { assert(obj); if(StackEmpty(&obj->pop)) { while(!StackEmpty(&obj->push)) { int top = StackTop(&obj->push); StackPush(&obj->pop,top); StackPop(&obj->push); } } int ret = StackTop(&obj->pop); StackPop(&obj->pop); return ret; }
push的时候就很简单放入obj->push里就完事.
删除时
当obj->pop为空的时候就直接吧obj->push的所用元素全部都放到pop里.
然后根据题目要求要把顶部元素返回就可以直接在obj->pop的栈顶元素返回即可.
int myQueuePeek(MyQueue* obj) { assert(obj); if(StackEmpty(&obj->push)&&StackEmpty(&obj->pop)) { printf("队列为空无元素\n"); return -1; } if(StackEmpty(&obj->pop)) { while(!StackEmpty(&obj->push)) { int top = StackTop(&obj->push); StackPush(&obj->pop,top); StackPop(&obj->push); } } return StackTop(&obj->pop); } bool myQueueEmpty(MyQueue* obj) { assert(obj); if(StackEmpty(&obj->push)&&StackEmpty(&obj->pop)) { return true; } else { return false; } } void myQueueFree(MyQueue* obj) { assert(obj); StackDestroy(&obj->pop); StackDestroy(&obj->push); free(obj); }
myQueuePeek是得到队列顶的元素.
这个if条件是防止pop内元素为空.
当obj->pop内的元素为空时.
我们要把存储在obj->push内的元素转移到obj->pop中.
如果pop和push都没有元素可以加个if条件.
myQueueEmpty
obj内无元素的时候返回true.
myQueueFree
将两个栈的元素全部free咯.
记得吧obj free了👍.
无了=-=.
