【数据结构】循环队列-阿里云开发者社区

【数据结构】循环队列

2023-10-09 91

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 文章目录📑前言🍁一、循环队列的结构💭 二、循环队列的操作1.定义循环队列2.创建循环队列3.判断满

💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤

📃个人主页：阿然成长日记 👈点击可跳转

📆 个人专栏： 🔹数据结构与算法🔹C语言进阶

🚩 不能则学，不知则问，耻于问人，决无长进

🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍

文章目录

📑前言

在上一篇博客当中我们使用了单链表的形式来模拟队列，你会发现，当执行入队列操作时，我们动态开辟了许多的节点，在元素出队列时，我们进行大量头删，释放内存等操作。实际上浪费了许多的空间与时间。

顺序队列在使用过程中容易出现虚假的满状态，为了解决这个问题，就产生了一个较巧妙的方法，将顺序队列臆造为一个环状的空间，称之为循环队列。循环队列中指针和队列元素之间的关系不变，我们只需要利用模运算就可以很容易实现指针的循环移动。但是循环队列中存在一个问题，在循环队列中只凭头指针front等于尾指针rear无法判别队列空间是“空”还是“满”，可有两种处理方法：其一是另设一个标志位以区别队列是“空”还是“满”；其二是少用一个元素空间，约定以“队列头指针在队列尾指针的下一位置(指环状的下一位置)上”作为队列呈“满”状态的标志。

🍁一、循环队列的结构

循环队列的结构建议使用数组，它能更好的利用空间与位置，便于指针的循环。

假定：此队列最大容纳MaxSize个元素。

为了更好的区分空和满。循环队列最后一个空间第MaxSize+1位置保证为空NULL；

💭 二、循环队列的操作

1.定义循环队列

//定义循环队列 
typedef struct MyCircularQueue
{
  int* a;//数组
  int front;//头
  int rear;//尾
  int MaxSize;//队列最大容量
}MCQueue;

2.创建循环队列

注意：创建数组,MaxSize + 1，多开辟一个空间。

//创建循环队列
MCQueue* MCQueueCreat(int MaxSize)
{
  //创建队列结构
  MCQueue* obj = (MCQueue*)malloc(sizeof(MCQueue));
  //创建数组,MaxSize + 1，多开辟一个空间。
  obj->a = (int*)malloc(sizeof(int) * (MaxSize + 1));
  obj->front = 0;
  obj->rear = 0;
  obj->MaxSize = MaxSize;
  return obj;
}

3.判断满

判断为满：(rear+1) % (MaxSize+1) = front;

此时的MaxSize = 6；rear = 7; front = 0;

（6+1）%7=0 = 0；所以，满。

循环队列最后一个空间保证为空NULL；

//判断满
bool MCQueueIsFull(MCQueue* obj)
{
  return (obj->rear + 1) % (obj->MaxSize + 1) == obj->front;
}

4.判断空

此时满足条件front = rear;

//判断空 
bool MCQueueIsEmpty(MCQueue* obj)
{
  return obj->front == obj->rear;
}

5.入队

rear++在这种情况下将不能实现，需要取余求模

rear = (rear+1)%(MaxSize+1)

如图：

//入队
bool MCQueueIsIn(MCQueue* obj, int value)
{
  //判断是否为满 
  if (MCQueueIsFull(obj))
    return false;
  obj->rear = value;
  obj->rear = (obj->rear + 1) % (obj->MaxSize + 1);
  return true;
}

6.出队

出队列时面临的情况与入队时一样考虑。

//出队
bool MCQueueIsOut(MCQueue* obj)
{
  if (MCQueueIsEmpty(obj))
    return false;
  //删不删 front指向的元素无所谓 ，不影响
  obj->front = (obj->front+1)% (obj->MaxSize + 1);
  return true;
}

7.返回队列头元素

//返回队列头元素 
int ReturnFront(MCQueue* obj)
{
  //如果为空返回-1
  if (MCQueueIsEmpty(obj))
    return -1;
  return obj->a[obj->front];
}

8.返回队列尾元素

//返回队列尾元素
int ReturnRear(MCQueue* obj)
{
  //如果为空返回-1
  if (MCQueueIsEmpty(obj))
    return -1;
  int pos = (obj->rear + obj->MaxSize) % (obj->MaxSize + 1);
  return obj->a[pos];
}

9. 释放

//释放
void Free(MCQueue* obj)
{
  free(obj->a);
  free(obj);
}