把网站做静态化是什么意思,久久网站建设,智慧城市网站建设,翡翠原石网站首页怎么做目录 前言 1. 题目#xff1a;用栈实现队列 2. 思路 3. 分析 3.1 定义 “ 队列 ” 3.2 创建队列 3.3 入队 3.4 队头数据 3.5 出队 3.6 判空和销毁 4.题解 总结 前言 栈和队列是数据结构中的两个重要概念#xff0c;它们在算法和程序设计中都有着广泛的应用。本文将带你深入了… 目录 前言 1. 题目用栈实现队列 2. 思路 3. 分析 3.1 定义 “ 队列 ” 3.2 创建队列 3.3 入队 3.4 队头数据 3.5 出队 3.6 判空和销毁 4.题解 总结 前言 栈和队列是数据结构中的两个重要概念它们在算法和程序设计中都有着广泛的应用。本文将带你深入了解如何使用栈来模拟实现队列让你在解决问题时更加灵活和创新便于大家更深入的理解栈和队列。 1. 题目用栈实现队列 题目描述 题目链接
用栈实现队列https://leetcode.cn/problems/implement-queue-using-stacks/description/
2. 思路 这道题目的解题思路于队列实现栈有很大的相似点。这道题也是给了两个栈要求使用两个栈来实现队列。这里我们可以使用两边倒的方式来模拟实现队列。 假设入栈1、2、3、4那么出栈的顺序就是4、3、2、1如果我们按照出栈的顺序再入栈到另一个栈中空栈再次出栈就可以达到队列出队的效果1、2、3、4
3. 分析 根据上述的思路我们就可以利用两个栈模拟实现队列。思路的大概过程 那么我们来考虑一下特殊的情况如果我们入队了1、2、3、4出队了1和2然后再入队5和6这时候我们考虑一下是否还需要倒一次将剩下的3和4入栈到原栈中然后入栈5和6再将3、4、5、6依次出栈入栈到另外一个栈中 这里其实是不需要在倒一次入队1、2、3、4。出队1和2然后再入队5和6然后再出队出队的顺序是1、2、3、4、5、6。我们可以将5和6入栈到原栈中然后将3和4继续出栈当一个栈为空时再入栈原栈中的数据。过程如下 好的过程分析完之后我们来对每个接口进行实现。题目中依然是没有现成的栈所以我们依然需要 “ 造轮子 ” 前边我们已经实现的栈可以复制过来使用。 3.1 定义 “ 队列 ” 由于我们再模拟队列时需要用到两个栈但调用函数时传两个栈又太麻烦这里我们就使用结构体来定义两个栈MyQueue这样传参时就可以直接传结构体MyQueue指针就可以了。
typedef struct {Stack pushst;Stack popst;
} MyQueue;3.2 创建队列 创建队列就非常简单了我们只需要调用前边实现的InItStack函数将两个栈进行初始化就可以了
MyQueue* myQueueCreate() {MyQueue* obj(MyQueue*)malloc(sizeof(MyQueue));InItStack(obj-pushst);InItStack(obj-popst);return obj;
} 可能对结构体不熟练的同学会有疑惑
问题一 为什么要malloc一个空间这里注意前边我们仅仅只是定义了一个模拟实现的队列定义的是类型并没有创建结构体变量这里malloc也仅仅只是创建一个结构体变量。 问题二 那为什么不直接MyQueue obj这样定义这是在函数内部如果这样创建结构体变量它是创建在栈区一旦出了函数1就会被销毁为了后续的传参所以最好使用malloc在堆区开辟空间。
问题三 初始化两个栈时需要取地址那我们可不可以在定义时直接定义成指针类型例如
Stack* pushst;
Stack* popst; 这当然可以但是如果按照这样的写法那么在创建 “队列” 时就需要malloc给两个栈开辟空间在调用的初始化函数中并没有开辟空间给栈。如果是这样定义
typedef struct {Stack pushst;Stack popst;
} MyQueue; 那么在mallocobj时就已经将两个栈的空间开辟好了。这样也更简单便捷。
3.3 入队 入队就很简单了直接将数据入栈到pushst中。
void myQueuePush(MyQueue* obj, int x) {StackPush(obj-pushst,x);
} 3.4 队头数据 这里为什么先写队头数据呢那是因为出队时不仅需要将队头移除还需要返回被移除队头的数据。所以这里我们先实现队头数据的接口。 想要得到队头数据那就需要将pushst中的元素按照出栈顺序入栈到popst中然后返回popst这个栈的栈顶元素即可过程如下 int myQueuePeek(MyQueue* obj) {if(IsEmpty(obj-popst)){while(!IsEmpty(obj-pushst)){StackPush(obj-popst,TopData(obj-pushst));StackPop(obj-pushst);}}return TopData(obj-popst);
} 这里注意入栈到popst中的条件是popst为空这也与上述的分析对应popst栈为空时才可以继续将pushst中入队元素倒到popst中。 3.5 出队 有了队头数据的接口出队接口的实现就非常简单了在出队前保存一下队头数据popst栈顶数据然后将popst中的栈顶元素出栈最后返回front即可
int myQueuePop(MyQueue* obj) {int frontmyQueuePeek(obj);StackPop(obj-popst);return front;
} 3.6 判空和销毁 判空和销毁的接口也非常简单当两个栈都为空时就表明队列为空代码如下
bool myQueueEmpty(MyQueue* obj) {return (IsEmpty(obj-pushst)IsEmpty(obj-popst));
} 接下来是销毁销毁队列前我们需要先将两个栈销毁最后销毁obj。代码如下
void myQueueFree(MyQueue* obj) {DestoryStack(obj-popst);DestoryStack(obj-pushst);free(obj);
}
4.题解
整体代码如下
typedef int Datatype;
typedef struct Stack
{Datatype* a;int top;int capacity;
}Stack;void InItStack(Stack* ps);void DestoryStack(Stack* ps);void StackPush(Stack* ps, Datatype x);void StackPop(Stack* ps);int Stacksize(Stack* ps);Datatype TopData(Stack* ps);bool IsEmpty(Stack* ps);void InItStack(Stack* ps)
{assert(ps);ps-top 0;ps-a NULL;ps-capacity 0;
}void DestoryStack(Stack* ps)
{assert(ps);ps-top ps-capacity 0;free(ps-a);ps-a NULL;
}
void StackPush(Stack* ps, Datatype x)
{assert(ps);if (ps-top ps-capacity){int newcapacity (ps-capacity 0 ? 4 : ps-capacity * 2);Datatype* tmp (Datatype*)realloc(ps-a, sizeof(Datatype) * newcapacity);if (tmp NULL){perror(realloc fail);exit(-1);}ps-a tmp;ps-capacity newcapacity;}ps-a[ps-top] x;ps-top;
}
void StackPop(Stack* ps)
{assert(ps);assert(ps-top 0);ps-top--;
}
int Stacksize(Stack* ps)
{assert(ps);return ps-top;
}
Datatype TopData(Stack* ps)
{assert(ps);assert(ps-top 0);return ps-a[ps-top - 1];
}
bool IsEmpty(Stack* ps)
{assert(ps);return (ps-top 0);
}typedef struct {Stack pushst;Stack popst;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* obj(MyQueue*)malloc(sizeof(MyQueue));InItStack(obj-pushst);InItStack(obj-popst);return obj;
}void myQueuePush(MyQueue* obj, int x) {StackPush(obj-pushst,x);
}int myQueuePeek(MyQueue* obj) {if(IsEmpty(obj-popst)){while(!IsEmpty(obj-pushst)){StackPush(obj-popst,TopData(obj-pushst));StackPop(obj-pushst);}}return TopData(obj-popst);
}int myQueuePop(MyQueue* obj) {int frontmyQueuePeek(obj);StackPop(obj-popst);return front;
}bool myQueueEmpty(MyQueue* obj) {return (IsEmpty(obj-pushst)IsEmpty(obj-popst));
}void myQueueFree(MyQueue* obj) {DestoryStack(obj-popst);DestoryStack(obj-pushst);free(obj);
}总结 使用栈模拟实现队列让我们在实践中深入思考了数据结构的本质和应用为我们的编程思维和算法设计能力提供了挑战和提升。希望本期内容对你有些许帮助最后感谢阅读
