AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

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

2023-04-24 113
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 比如如果栈里有5个数据，而要根据队列的特性，出队列肯定出的是队头数据，也就是1，而在栈里，怎么才能将数据1删除掉呢？

💯💯💯


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


c69669d21df244c787cce5637d52a15b.png93b6b88196fc441280b30d36273d8606.gif


⏰1.用栈实现队列


1242205cafe34a9b8b373ff21ec6087f.png


思路：


一个栈专门用来插入数据

一个栈专门用来出数据


f27ceea8dbc44010adb1d71c461f3949.png


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


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


e7eb3840b3bd47969abf924838dea3ed.png


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


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


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


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


2e3b99b150854596a5bd50dfb2abc416.png


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


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


aa2eac21128e4786907d8d4473e8febb.png


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


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


🕕"销毁队列"


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


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


844af129ad1146f2a05f5048d354aff7.png


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


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);
*/
文章标签：
C语言
关键词：
数据结构栈
数据结构队列
数据结构栈队列
数据结构用栈队列
小陶来咯
目录
相关文章
ephemerals__
|
22天前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
109 9
那年春天
|
13天前
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
21 1
德国都芳最好
|
16天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构，在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈，可以有效地解决许多与数据存储和操作相关的问题。
德国都芳最好
60 21
html的七十二变
|
19天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境，每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用，每当调用一个函数，就会在栈中添加一个新的执行上下文。
html的七十二变
28 2
dufadayang
|
21天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息？
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息，操作系统能够实现用户模式和内核模式之间的无缝切换，为用户程序提供稳定、可靠的系统服务。
dufadayang
47 4
肾透侧视攻城狮
|
25天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总（10）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
21 1
星霜旅人
|
1月前
数据结构（栈与列队）
数据结构（栈与列队）
星霜旅人
20 1
白子寰
|
1月前
【数据结构】-- 栈和队列
【数据结构】-- 栈和队列
白子寰
17 0
java冯坚持
|
1月前
|
算法 程序员 索引
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈，并展示了如何利用栈和中缀表达式实现一个综合计算器。
java冯坚持
33 1
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
禁默
|
1月前
初步认识栈和队列
初步认识栈和队列
禁默
61 10