数据结构——循环队列
目录
循环队列的基本知识
循环队列的实现
定义
各个接口的实现
循环队列的基本知识
循环队列的定义
循环队列（Circular Queue）是一种使用固定大小的数组实现的队列，它将数组的首尾相连，形成环形，以充分利用空间并实现高效的入队（enqueue）和出队（dequeue）操作。
基本特点
- 固定大小：循环队列通常有一个固定的大小，这意味着它能够存储的元素数量是有限的。
- 循环利用空间：当队尾指针到达数组的末尾时，下一个元素会循环到数组的开头位置。
- 高效操作：循环队列可以避免在数组末尾重新分配空间，从而提高入队和出队操作的效率。
基本操作
- 入队（Enqueue）：在队尾添加一个元素。如果添加后队尾指针到达数组末尾，则循环回数组的开始位置。
- 出队（Dequeue）：移除队首的元素。如果移除后队首指针到达数组末尾，则循环回数组的开始位置。
- 查看队首元素（Peek/Front）：返回队首元素的值，但不移除它。
- 检查是否为空（IsEmpty）：如果队首和队尾指针相同，且队列未满，则队列为空。
- 检查是否已满（IsFull）：如果队尾指针在移动一位后将与队首指针相遇，或者队列的元素数量等于数组的大小，则队列为满。
适用场景
- 当数据元素数量相对固定时，循环队列可以高效地利用内存空间。
- 在需要频繁入队和出队操作的场景中，循环队列可以减少内存分配和回收的开销。
循环队列的实现
定义
循环队列的实现需要一个定长数组arr，一个头指针head，一个尾指针rear，还有用于记录数据个数的变量k。
typedef struct
{int* arr;int head;int rear;int k;} MyCircularQueue;各个接口的实现
创造k个数据的循环队列
MyCircularQueue* myCircularQueueCreate(int k)
{MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj->arr = (int*)malloc(sizeof(int)*(k+1));obj->head = obj->rear = 0;obj->k = k;return obj;
}这里为什么数据个数是k个，但开了k+1个空间？
首先，head指向队列的第一个元素，rear指向队列最后一个元素的下一个位置。
当rear == head的时候，队列可能是空，也可能是满；当队列满的时候，rear指向的应该是最后一个元素的下一个位置，也就是head（循环队列）；当队列为空时，rear == head（rear和head可能不等于0）
所以判断队列为空和队列为满的条件是冲突的，所以特意开多一个空间，这样的话这个循环数组的任意时刻都有一个位置不存放元素，这两个判断条件也就不冲突了。
销毁循环队列
释放动态开辟的数组，把head、rear、k值0即可。
void myCircularQueueFree(MyCircularQueue* obj)
{free(obj->arr);obj->head = obj->rear = obj->k = 0;
}判断循环队列是否为空
判断rear和head是否相等就可以。
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{return obj->head == obj->rear;
}判断循环队列是否为满
其实在创建数组的时候多开的那个空间就是专门为了rear准备的，这里队列为满时rear就不会和head指向同一位置，而是指向多开出来的那个空间。
理想情况下，rear + 1 == head就说明队列为满。
而如果rear刚好是数组的最后下标，rear+1就会越界，所以需要模上capacity（k + 1）。
bool myCircularQueueIsFull(MyCircularQueue* obj)
{return (obj->rear + 1) % (obj->k + 1) == obj->head;
}插入元素到队尾（入队列）
如果插入成功，返回true。
注意先判断队列是否为满，如果满，返回false。
还需注意rear是否会越界的问题
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{if(myCircularQueueIsFull(obj)){return false;}obj->arr[obj->tail++] = value;//记得让rear模上一个周期（k+1），以防越界obj->rear %= (obj->k + 1);return true;
}删除队头元素（出队列）
删除成功就返回true。
注意判断队列为空和head的越界问题即可。
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{if(myCircularQueueIsEmpty(obj)){return false;}obj->head++;//防止head越界obj->head %= (obj->k + 1);return true;
}获取队头元素
注意队列为空，为空就返回-1。
int myCircularQueueFront(MyCircularQueue* obj)
{if(myCircularQueueIsEmpty(obj)){return -1;}return obj->arr[obj->head];
}获取队尾元素
还是注意如果队列为空，为空就返回-1。
int myCircularQueueRear(MyCircularQueue* obj)
{if(myCircularQueueIsEmpty(obj)){return -1;}return obj->arr[(obj->rear + obj->k) % (obj->k + 1)];
}这里不能直接return obj->arr[rear - 1]，因为rear有可能是0，还是得对rear进行特殊处理。
(rear + k + 1 - 1)% (k + 1)就可以处理上面这种特殊情况。
拜拜，下期再见😏
摸鱼ing😴✨🎞
