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

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

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

💯💯💯


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


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);
*/


关键词：
数据结构队列栈
数据结构栈
数据结构队列
小陶来咯
目录
相关文章
倔强的石头_
|
2天前
|
算法 C语言
【数据结构与算法 经典例题】使用栈实现队列（图文详解）
【数据结构与算法 经典例题】使用栈实现队列（图文详解）
倔强的石头_
10 0
反季雪
|
2天前
|
存储 算法
【数据结构和算法】--队列的特殊结构-循环队列
【数据结构和算法】--队列的特殊结构-循环队列
反季雪
6 0
lge101058
|
2天前
|
存储 测试技术
【数据结构】操作受限的线性表，队列的具体实现
【数据结构】操作受限的线性表，队列的具体实现
lge101058
12 4
倔强的石头_
|
2天前
|
算法 C语言
【数据结构与算法 经典例题】使用队列实现栈（图文详解）
【数据结构与算法 经典例题】使用队列实现栈（图文详解）
倔强的石头_
9 1
枫叶丹4
|
2天前
【海贼王的数据航海】栈和队列
【海贼王的数据航海】栈和队列
枫叶丹4
4 0
倔强的石头_
|
2天前
|
算法 程序员 数据处理
【数据结构与算法】使用单链表实现队列：原理、步骤与应用
【数据结构与算法】使用单链表实现队列：原理、步骤与应用
倔强的石头_
8 0
倔强的石头_
|
2天前
|
存储 算法 编译器
【数据结构与算法】使用数组实现栈：原理、步骤与应用
【数据结构与算法】使用数组实现栈：原理、步骤与应用
倔强的石头_
8 0
反季雪
|
2天前
|
算法
【数据结构和算法】---栈和队列的互相实现
【数据结构和算法】---栈和队列的互相实现
反季雪
5 0
反季雪
|
2天前
|
算法
【数据结构和算法】--队列
【数据结构和算法】--队列
反季雪
4 0
反季雪
|
2天前
|
缓存 算法
【数据结构和算法】--- 栈
【数据结构和算法】--- 栈
反季雪
4 0

热门文章

最新文章

  • 1
    云原生数据仓库产品使用合集之在ADB中，如何将源数据的多表（数据结构一致）汇总到一张表
  • 2
    InfluxDB数据模型与数据结构设计详解
  • 3
    可视化数据结构——让你的树跃然纸上
  • 4
    【C 言专栏】C 语言中的数据结构应用
  • 5
    栈数据结构详解
  • 6
    22个常用数据结构实现与原理分析
  • 7
    数据结构面试常见问题
  • 8
    数据结构第二课 -----线性表之顺序表
  • 9
    【数据结构】哈夫曼树编译码器【课程设计】
  • 10
    数据结构——lesson12排序之归并排序
  • 1
    Redis数据类型详解：选择合适的数据结构优化你的应用
    78
  • 2
    【算法与数据结构】二叉树（前中后）序遍历2
    24
  • 3
    【MongoDB】MongoDB 如何处理复杂的数据结构？
    39
  • 4
    【数据结构】排序算法
    35
  • 5
    【数据结构】C语言实现链队列(附完整运行代码)
    54
  • 6
    深入理解InnoDB索引数据结构和算法
    75
  • 7
    【数据结构】深入浅出理解链表中二级指针的应用
    43
  • 8
    【数据结构】线性表的链式存储结构
    29
  • 9
    【数据结构】C语言实现顺序表万字详解(附完整运行代码)
    52
  • 10
    【Redis技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现（字典）（二）
    74

    • 相关课程

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

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    部署LAMP环境（Alibaba Cloud Linux 3）