1、循环队列的定义
顺序队列在使用过程中容易出现虚假的满状态， 为了解决这个问题，就产生了一个较巧妙的方法，将顺序队列臆造为一个环状的空间，称之为循环队列。循环队列中指针和队列元素之间的关系不变，我们只需要利用模运算就可以很容易实现指针的循环移动。但是循环队列中存在一个问题，在循环队列中只凭头指针front等于尾指针rear无法判别队列空间是“空”还是“满”，可有两种处理方法：其一是另设一个标志位以区别队列是“空”还是“满”；其二是少用一个元素空间，约定以“队列头指针在队列尾指针的下一位置(指环状的下一位置)上”作为队列呈“满”状态的标志。此处使用方法二来解决这个问题。
2、循环队列的结构
typedef struct CircularQueue{ int* a;//存放数据数组 int front;//头结点 int back;//尾结点后一个，有效数据个数 int k;//元素个数 } CircularQueue;
3、循环队列的实现
3.1、初始化队列
开辟k+1个空间，k个存放数据，将头尾结点初始化为0，即数组的第一个位置。
代码实现
//队列初始化 CircularQueue* InitQueue(int k) { CircularQueue* obj=(CircularQueue*)malloc(sizeof(CircularQueue));//为队列分配空间 obj->a=(int*)malloc(sizeof(int)*(k+1)); obj->front=obj->back=0;//初始队列为空，头尾指针都指向0的位置 obj->k=k; return obj; }
测试
3.2、判断是否为空
根据结构定义，头结点跟尾结点相等时则队列为空。为真则为空，为假则不为空。
代码实现
bool QueueEmpty(CircularQueue* obj) { return obj->front==obj->back;//头尾结点相等时则为空 }
测试
3.3、判断是否为满
根据循环队列结构的定义，尾结点后一个是头结点则队列为满。为真则为满，不为真则不满。
代码实现
bool QueueFull(CircularQueue* obj) { return (obj->back+1)%(obj->k+1)==obj->front;//尾结点的下一个等于头结点则为满 }
测试
3.4、入队
根据队列的结构定义，back为尾结点的后一个，当队列空间没有满时，插入数据时则在back位置插入。
代码实现
bool EnQueue(CircularQueue* obj, int value) { //满了返回false if(QueueFull(obj)) { return false; } obj->a[obj->back]=value;//插入有效数据 obj->back++; obj->back%=(obj->k+1);//进入循环，不能超过最大个数 return true; }
测试
3.5、出队
根据队列的定义，只能队头出数据，在循环队列里面通过头尾结点来访问数据，将front++即可删除头结点数据。
代码实现
bool DeQueue(CircularQueue* obj) { //如果为空返回false if(QueueEmpty(obj)) { return false; } obj->front++;//出队则头结点往前走 obj->front%=(obj->k+1); return true; }
测试
3.6、返回队头元素
在保证队列不是空的情况下，队头元素为front下标的元素，为空则返回-1
代码实现
int QueueFront(CircularQueue* obj) { //为空返回-1 if(QueueEmpty(obj)) return -1; return obj->a[obj->front]; }
测试
3.7、返回队尾元素
在保证队列不是空的情况下，队头元素为back前一个下标的元素，为空则返回-1
代码实现
int QueueRear(CircularQueue* obj) { //为空返回-1 if(QueueEmpty(obj)) return -1; //有一种特殊情况 不是back-1 //1. //return obj->a[(obj->back-1+obj->k+1)%(obj->k+1)]; return obj->a[(obj->back+obj->k)%(obj->k+1)]; //2. // if(obj->back==0) // { // return obj->a[obj->k]; // } // else // { // return obj->a[obj->back-1]; // } }
测试
3.8、销毁队列
数组是通过队列的指针访问，且数组和队列都是内存是连续的，可以直接释放内存，所以先释放数组，在释放队列
void QueueFree(CircularQueue* obj) { free(obj->a);//释放数组 free(obj);//释放队列 }
4、代码汇总
#include<stdio.h> #include<stdlib.h> #include<stdbool.h> typedef int QDataType; //结构定义 typedef struct CircularQueue{ QDataType* a;//存放数据数组 int front;//头结点 int back;//尾结点后一个，有效数据个数 int k;//元素个数 } CircularQueue; //初始化 CircularQueue* InitQueue(int k) { CircularQueue* obj=(CircularQueue*)malloc(sizeof(CircularQueue));//为队列分配空间 obj->a=(int*)malloc(sizeof(int)*(k+1)); obj->front=obj->back=0;//初始队列为空，头尾指针都指向0的位置 obj->k=k; return obj; } //判断是否为空 bool QueueEmpty(CircularQueue* obj) { return obj->front==obj->back;//头尾结点相等时则为空 } //判断是否为满 bool QueueFull(CircularQueue* obj) { return (obj->back+1)%(obj->k+1)==obj->front;//尾结点的下一个等于头结点则为满 } //入队 bool EnQueue(CircularQueue* obj, int value) { //满了返回false if(QueueFull(obj)) { return false; } obj->a[obj->back]=value;//插入有效数据 obj->back++; obj->back%=(obj->k+1);//进入循环，不能超过最大个数 return true; } //出队 bool DeQueue(CircularQueue* obj) { //如果为空返回false if(QueueEmpty(obj)) { return false; } obj->front++;//出队则头结点往前走 obj->front%=(obj->k+1); return true; } //获取队头元素 int QueueFront(CircularQueue* obj) { //为空返回-1 if(QueueEmpty(obj)) return -1; return obj->a[obj->front]; } //获取队尾元素 int QueueRear(CircularQueue* obj) { //为空返回-1 if(QueueEmpty(obj)) return -1; //有一种特殊情况 不是back-1 //1. //return obj->a[(obj->back-1+obj->k+1)%(obj->k+1)]; return obj->a[(obj->back+obj->k)%(obj->k+1)]; //2. // if(obj->back==0) // { // return obj->a[obj->k]; // } // else // { // return obj->a[obj->back-1]; // } } //销毁 void QueueFree(CircularQueue* obj) { free(obj->a); free(obj); }
循环队列OJ链接
总结
本篇博客就结束啦，谢谢大家的观看，如果公主少年们有好的建议可以留言喔，谢谢大家啦！
