[数据结构]OJ一道------用栈实现队列

题���来源:232. 用栈实现队列 - 力扣（LeetCode）

解题思路来源:力扣官方题解

https://leetcode.cn/problems/implement-queue-using-stacks/solutions/632369/yong-zhan-shi-xian-dui-lie-by-leetcode-s-xnb6/

首先我们先来看题目:

给的代码:

typedef struct {    } MyQueue;MyQueue* myQueueCreate() {    }void myQueuePush(MyQueue* obj, int x) {    }int myQueuePop(MyQueue* obj) {    }int myQueuePeek(MyQueue* obj) {    }bool myQueueEmpty(MyQueue* obj) {    }void myQueueFree(MyQueue* 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);*/

我们知道,这道题目要用栈的操作来实现队列的操作,如果对栈和队列不了解的同学,可以去看看以下两篇文章:

[数据结构]栈-CSDN博客

[数据结构]队列-CSDN博客

我们可以先创建栈,以及其相应的功能

typedef struct {    int* stk;    int stkSize;    int stkCapacity;}Stack;Stack* stackCreate(int cpacity) {    Stack* ret = malloc(sizeof(Stack));    ret->stk = malloc(sizeof(int) * cpacity);    ret->stkSize = 0;    ret->stkCapacity = cpacity;    return ret;}void stackPush(Stack* obj, int x){ obj->stk[obj->stkSize++] = x; }void stackPop(Stack* obj) { obj->stkSize--; }int stackTop(Stack* obj) { return obj->stk[obj->stkSize - 1]; }bool stackEmpty(Stack* obj) { return obj->stkSize == 0; }void stackFree(Stack* obj) { free(obj->stk); }

然后我们来思考如何解决用栈的操作去完成队列的操作?

这里我们选择创建两个栈.

将一个栈当作输入栈，用于压入 push传入的数据；另一个栈当作输出栈，用于 pop 和 peek 操作。

每次 pop 或 peek 时，若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈，这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。

这里我们来举个例子:

我们创建两个栈一个叫IN,用来输入,一个叫OUT,用来输出.

我们我们把一个1234这四个数字分别压入栈

然后我们可以遍历IN栈,然后把存储的内容压入OUT栈,我们知道栈只能头插,所以我们在这些操作后会发现OUT栈和IN栈中数据的顺序颠倒了

注意:要把IN中的元素在压入OUT后删除

因为我们知道队列只能后插,而这样一颠倒正好让原本的前插变成了后插,符合队列入队列的要求

代码示例:

typedef struct {    Stack* inStack;    Stack* outStack;} MyQueue;MyQueue* myQueueCreate() {    MyQueue* ret = malloc(sizeof(MyQueue));    ret->inStack = stackCreate(100);    ret->outStack = stackCreate(100);    return ret;}void in2out(MyQueue* obj) {    while (!stackEmpty(obj->inStack)) {        stackPush(obj->outStack, stackTop(obj->inStack));        stackPop(obj->inStack);    }}void myQueuePush(MyQueue* obj, int x) {     stackPush(obj->inStack, x); }

因为我们知道队列只能头删,而OUT现在正好是颠倒的栈,对其尾删其实就是对输入的数进行头删

代码示例:

int myQueuePop(MyQueue* obj) {    if (stackEmpty(obj->outStack))     {        in2out(obj);    }    int x = stackTop(obj->outStack);    stackPop(obj->outStack);    return x;}

下一个是peek()函数,这个很简单就是输出OUT栈的栈顶的元素

int myQueuePeek(MyQueue* obj) {    if (stackEmpty(obj->outStack)) {        in2out(obj);    }    return stackTop(obj->outStack);}

然后是判断队列是否为空,这里我们可以直接判断两个栈是否是空的如果都是空的,则队列也是空的.

bool myQueueEmpty(MyQueue* obj) {    return stackEmpty(obj->inStack) && stackEmpty(obj->outStack);}

最后别忘了释放空间

void myQueueFree(MyQueue* obj) {    stackFree(obj->inStack);    stackFree(obj->outStack);}

---

本题的解析到此结束,感谢阅读.