循环队列
原则：遵循 先进先出
队首 ：Tail / Rear
队尾：Head / Front
由于队列是循环的，为了区分空队列和满队列（尾指针等于首指针）以及下标越界的情况，循环队列会空最后一个元素的位置用于区分，判断满队列的条件为
(Manager->Rear + 1) % Manager->Size == Manager->Front
1.循环队列结构
/****************************************************
循环队列的结构
****************************************************/
typedef struct CircularQueue
{
DataType_t * Addr; //记录循环队列首地址
unsigned int Size; //记录循环队列的容量
int Rear; //循环队列队尾下标
int Front; //循环队列队首下标
}CirQueue_t;
2.创建循环队列并完成初始化
/*****************************************************************************
* 函数名称: CirQueue_Create
* 函数功能： 创建循环队列并完成初始化
* 函数参数：
* @a size 循环队列的大小
* 返回结果： 指向循环队列的指针
* 注意事项： NONE
* 函数作者： [email protected]
* 创建日期： 2024/4/29
* 修改历史： 2024/4
* 函数版本： 1.0
*
*****************************************************************************/
CirQueue_t * CirQueue_Create(unsigned int size)
{
//1.利用calloc为循环队列的管理结构体申请一块堆内存
CirQueue_t *Manager = (CirQueue_t *)calloc(1,sizeof(CirQueue_t));
//对内存申请做错误判断
if(NULL == Manager)
{
perror("calloc memory for manager is failed");
exit(-1); //程序异常终止
}
//2.利用calloc为所有元素申请堆内存
Manager->Addr = (DataType_t *)calloc(size,sizeof(DataType_t));
//对内存申请做错误判断
if (NULL == Manager->Addr)
{
perror("calloc memory for element is failed");
free(Manager);
exit(-1); //程序异常终止
}
//3.对管理循环队列的结构体进行初始化（循环队列容量 + 队尾下标+队首下标）
Manager->Size = size; //对循环队列中的容量进行初始化
Manager->Rear = 0; //队尾下标初值为0
Manager->Front = 0; //队首下标初值为0
return Manager;
}
3.判断循环队列是否为 空/满
/*****************************************************************************
* 函数名称: CirQueue_IsEmpty
* 函数功能： 判断队列是否为空
* 函数参数：
* @a Manager 操作的队列
* 返回结果： 布尔型
* 注意事项： NONE
* 函数作者： [email protected]
* 创建日期： 2024/4/29
* 修改历史： 2024/4
* 函数版本： 1.0
*
*****************************************************************************/
bool CirQueue_IsEmpty(CirQueue_t *Manager)
{
//当队尾下标等于队首下表时，队列为空
return (Manager->Front == Manager->Rear) ? true : false;
}
/*****************************************************************************
* 函数名称: CirQueue_IsFull
* 函数功能： 判断队列是否为满
* 函数参数：
* @a Manager 操作的队列
* 返回结果： 布尔型
* 注意事项： NONE
* 函数作者： [email protected]
* 创建日期： 2024/4/29
* 修改历史： 2024/4
* 函数版本： 1.0
*****************************************************************************/
//判断循环队列是否已满
bool CirQueue_IsFull(CirQueue_t *Manager)
{
//当队尾下标 +1 然后对 容量求余 = 队首下标时，队列为满
return ( (Manager->Rear + 1) % Manager->Size == Manager->Front ) ? true : false;
}
4.入队
/*****************************************************************************
* 函数名称: CirQueue_Enqueue
* 函数功能： 将元素加入队列中
* 函数参数：
* @Manager 操作的队列
* @Data 入队的元素
* 返回结果： 布尔型
* 注意事项： NONE
* 函数作者： [email protected]
* 创建日期： 2024/4/29
* 修改历史： 2024/4
* 函数版本： 1.0
*
*****************************************************************************/
bool CirQueue_Enqueue(CirQueue_t *Manager, DataType_t Data)
{
//1.判断循环队列是否已满
if ( CirQueue_IsFull(Manager) )
{
printf("CirQueue is Full!\n");
return false;
}
//2.如果循环队列有空闲空间，则把新元素添加到循环队列尾部
Manager->Addr[Manager->Rear] = Data;
//移动下标，防止队尾下标越界
Manager->Rear = (Manager->Rear+1) % Manager->Size;
return true;
}
5.出队
/*****************************************************************************
* 函数名称: CirQueue_Dequeue
* 函数功能： 将元素出队
* 函数参数：
* @Manager 操作的队列
* 返回结果： 出队的元素的值
* 注意事项： NONE
* 函数作者： [email protected]
* 创建日期： 2024/4/29
* 修改历史： 2024/4
* 函数版本： 1.0
*
*****************************************************************************/
DataType_t CirQueue_Dequeue(CirQueue_t *Manager)
{
DataType_t temp =0;
//1.判断循环队列是否为空
if ( CirQueue_IsEmpty(Manager) )
{
printf("CirQueue is Empty!\n");
return false;
}
//2.把元素从队首出队，并备份到变量temp
temp = Manager->Addr[Manager->Front];
//防止队首下标越界
Manager->Front = (Manager->Front+1) % Manager->Size;
return temp;
}