💯💯💯

本篇总结利用栈如何实现队列的相关操作，不难观察，栈和队列是可以相互转化的，需要好好总结它们的特性，构造出一个恰当的结构来实现即可，所以本篇难点不在代码思维，而是对结构的理解。

⏰1.用栈实现队列

思路：

一个栈专门用来插入数据

一个栈专门用来出数据

比如如果栈里有5个数据，而要根据队列的特性，出队列肯定出的是队头数据，也就是1，而在栈里，怎么才能将数据1删除掉呢？

我们的做法是：将栈1的数据全部导入到栈2去。这样由原来的数据就倒过来了，那删除栈顶元素即可。

删除栈顶元素之后，我们分析发现，这时的栈2如果再进行删除，就和队列的删除操作是一致的了，不需要再导回去，如果要再删除队头数据2，直接让栈2删除即可。

所有我们发现经过一次导数据之后，栈2就完全可以当成pop数据的。

那我们如果想插入数据，该怎么插入呢？

根据队列特性，我们只能从队尾插入，也就是元素5的后面插入数据。该怎么插呢？将数据插入栈2里？那可不行，将数据插入栈2中后，原来的顺序就乱了。所以我们将数据插入到栈1去，比如我们要插入数据6，7，8.直接插入到栈1即可。

这样就不会影响栈2出数据的顺序了，并且插入的顺序也不受出数据的影响。

唯一需要注意的是，当栈2的数据都删除空了，这时就需要将栈1的数据再导入到栈2中，这样就能接着删除队列中的数据了。

所以我们可以直接定义两个栈，一个栈用来插入数据，一个栈用来删除数据。

typedef struct 
{  
   ST pushst;
   ST popst;
} MyQueue;

不过在定义之前我们需要写一个栈的数据结构，因为C语言是没有自己的栈的。

typedef int STData;
typedef struct Stack
{
  int* a;
  int top;
  int capicty;
}ST;
void STInit(ST*ps);//初始化栈表
void STDestroy(ST* ps);//销毁栈表
void STpush(ST* ps,STData x);//压栈，在栈顶压入一个元素
void STpop(ST* ps);//出栈，在栈顶弹出一个元素。
STData STTop(ST* ps);//访问栈顶元素
int STSize(ST* ps);
int STEmpty(ST*ps);//
void STInit(ST* ps)//初始化栈表
{
  assert(ps);//判断结构体指针不为NULL；
  //一上来可以给栈表初始化容量
  ps->a = (STData*)malloc(sizeof(STData) * 4);
  if (ps->a == NULL)//判断是否开辟成功
  {
    perror("malloc");
  }
  //初始话容量为4
  ps->capicty = 4;
  ps->top = 0;//top=0 表示的是指向栈顶元素的下一个位置
  //top如果为-1，则表示栈顶元素的位置
}
void STDestroy(ST* ps)//销毁栈表
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->capicty = 0;
  ps->top = 0;
}
void STpush(ST* ps, STData x)//压栈，在栈顶压入一个元素--在压入之前也要考虑是否需要增容
{
    assert(ps);//断言判断
  if (ps->top == ps->capicty)
  {
    //增容
    STData* tmp = (STData*)realloc(ps->a, sizeof(STData) * ps->capicty * 2);
    if (tmp == NULL)
    {
      perror("realloc");
    }
    ps->a = tmp;
    ps->capicty *= 2;
  }
  ps->a[ps->top] = x;//将元素压入栈顶，一开始top是0，当元素进去后，再让top指向该栈顶元素后一个位置
  ps->top++;
}
int STEmpty(ST* ps)
{
  assert(ps);
  return ps->top == 0;
}
void STpop(ST* ps)//出栈，在栈顶弹出一个元素。
{
  assert(ps);
  //删除元素之前要检查栈表是否还有元素可删
  assert(!STEmpty(ps));//当栈表为NULL是断言
  ps->top--;
}
int STSize(ST* ps)//计算栈表长度
{
  assert(ps);
  return ps->top;
  //top的长度就是栈表的长度
}
STData STTop(ST* ps)//访问栈顶元素
{
  assert(ps);
  return ps->a[ps->top - 1];
}

接下来就是获取一个指向 MyQueue队列的指针。

MyQueue* myQueueCreate() //发现没有传入参数并且返回值是指向栈的指针说明里面是用malloc开辟的内存而不是在栈上开辟的
{
    MyQueue *q=(MyQueue*)malloc(sizeof(MyQueue));
    if(q==NULL)
    {
        perror("malloc");
    }
    STInit(&q->pushst);//一开始需要对两个栈进行初始化
    STInit(&q->popst);
    return q;
}

🕐"入队列"

入队列，即插入数据，直接在push栈进行插入即可，不用担心顺序什么的，因为当pop栈没有数据时，就会让push栈导数据过来，这时的顺序就符合队列的要求了

void myQueuePush(MyQueue* obj, int x) 
{
    //只管往pushst里插入即可，不需要管其他
    STpush(&obj->pushst,x);
}

🕑"出队列"

出队列呢就指望pop栈即可，不过在出队列之前，我们需要检查一下pop栈里是否为空，如果为空，就需要将push栈里的数据导过来，如果不为空，那就可以进行删除操作了。

int myQueuePop(MyQueue* obj) 
{
    //需要讨论下，当pop这个栈为空时，需要将push栈中的数据导过来
    if(STEmpty(&obj->popst))
    {
        while(!STEmpty(&obj->pushst))//将push栈中的所有数据都导过去即可
        {
           STpush(&obj->popst,STTop(&obj->pushst));
           STpop(&obj->pushst);//删除push栈里的这个数据
        }
    }
    //走到这里有两种情况，可能push栈里的数据导光了，也可能是pop栈里本来就有数据，不为空
    int top=STTop(&obj->popst);//将这个栈顶元素记录下来，最后需要返回
    STpop(&obj->popst);
    return top;
}

🕒"获取队头元素"

获取队头数据，这个操作与刚刚的删除操作基本一样，只不过该操作不需要将数据删除，直接返回栈顶元素即可，所以大部分代码是一样的。

int myQueuePeek(MyQueue* obj) 
{
   //这里跟pop数据很像,直接return 栈顶元素即可
    //需要讨论下，当pop这个栈为空时，需要将push栈中的数据导过来
    if(STEmpty(&obj->popst))
    {
        while(!STEmpty(&obj->pushst))//将push栈中的所有数据都导过去即可
        {
           STpush(&obj->popst,STTop(&obj->pushst));
           STpop(&obj->pushst);
        }
    }
    //走到这里有两种情况，可能push栈里的数据导光了，也可能是pop栈里本来就有数据，不为空
   return STTop(&obj->popst);
}

🕔"判断队列是否为空"

判断队列是否为空其实很简单，因为该队列是由两个栈构成，当两个栈都为空时，则该队列肯定为空。

bool myQueueEmpty(MyQueue* obj) 
{
   return STEmpty(&obj->pushst)&&STEmpty(&obj->popst);
}

🕕"销毁队列"

销毁队列也简单，要想真正的释放该队列，需要理解该队列的结构是如何构成的。

该队列是由两个栈构成，栈是由数组构成。

释放空间从里到外释放，先释放两个栈空间，再释放队列空间。

void myQueueFree(MyQueue* obj) 
{
    STDestroy(&obj->pushst);
    STDestroy(&obj->popst);
    free(obj);
}

⏰2.完整代码

typedef int STData;
typedef struct Stack
{
  int* a;
  int top;
  int capicty;
}ST;
void STInit(ST*ps);//初始化栈表
void STDestroy(ST* ps);//销毁栈表
void STpush(ST* ps,STData x);//压栈，在栈顶压入一个元素
void STpop(ST* ps);//出栈，在栈顶弹出一个元素。
STData STTop(ST* ps);//访问栈顶元素
int STSize(ST* ps);
int STEmpty(ST*ps);//
void STInit(ST* ps)//初始化栈表
{
  assert(ps);//判断结构体指针不为NULL；
  //一上来可以给栈表初始化容量
  ps->a = (STData*)malloc(sizeof(STData) * 4);
  if (ps->a == NULL)//判断是否开辟成功
  {
    perror("malloc");
  }
  //初始话容量为4
  ps->capicty = 4;
  ps->top = 0;//top=0 表示的是指向栈顶元素的下一个位置
  //top如果为-1，则表示栈顶元素的位置
}
void STDestroy(ST* ps)//销毁栈表
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->capicty = 0;
  ps->top = 0;
}
void STpush(ST* ps, STData x)//压栈，在栈顶压入一个元素--在压入之前也要考虑是否需要增容
{
    assert(ps);//断言判断
  if (ps->top == ps->capicty)
  {
    //增容
    STData* tmp = (STData*)realloc(ps->a, sizeof(STData) * ps->capicty * 2);
    if (tmp == NULL)
    {
      perror("realloc");
    }
    ps->a = tmp;
    ps->capicty *= 2;
  }
  ps->a[ps->top] = x;//将元素压入栈顶，一开始top是0，当元素进去后，再让top指向该栈顶元素后一个位置
  ps->top++;
}
int STEmpty(ST* ps)
{
  assert(ps);
  return ps->top == 0;
}
void STpop(ST* ps)//出栈，在栈顶弹出一个元素。
{
  assert(ps);
  //删除元素之前要检查栈表是否还有元素可删
  assert(!STEmpty(ps));//当栈表为NULL是断言
  ps->top--;
}
int STSize(ST* ps)//计算栈表长度
{
  assert(ps);
  return ps->top;
  //top的长度就是栈表的长度
}
STData STTop(ST* ps)//访问栈顶元素
{
  assert(ps);
  return ps->a[ps->top - 1];
}
typedef struct 
{  
   ST pushst;
   ST popst;
} MyQueue;
MyQueue* myQueueCreate() 
{
    MyQueue *q=(MyQueue*)malloc(sizeof(MyQueue));
    if(q==NULL)
    {
        perror("malloc");
    }
    STInit(&q->pushst);
    STInit(&q->popst);
    return q;
}
void myQueuePush(MyQueue* obj, int x) 
{
    //只管往pushst里插入即可，不需要管
    STpush(&obj->pushst,x);
}
int myQueuePop(MyQueue* obj) 
{
    //需要讨论下，当pop这个栈为空时，需要将push栈中的数据导过来
    if(STEmpty(&obj->popst))
    {
        while(!STEmpty(&obj->pushst))//将push栈中的所有数据都导过去即可
        {
           STpush(&obj->popst,STTop(&obj->pushst));
           STpop(&obj->pushst);
        }
    }
    //走到这里有两种情况，可能push栈里的数据导光了，也可能是pop栈里本来就有数据，不为空
    int top=STTop(&obj->popst);
    STpop(&obj->popst);
    return top;
}
int myQueuePeek(MyQueue* obj) 
{
   //这里跟pop数据很像,直接return 栈顶元素即可
    //需要讨论下，当pop这个栈为空时，需要将push栈中的数据导过来
    if(STEmpty(&obj->popst))
    {
        while(!STEmpty(&obj->pushst))//将push栈中的所有数据都导过去即可
        {
           STpush(&obj->popst,STTop(&obj->pushst));
           STpop(&obj->pushst);
        }
    }
    //走到这里有两种情况，可能push栈里的数据导光了，也可能是pop栈里本来就有数据，不为空
   return STTop(&obj->popst);
}
bool myQueueEmpty(MyQueue* obj) 
{
   return STEmpty(&obj->pushst)&&STEmpty(&obj->popst);
}
void myQueueFree(MyQueue* obj) 
{
    STDestroy(&obj->pushst);
    STDestroy(&obj->popst);
    free(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);
*/

【数据结构】用栈实现队列

本篇总结利用栈如何实现队列的相关操作，不难观察，栈和队列是可以相互转化的，需要好好总结它们的特性，构造出一个恰当的结构来实现即可，所以本篇难点不在代码思维，而是对结构的理解。

⏰1.用栈实现队列

🕐"入队列"

🕑"出队列"

🕒"获取队头元素"

🕔"判断队列是否为空"

🕕"销毁队列"

⏰2.完整代码

热门文章

最新文章

相关课程

相关电子书