AI 助理
备案控制台
开发者社区 云计算 文章 正文

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

2023-04-24 70
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 我们知道队列的特点：先进先出，只能在一端插入，一端删除。

💯💯💯


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


c69669d21df244c787cce5637d52a15b.png93b6b88196fc441280b30d36273d8606.gif


⏰1.用队列实现栈


db884fd6bdb4402696ca5c144439956a.png


做该种题要记住两个关键点：


一个队列用来插入数据。一个队列用来存数据


1.空队列用来导数据

2.非空队列用来插入数据


我们知道队列的特点：先进先出，只能在一端插入，一端删除。


而栈的特点是：先进后出，后进先出。


496cb577de8d4c01a4991e7a12731d6a.png


比如要让两个队列实现栈的功能，就拿出栈来说，如果要应该将栈顶元素5拿走。


但在队列1中，因为只能在队头进行删除，所以只能拿走元素1.


那该怎么办呢？


要想pop掉队列中的元素5，我们得想办法将它搞成队头元素才行，这样才可以删除掉它。而如果队列2是空队列的话，那么我们这样做：将元素5之前的4个元素都放到队列2中，队列1中就只剩下元素5了，那元素5就相当于队头元素，就可以进行pop操作最终将其删除掉了，删除后队列1又变成空队列了。


而队列2就是非空队列。而重复这样的操作就可以实现删除栈顶元素的操作了：首先将非空队列中前n-1个元素导入空队列中，然后再pop掉非空队列中的元素。


38017bffcef64afe92f5bf5c8dfba6a8.png


我们如果想要进行压栈操作，将元素6，7压入栈顶，那该如何插入呢？


9b7a90602b7d47f49b50598851938fc4.png


其实只要在非空队列中尾插元素即可，也就是正常的入队即可


那我们来按照空与非空来区别两个队列，因为两个不同队列有着不同的功能：


非空队列：用来插入数据

空队列：用来导数据，存数据

首先我们需要将队列的数据结构写出来，然后定义两个队列。


//利用单链表来实现队列
typedef int QData;
typedef struct QNode
{
  struct QNode* next;
  int data;
}QNode;
//因为队列的数据结构操作需要找尾，这就需要传多个参数了，很麻烦，所以我们再分装个结构体将多个数据变成一个
typedef struct Queue
{
  QNode* head;
  QNode* tail;
  int size;
}Queue;
void QueueInit(Queue *pq);//初始化队列
void QueueDestroy(Queue *pq);//销毁队列
void QueuePush(Queue*pq ,QData x);//入队，从队尾插入一个数据，尾删
void QueuePop(Queue *pq);//出队，从队头删除数据，头删
bool QueueEmpty(Queue *pq);//判断队列是否为空
int QueueSize(Queue*pq);//获得队列有效数据个数大小
QData QueueFront(Queue*pq);//获取队头数据
QData QueueBack(Queue*pq);//获取队尾数据
void QueueInit(Queue* pq)//初始化队列
{
  assert(pq);
  pq->head = pq->tail = NULL;
  pq->size = 0;
}
void QueueDestroy(Queue* pq)//销毁队列
{
  QNode* cur = pq->head;
  while (cur)
  {
    QNode* next = cur->next;
    free(cur);
    cur = next;
  }
  pq->head = pq->tail = NULL;
  pq->size = 0;
}
void QueuePush(Queue* pq, QData x)//入队，从队尾插入一个数据，尾删
{
  assert(pq);
/*  QNode* cur = pq->head;
  */QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    perror("malloc");
  }
  newnode->data=x;
  newnode->next = NULL;
  if (pq->head == NULL)
  {
    //赋值
    pq->head = pq->tail = newnode;
  }
  else
  {
    pq->tail->next = newnode;
    //更新tail的位置
    pq->tail = newnode;
  }
  pq->size++;
}
void QueuePop(Queue* pq)//出队，从队头删除数据，头删
{
  assert(pq);
  //头删之前需要判断链队列是否为空
  assert(pq->head!=NULL);
  //改变头指针的指向
    QNode* next = pq->head->next;
    free(pq->head);
    pq->head = next;
     //当headtail都指向一起是，把head指向的空间释放，那tail就变成野指针了
  //所以还需要考虑最后一个结点，需要将tail和head一起置空
  if (pq->head==NULL)//只管头删，最后再处理。
  {
    pq->tail=NULL;
  }
  pq->size--;
}
//链表哨兵卫里面可以存放大小吗？
//不能--可能不是int类型--如果我们像求一个链表的大小通常需要遍历链表
bool QueueEmpty(Queue* pq)//判断队列是否为空----主要size的作用
{
  assert(pq);
  return pq->size == 0;
  //return pq->head=pq->tailk=NULL;
}
int QueueSize(Queue* pq)//获得队列有效数据个数大小
{
  assert(pq);
  return pq->size;
}
QData QueueFront(Queue* pq)//获取队头数据
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->head->data;
}
QData QueueBack(Queue* pq)//获取队尾数据
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->tail->data;
}


定义两个队列q1，q2


typedef struct //该重命名方式为匿名结构体，没有名字但有效
{
  Queue q1;
  Queue q2;
} MyStack;


然后要获得指向MyStack的指针


MyStack* myStackCreate() //注意这里最后要返回指向栈的指针，并且空间是可使用的，所以必须动态开辟空间，如果只是由栈上开辟空间，那么函数结束，空间就被销毁，而在堆上申请的空间不会被销毁，所以需要用malloc给这个结构体开辟空间
{
}


🕑"出栈"


Pop就需要导数据了，将非空的数据导入空队列中，这样才可以删除最后一个元素。


但一开始并不知道谁是空的谁是非空，所以我们需要先讨论下


所以步骤就是：


1.先判断哪个队列是非空，哪个队列是空。

2.将非空队列前n-1个元素导入空队列

3.删除非空队列元素


int myStackPop(MyStack* obj) 
{
  Queue* empty = &obj->q1;//假设一开始q1是空队列
  Queue* nonempty = &obj->q2;//假设q2是非空队列
  if (!QueueEmpty(empty))//如果假设错误那q1就是非空队列，q2是空队列
  {
    empty = &obj->q2;
    nonempty = &obj->q1;
  }
  //这样我们就不用管谁是空谁是非空了，empty就是空，nonempty就是非空
  //将非空队列前n-1个元素导入空队列中华
  //【导数据】
  while (QueueSize(nonempty) - 1 > 0)
  {
    QueuePush(empty, QueueFront(nonempty));
           //插入空队列   //获取队头元素
    QueuePop(nonempty);//将数据pop掉
  }
  //走到这时说明非空队列就剩最后一个元素了，即栈顶元素
  //要求返回栈顶元素，所以我们需要保存下来
  int top = QueueFront(nonempty);
  QueuePop(nonempty);//删除最后一个元素
  return top;
}


🕓"压栈"


往非空队列里插入，哪个队列不为空就往哪里插，两个都为空，随便插入一个即可


void myStackPush(MyStack* obj, int x) 
{
  assert(obj);
  if (!QueueEmpty(&obj->q1))//如果q1不为空
  {
    QueuePush(&obj->q1, x);//就将数据插入q1中
  }
  else//如果q1为空，则q2不为空，就往q2中插入数据
  {
    QueuePush(&obj->q2, x);//或者都为空，随便进入一个
  }
}


🕕"获取栈顶数据"


取栈顶数据，其实就是非空队尾数据


但仍然不知道谁是非空谁是空，所以需要讨论下


int myStackTop(MyStack* obj) {
  assert(obj);
  if (!QueueEmpty(&obj->q1))//如果q1不为空
  {
    return QueueBack(&obj->q1);//队尾数据即栈顶数据
  }
  else//如果q1为空，则q2不为空，
  {
    return QueueBack(&obj->q2);//队尾数据即栈顶数据
  }
}


🕖"判断是否为空"


怎么算空呢？当然当两个队列都为空时才是真正的空。


bool myStackEmpty(MyStack* obj) 
{
  assert(obj);
  return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}


🕗"销毁栈"


如何销毁用队列实现的栈呢？


这要求我们需要搞清楚这个栈的结构到底是什么样子：


栈是由两个队列构成，而队列又是由结点和一个size构成。结点又是由一个data数据和一个指针构成。


fb694987533249f491f8cd1fa8f83969.png


我们应该先从里面开始释放，不然先释放外面的里面的空间就找不到了，所以从里到外释放。先释放两个队列，然后再释放栈的空间。


void myStackFree(MyStack* obj) 
{
  assert(obj);
  QueueDestroy(&obj->q1);
  QueueDestroy(&obj->q2);
  free(obj);
  obj = NULL;
}


⏰2.整体代码


typedef int QData;
typedef struct QNode
{
  struct QNode* next;
  int data;
}QNode;
typedef struct Queue
{
  QNode* head;
  QNode* tail;
  int size;
}Queue;
void QueueInit(Queue *pq);//初始化队列
void QueueDestroy(Queue *pq);//销毁队列
void QueuePush(Queue*pq ,QData x);//入队，从队尾插入一个数据，尾删
void QueuePop(Queue *pq);//出队，从队头删除数据，头删
bool QueueEmpty(Queue *pq);//判断队列是否为空
int QueueSize(Queue*pq);//获得队列有效数据个数大小
QData QueueFront(Queue*pq);//获取队头数据
QData QueueBack(Queue*pq);//获取队尾数据
void QueueInit(Queue* pq)//初始化队列
{
  assert(pq);
  pq->head = pq->tail = NULL;
  pq->size = 0;
}
void QueueDestroy(Queue* pq)//销毁队列
{
  QNode* cur = pq->head;
  while (cur)
  {
    QNode* next = cur->next;
    free(cur);
    cur = next;
  }
  pq->head = pq->tail = NULL;
  pq->size = 0;
}
void QueuePush(Queue* pq, QData x)//入队，从队尾插入一个数据，尾删
{
  assert(pq);
/*  QNode* cur = pq->head;
  */QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    perror("malloc");
  }
  newnode->data=x;
  newnode->next = NULL;
  if (pq->head == NULL)
  {
    //赋值
    pq->head = pq->tail = newnode;
  }
  else
  {
    pq->tail->next = newnode;
    //更新tail的位置
    pq->tail = newnode;
  }
  pq->size++;
}
void QueuePop(Queue* pq)//出队，从队头删除数据，头删
{
  assert(pq);
  //头删之前需要判断链队列是否为空
  assert(pq->head!=NULL);
  //改变头指针的指向
    QNode* next = pq->head->next;
    free(pq->head);
    pq->head = next;
     //当headtail都指向一起是，把head指向的空间释放，那tail就变成野指针了
  //所以还需要考虑最后一个结点，需要将tail和head一起置空
  if (pq->head==NULL)//只管头删，最后再处理。
  {
    pq->tail=NULL;
  }
  pq->size--;
}
bool QueueEmpty(Queue* pq)//判断队列是否为空----主要size的作用
{
  assert(pq);
  return pq->size == 0;
  //return pq->head=pq->tailk=NULL;
}
int QueueSize(Queue* pq)//获得队列有效数据个数大小
{
  assert(pq);
  return pq->size;
}
QData QueueFront(Queue* pq)//获取队头数据
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->head->data;
}
QData QueueBack(Queue* pq)//获取队尾数据
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->tail->data;
}
//柔性数组与顺序表的区别
typedef struct {
    Queue q1;
    Queue q2;
} MyStack;//用两个队列实现的栈
//匿名定义结构体
MyStack* myStackCreate()//发现没有传入参数并且返回值是指向栈的指针说明里面是用malloc开辟的内存而不是在栈上开辟的
 {
     MyStack*st=(MyStack*)malloc(sizeof(MyStack));//
     if(st==NULL)
     {
         perror("malloc");
     }
    //需要对两个队列进行初始化
    QueueInit(&st->q1);
    QueueInit(&st->q2);
     return st;
}
void myStackPush(MyStack* obj, int x)//压栈怎么压呢？直接在不为空的队列后面尾插即可
{
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
}
int myStackPop(MyStack* obj)//出栈怎么出呢？ 需要将不为空的队列前面的数据导入为空的队列中，再将最后一个数据删除掉，在删除之前保存删除的数据。//但不知道谁是空谁不是空所以需要判断一下
{
   Queue *empty=&obj->q1;//假设q1是空队列
   Queue *nonempty=&obj->q2;//假设q2是非空队列
   if(!QueueEmpty(&obj->q1))
   {
       empty=&obj->q2;
       nonempty=&obj->q1;
   }
   //现在不需要知道谁是空谁是非空了
   //将非空队列数据导入空队列中
   while(QueueSize(nonempty)-1>0)
   {
       QueuePush(empty,QueueFront(nonempty));
       QueuePop(nonempty);
   }
   //删除最后一个数据之前需要保存
   int top=QueueFront(nonempty);
   QueuePop(nonempty);
   return top;
}
int myStackTop(MyStack* obj)//返回栈顶元素--对应队列就是让非空队列中最后一个元素
{
      //首先需要判断谁是非空
    //判断完后让返回非空最后一个元素
    if(!QueueEmpty(&obj->q1))
    {
       return QueueBack(&obj->q1);
    }
    else
    {
       return QueueBack(&obj->q2);
    }
}
bool myStackEmpty(MyStack* obj) //判断是否为空，只要两个队列都为空就为空
{
  return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}
void myStackFree(MyStack* obj) 
{
   //从里到外释放，不能从外到里释放
   QueueDestroy(&obj->q1);
   QueueDestroy(&obj->q2);
   free(obj);
}
/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 * int param_2 = myStackPop(obj);
 * int param_3 = myStackTop(obj);
 * bool param_4 = myStackEmpty(obj);
 * myStackFree(obj);
*/


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

热门文章

最新文章

  • 1
    数据结构~在页面上渲染树型结构
  • 2
    我花了一夜用数据结构给女朋友写个H5走迷宫游戏
  • 3
    数据结构学习笔记【持续更新】
  • 4
    基于OHCI的USB主机 —— OHCI（自定义数据结构）
  • 5
    算法导论第十四章 数据结构的扩张
  • 6
    学数据结构，只需要基本的编程体验
  • 7
    【数据结构与算法】一篇文章彻底搞懂二分查找（思路图解+代码优化）两种实现方式，递归与非递归
  • 8
    数据结构（2）：栈的原理和实现
  • 9
    基于OHCI的USB主机 —— UFI数据结构2
  • 10
    R语言学习笔记（一）数据结构
  • 1
    数据结构~缓存淘汰算法--LRU算法（Java的俩种实现方式，万字解析
    93
  • 2
    数据结构（五）----特殊矩阵的压缩存储
    229
  • 3
    数据结构（九）---并查集
    64
  • 4
    【数据结构与算法 11，高并发系统基础篇
    41
  • 5
    JavaScript 中实现常见数据结构：栈、队列与树
    73
  • 6
    数据结构链表详解(不仅顺序表可以，我链表也可以)
    39
  • 7
    顺序表的实现（迈入数据结构的大门）（2）
    36
  • 8
    顺序表的实现（迈入数据结构的大门）（1）
    32
  • 9
    每个程序员都必须掌握的8种数据结构，retrofit教程
    33
  • 10
    scala中常见数据结构的用法
    42

    • 相关课程

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

    • 相关电子书

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