用栈实现队列——leetcode刷题

news/2024/5/20 14:39:06

题目要求我们只用栈的基本操作 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;
}

这里我我同样使用了外部函数，可以整合一下。

这就是文章的全部内容了，希望对你有所帮助，如有错误欢迎评论。