本文主要是介绍用栈实现队列——leetcode刷题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目要求我们只用栈的基本操作 push to top 入栈,peek from top 返回栈顶元素,pop from top 移除并返回栈顶元素,size 栈的大小,is_empty 判断栈是否为空,这几个函数来实现队列,也就是说,我们在队列函数push pop peek empty函数中要调用栈的函数实现。
首先栈的特点是先进后出,队列的特点是先进先出,如何用两个栈来实现先进先出,我们想到可以把一个栈压入另外一个栈,此时第二个栈的顺序相对第一个就是一个倒序,此时在出栈就是相当于首元素出栈,就相当于队列的逻辑。如图所示,我们还要做的就是把 栈2 的剩余元素重新入栈更新 栈1 。
我们可以把 栈1 理解为队列的真实情况,栈2 只是出队列时寻找队头的工具(负责逆序栈),每次出队列之后都要重新更新 栈1 ,更新队列。
接下来就是代码实现:
typedef struct {struct Stacklist* p1;struct Stacklist* p2;
} MyQueue;
struct Stacklist* Stackcreat() {struct Stacklist* p = (struct Stacklist*)malloc(sizeof(struct Stacklist));return p;
}
void StackInit(struct Stacklist* stack) {stack->cap = 0;stack->size = 0;stack->val = NULL;
}
MyQueue* myQueueCreate() {MyQueue* list = (MyQueue*)malloc(sizeof(MyQueue));list->p1 = Stackcreat();list->p2 = Stackcreat();StackInit(list->p1);StackInit(list->p2);return list;
}
首先是Queue队列结构体的成员,两个指向栈的指针:栈1 p1,栈2 p2 。其次是创建队列指针,创建队列中两个栈的指针,对他们进行初始化。(这里使用了题目要求之外的函数,个人感觉不妥,当然可以自己写一下)
接着是入队列函数:
void myQueuePush(MyQueue* obj, int x) {StackPush(obj->p1, x);
}
直接就是入栈函数,因为进入第一个栈就相当于是入队列了。
然后是出队列函数 Pop(移除元素):
int myQueuePop(MyQueue* obj) {while (!is_empty(obj->p1)) {StackPush(obj->p2, StackPop(obj->p1));}int val = StackPop(obj->p2);while (!is_empty(obj->p2)) {StackPush(obj->p1, StackPop(obj->p2));}return val;
}
我们先把 栈1 的元素压入 栈2 中去,即StackPush(obj->p2, StackPop(obj->p1)); 条件是 栈1 不为空,当条件不满足则说明 栈1 中元素已经全部拷贝到 栈2 中去,接着让 栈2 出栈,记录出栈的数值,然后再把 栈2 拷贝回 栈1 。这一流程就是刚才的图的流程。
然后是查看队头数值函数 Peek(不移除元素,仅查看):
int myQueuePeek(MyQueue* obj) {while (!is_empty(obj->p1)) {StackPush(obj->p2, StackPop(obj->p1));}int val = StackPeek(obj->p2);while (!is_empty(obj->p2)) {StackPush(obj->p1, StackPop(obj->p2));}return val;
}
逻辑和出队列函数一样,只不过val赋值时使用的是StackPeek函数,也就是只查看不删除的"出栈"函数。
最后是判断队列是否为空的函数:
bool myQueueEmpty(MyQueue* obj) {if (is_empty(obj->p1)) {return true;}else {return false;}
}
直接根据 栈1 是否为空来判断队列是否为空即可,因为我们每次都会拷贝回 栈1 保证 栈1 是队列的真实元素。
最后补充一下销毁函数:
void myQueueFree(MyQueue* obj) {StackDes(obj->p1);StackDes(obj->p2);free(obj);obj = NULL;
}
void StackDes(struct Stacklist* stack) {free(stack->val);stack->val = NULL;
}
这里我我同样使用了外部函数,可以整合一下。
这就是文章的全部内容了,希望对你有所帮助,如有错误欢迎评论。
这篇关于用栈实现队列——leetcode刷题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!