目录

循环队列的基本知识

循环队列的实现

定义

各个接口的实现

---

循环队列的基本知识

循环队列的定义

循环队列（Circular Queue）是一种使用固定大小的数组实现的队列，它将数组的首尾相连，形成环形，以充分利用空间并实现高效的入队（enqueue）和出队（dequeue）操作。

基本特点

• 固定大小：循环队列通常有一个固定的大小，这意味着它能够存储的元素数量是有限的。
• 循环利用空间：当队尾指针到达数组的末尾时，下一个元素会循环到数组的开头位置。
• 高效操作：循环队列可以避免在数组末尾重新分配空间，从而提高入队和出队操作的效率。

基本操作

1. 入队（Enqueue）：在队尾添加一个元素。如果添加后队尾指针到达数组末尾，则循环回数组的开始位置。
2. 出队（Dequeue）：移除队首的元素。如果移除后队首指针到达数组末尾，则循环回数组的开始位置。
3. 查看队首元素（Peek/Front）：返回队首元素的值，但不移除它。
4. 检查是否为空（IsEmpty）：如果队首和队尾指针相同，且队列未满，则队列为空。
5. 检查是否已满（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😴✨🎞