1. 循环队列
1.1 概念及结构
循环队列是一种特殊类型的队列数据结构，也被称为”唤醒缓冲器“。它在数组的基础上实现了循环利用空间的功能。在循环队列中，队尾和队头之间形成了一个循环，当队尾指针“追上”队头指针时，队列不再继续增长，而是继续利用之前出队的空间。
循环队列通常由两个指针来辅助构建：
- 队尾指针(rear)：指向队尾元素的下一个位置，也就是即将插入新元素的位置。
- 队头指针(front)：指向队头元素的位置。
入队和出队：
- 入队操作会将元素插入到队尾指针所指向的位置，并将队尾指针后移。当队列满时，入队操作会失败。
- 出队操作会**删除队头元素，并将队头指针后移。**当队列为空时，出队操作会失败。
队空和队满的条件：
- 当队列为空时，
front指针和rear指针同时指向下标为0的位置，因此循环队列为空的条件为front == rear - 需要清楚，由于循环队列需要预留一个空间来区分队列为空和队列满的状态，队列满的条件为
rear + 1 == head
为什么需要预留一个空间？
假设我们不预留空间，要对下面的队列插入元素‘7’
那么插入后，front（head）和rear（tail）两个指针的关系就变成了这样：
可以看到，front和rear又相等了，这不就和队列为空的条件混到一起了吗。所以说要多预留一个空间用来判断队列满的情况：
1.2 结构的定义
这里我们用数组来模拟实现循环队列
typedef struct { int *data; //动态数组 int front; //队头指针 int rear; //队尾指针 int capacity; //最大容量 } MyCircularQueue
1.3 基本功能实现
1.3.1 初始化(返回一个循环队列指针)
MyCircularQueue* myCircularQueueCreate(int k);
- k为循环队列的最大容量
- 该函数用来返回一个已经初始化好的循环队列指针
MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* CQueue = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); CQueue->data = (int*)malloc(sizeof(int) * (k + 1)); //申请k+1个空间 CQueue->front = 0; CQueue->rear = 0; CQueue->capacity = k; return CQueue; }
1.3.2 判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->front == obj->rear; }
1.3.3 判满
可不要简单的以为循环队列满的条件就是rear + 1 == front，我们要考虑下面两种情况（假设最大容量为4）：
情况一：
情况二：
上面两种情况队列都是满的，显然我们不能简单的用front == rear + 1来判断队列是否已满。
直接下结论：我们可以用表达式**(rearf + 1) % capacity == front**来判断队列是否已满
bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj->rear + 1) % obj->capacit == obj->front; }
1.3.4 入队
入队移动的是队尾指着，同样也要考虑两种情况：
情况一：
情况二：
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if (myCircularQueueIsFull(obj)) //如果已满，插入失败 return false; //如果队尾指针在队列尾部，那么插入过后，队尾指针移到最前面 if (obj->rear == obj->capacity) { obj->data[obj->rear] = value; obj->rear = 0; } //否则队尾指针加以即可 else { obj->data[obj->rear] = value; obj->rear++; } return true; }
1.3.5 出队
出队移动的是队头指针，考虑两种情况：
情况一：
情况二：
bool myCircularQueueDeQueue(MyCircularQueue* obj) { if (myCircularQueueIsEmpty(obj)) //如果队列为空，则出队失败 return false; //如果队头指针位于队列最后一个位置，那么删除后就要回到最前面 if (obj->front == obj->capacity) obj->front = 0; //否则队头指针往后移即可 else obj->front++; return true; }
1.3.5 返回队头元素
由于队头指针指向的就是队头元素，因此直接返回下标位置的元素即可
int myCircularQueueFront(MyCircularQueue* obj) { if (myCircularQueueIsEmpty(obj)) //队列为空，返回-1 return -1; return obj->data[obj->front]; }
1.3.6 返回队尾元素
由于队尾指针指向的是队尾元素的下一个位置，因此要考虑两种情况：
情况一：
情况二：
int myCircularQueueRear(MyCircularQueue* obj) { if (myCircularQueueIsEmpty(obj)) //队列为空，返回-1 return -1; //如果队尾指针在下标为0的位置，就说明队尾元素位于数组最后的位置 if (obj->rear == 0) return obj->data[obj->capacity]; //否则，队尾元素就是队尾指针下标-1的位置 else return obj->data[obj->rear - 1]; }
1.3.7 销毁队列
void myCircularQueueFree(MyCircularQueue* obj) { free(obj->data); //销毁数组 free(obj); //销毁队列 }
1.4 练习
学习完循环队列的相关知识，可以做这一题来加深印象👉设计循环队列
