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

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

2023-04-24 214
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 比如如果栈里有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语言
关键词：
数据结构队列
数据结构栈队列
数据结构栈
数据结构用栈队列
小陶来咯
目录
相关文章
大数据文摘
|
8月前
|
前端开发 Java
java实现队列数据结构代码详解
本文详细解析了Java中队列数据结构的实现，包括队列的基本概念、应用场景及代码实现。队列是一种遵循“先进先出”原则的线性结构，支持在队尾插入和队头删除操作。文章介绍了顺序队列与链式队列，并重点分析了循环队列的实现方式以解决溢出问题。通过具体代码示例（如`enqueue`入队和`dequeue`出队），展示了队列的操作逻辑，帮助读者深入理解其工作机制。
大数据文摘
280 1
hahaha无
|
6月前
|
编译器 C语言 C++
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因，涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问，修改了变量`i`的值，导致`for`循环条件始终为真，形成死循环。原因是VS2022栈区从低地址到高地址分配内存，`arr`数组与`i`相邻，`arr[15]`恰好覆盖`i`的地址。而在VS2019中，栈区先分配高地址再分配低地址，因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致，需避免数组越界以确保代码健壮性。
hahaha无
140 0
栈区的非法访问导致的死循环(x64)
游客beejssedmb2sq
|
6月前
232.用栈实现队列，225. 用队列实现栈
在232题中，通过两个栈（`stIn`和`stOut`）模拟队列的先入先出（FIFO）行为。`push`操作将元素压入`stIn`，`pop`和`peek`操作则通过将`stIn`的元素转移到`stOut`来实现队列的顺序访问。 225题则是利用单个队列（`que`）模拟栈的后入先出（LIFO）特性。通过多次调整队列头部元素的位置，确保弹出顺序符合栈的要求。`top`操作直接返回队列尾部元素，`empty`判断队列是否为空。 两题均仅使用基础数据结构操作，展示了栈与队列之间的转换逻辑。
游客beejssedmb2sq
168 0
RossyYan
|
11月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算（头歌实践教学平台习题）【合集】
本关任务：编写一个程序实现顺序栈的基本运算。开始你的任务吧，祝你成功！​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念：初始化栈是为栈的使用做准备，包括分配内存空间（如果是动态分配）和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈，通常需要定义一个数组来存储栈元素，并设置一个变量来记录栈顶位置；对于链式栈，需要定义节点结构，包含数据域和指针域，同时初始化栈顶指针。 示例（顺序栈）： 以下是一个简单的顺序栈初始化示例，假设用C语言实现，栈中存储
RossyYan
556 77
蓝易云
|
10月前
|
算法 调度 C++
STL——栈和队列和优先队列
通过以上对栈、队列和优先队列的详细解释和示例，希望能帮助读者更好地理解和应用这些重要的数据结构。
蓝易云
256 11
羑悻的小杀马特
|
10月前
|
DataX
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法：用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下： 1. **用两个队列实现栈**： - 插入元素时，选择非空队列进行插入。 - 移除栈顶元素时，将非空队列中的元素依次转移到另一个队列，直到只剩下一个元素，然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**： - 插入元素时，选择非空栈进行插入。 - 移除队首元素时，将非空栈中的元素依次转移到另一个栈，再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
羑悻的小杀马特
187 14
ephemerals__
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
1056 9
那年春天
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
307 59
RossyYan
|
11月前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算（头歌实践教学平台习题）【合集】
【数据结构——栈与队列】环形队列的基本运算（头歌实践教学平台习题）【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务：编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧，祝你成功！(4)出队一个元素a。(4)出队一个元素x。
RossyYan
461 13
【C++数据结构——栈与队列】环形队列的基本运算（头歌实践教学平台习题）【合集】
RossyYan
|
11月前
|
存储 C语言 C++
【C++数据结构——栈与队列】链栈的基本运算（头歌实践教学平台习题）【合集】
本关任务：编写一个程序实现链栈的基本运算。开始你的任务吧，祝你成功！​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念：初始化栈是为栈的使用做准备，包括分配内存空间（如果是动态分配）和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈，通常需要定义一个数组来存储栈元素，并设置一个变量来记录栈顶位置；对于链式栈，需要定义节点结构，包含数据域和指针域，同时初始化栈顶指针。 示例（顺序栈）： 以下是一个简单的顺序栈初始化示例，假设用C语言实现，栈中存储整数，最大
RossyYan
249 9

热门文章

最新文章

  • 1
    （Python基础）新时代语言！一起学习Python吧！（一）：认识Python、Py解释器作用；编写第一个Python程序；Python中的基本数据结构
  • 2
    （Pandas）Python做数据处理必选框架之一！（一）：介绍Pandas中的两个数据结构；刨析Series：如何访问数据；数据去重、取众数、总和、标准差、方差、平均值等；判断缺失值、获取索引...
  • 3
    数据结构与算法（六）：图结构
  • 4
    包含min函数的栈和两个栈实现一个队列
  • 5
    数据结构与算法——字符串
  • 6
    《大话数据结构》 查找 以及一个简单的哈希表例子
  • 7
    栈的压入、弹出序列
  • 8
    数据结构之树
  • 9
    Redis部分数据结构方法小结
  • 10
    队列的数组实现_JAVA描述《数据结构与算法分析》
  • 1
    （Pandas）Python做数据处理必选框架之一！（一）：介绍Pandas中的两个数据结构；刨析Series：如何访问数据；数据去重、取众数、总和、标准差、方差、平均值等；判断缺失值、获取索引...
    454
  • 2
    （Python基础）新时代语言！一起学习Python吧！（一）：认识Python、Py解释器作用；编写第一个Python程序；Python中的基本数据结构
    442
  • 3
    Redis数据结构：别小看这5把“瑞士军刀”，用好了性能飙升！
    401
  • 4
    软考中级软件设计师专项-数据结构与算法上篇
    525
  • 5
    【Redis】常用数据结构之List篇：从常用命令到典型使用场景
    482
  • 6
    Redis基础命令与数据结构概览
    125
  • 7
    Redis各类数据结构详细介绍及其在Go语言Gin框架下实践应用
    309
  • 8
    【Redis】 常用数据结构之String篇：从SET/GET到INCR的超全教程
    367
  • 9
    【📕分布式锁通关指南 12】源码剖析redisson如何利用Redis数据结构实现Semaphore和CountDownLatch
    328
  • 10
    Redis核心数据结构与分布式锁实现详解
    359

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    安全设备篇——WAF