💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤
📃个人主页 :阿然成长日记 👈点击可跳转
📆 个人专栏: 🔹数据结构与算法🔹C语言进阶
🚩 不能则学,不知则问,耻于问人,决无长进
🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍
文章目录
- 📑前言
- 🍁一、循环队列的结构
- 💭 二、循环队列的操作
- 1.定义循环队列
- 2.创建循环队列
- 3.判断满
- 4.判断空
- 5.入队
- 6.出队
- 7.返回队列头元素
- 8.返回队列尾元素
- 9. 释放
📑前言
在上一篇博客当中我们使用了单链表的形式来模拟队列,你会发现,当执行入队列操作时,我们动态开辟了许多的节点,在元素出队列时,我们进行大量头删,释放内存等操作。实际上浪费了许多的空间与时间。
顺序队列在使用过程中容易出现虚假的满状态, 为了解决这个问题,就产生了一个较巧妙的方法,将顺序队列臆造为一个环状的空间,称之为循环队列。循环队列中指针和队列元素之间的关系不变,我们只需要利用模运算就可以很容易实现指针的循环移动。但是循环队列中存在一个问题,在循环队列中只凭头指针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)
{//如果为空返回-1if (MCQueueIsEmpty(obj))return -1;return obj->a[obj->front];
}
8.返回队列尾元素
//返回队列尾元素
int ReturnRear(MCQueue* obj)
{//如果为空返回-1if (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);
}