目录
前言
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;
那么在malloc,obj时就已经将两个栈的空间开辟好了。这样也更简单便捷。
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 front=myQueuePeek(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 front=myQueuePeek(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);
}
文章来源:https://www.toymoban.com/news/detail-643520.html
总结
使用栈模拟实现队列,让我们在实践中深入思考了数据结构的本质和应用,为我们的编程思维和算法设计能力提供了挑战和提升。希望本期内容对你有些许帮助,最后,感谢阅读!文章来源地址https://www.toymoban.com/news/detail-643520.html
到了这里,关于数据结构刷题训练:用栈实现队列(力扣OJ)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!