💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤
📃个人主页 ：阿然成长日记 👈点击可跳转
🚩 不能则学，不知则问，耻于问人，决无长进
🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍
文章目录
📑前言
在上一篇博客当中我们使用了单链表的形式来模拟队列，你会发现，当执行入队列操作时，我们动态开辟了许多的节点，在元素出队列时，我们进行大量头删，释放内存等操作。实际上浪费了许多的空间与时间。
顺序队列在使用过程中容易出现虚假的满状态， 为了解决这个问题，就产生了一个较巧妙的方法，将顺序队列臆造为一个环状的空间，称之为循环队列。循环队列中指针和队列元素之间的关系不变，我们只需要利用模运算就可以很容易实现指针的循环移动。但是循环队列中存在一个问题，在循环队列中只凭头指针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); }
