数据结构刷题训练：用栈实现队列（力扣OJ）-阿里云开发者社区

数据结构刷题训练：用栈实现队列（力扣OJ）

2023-10-16 56

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 数据结构刷题训练：用栈实现队列（力扣OJ）

前言

栈和队列是数据结构中的两个重要概念，它们在算法和程序设计中都有着广泛的应用。本文将带你深入了解如何使用栈来模拟实现队列，让你在解决问题时更加灵活和创新，便于大家更深入的理解栈和队列。

1. 题目：用栈实现队列

题目描述：

题目链接：

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);
}

总结

使用栈模拟实现队列，让我们在实践中深入思考了数据结构的本质和应用，为我们的编程思维和算法设计能力提供了挑战和提升。希望本期内容对你有些许帮助，最后，感谢阅读！