菜鸟笔记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来判断队列是否已满。
直接下结论：我们可以用表达式(rear + 1) % (capacity + 1) == front来判断队列是否已满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return (obj->rear + 1) % (obj->capacit + 1) == 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 练习
学习完循环队列的相关知识，可以做这一题来加深印象设计循环队列