🚀 作者简介：一名在后端领域学习，并渴望能够学有所成的追梦人。
🐌 个人主页：蜗牛牛啊
🔥 系列专栏：🛹数据结构、🛴C++
📕 学习格言：博观而约取，厚积而薄发
🌹 欢迎进来的小伙伴，如果小伙伴们在学习的过程中，发现有需要纠正的地方，烦请指正，希望能够与诸君一同成长！ 🌹
文章目录
- 循环队列
- 设计循环队列
循环队列
队列又称为”先进先出（FIFO）”线性表：插入操作只能在队尾进行，删除操作只能在队首进行。
而循环队列是队列的一种特殊形式，循环队列（也被称为环形队列）是一种线性数据结构，其操作表现基于先进先出原则，并且队尾被连接在队首之后以形成一个循环。
循环队列固定大小，空间能够重复利用。
循环队列可以用数组或者链表实现，那下面我们来分析一下哪种方式更好：
当我们想使用链表实现时，假设我们想要开辟的队列长度为k = 4；front表示队头指针，rear表示队尾指针：
由上图可知，当rear和front 都指向同一个位置时队列为空。
插入一个数据之后：
rear向后移动，此时我们知道rear指向的位置是最后一个数据的下一个位置。
那当我们一直插入数据，直至队列为满：
但是当队列满的时候，我们发现rear 和 front也指向同一个位置。那当队列为空和队列为满的时候，rear和front都指向同一个位置，我们怎么判断此时队列是满还是空？
通过判断front和rear是否为空可以吗？不行，front和rear刚开始都会指向节点，不会为空。
解决方法：1.增加一个size或者flag解决；2.增加一个空余节点。
我们可以多开一个节点，不是哨兵位节点，和头节点一样，此时：
队列为空时：
队列满时：
满的时候不能再插入数据，现在假设我们删除两个数据：
再插入两个数据：
如果我们不断pop，当rear和front指向同一个位置时，队列就变为空了。
那我们可以用单链表来实现循环队列吗？使用链表最不好解决的一个问题就是取队尾数据，单链表不容易取当前节点的前一个结点数据，我们可以通过增加一个指针rear->prev指向前一个结点。
当我们想使用数组实现时，假设我们想要开辟的队列长度为k = 4；front表示队头的下标，rear表示队尾的下标：
使用数组实现同样也面临着front和rear相等时无法判断队列是空还是满的问题，所以我们也可以通过增加一个size或者多开辟一个空间来解决该问题。
当我们插入一个数据后发现rear指向队尾数据的下一个位置，在链表中存在的找队尾问题，在这里找队尾数据变得简单。
当队列为空时下标front == rear：
当队列满时可以通过公式(rear + 1) % (k + 1) == front来判断队列是否满了：
插入数据在rear++之后可以通过rear % （k + 1）来计算插入数据之后rear的下标：
删除数据可以在front++之后通过front % (k + 1)得出删除数据之后front的下标：
练习：现有一循环队列，其队头指针为front，队尾指针为rear；循环队列长度为N。其队内有效长度为 ？
A (rear – front + N) % N + 1
B (rear – front + N) % N
C (rear – front) % (N + 1)
D (rear – front + N) % (N – 1)
假设队列如下图所示：
队内有效长度为2，两个指针相减得到的是两个指针之间的元素个数(rear – front) = 2；上面的四个选项中代入计算只有B符合要求。
设计循环队列
题目：设计循环队列
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
MyCircularQueue(k): 构造器，设置队列长度为 k 。Front: 从队首获取元素。如果队列为空，返回 -1 。Rear: 获取队尾元素。如果队列为空，返回 -1 。enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。isEmpty(): 检查循环队列是否为空。isFull(): 检查循环队列是否已满。
示例：
MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1); // 返回 true
circularQueue.enQueue(2); // 返回 true
circularQueue.enQueue(3); // 返回 true
circularQueue.enQueue(4); // 返回 false，队列已满
circularQueue.Rear(); // 返回 3
circularQueue.isFull(); // 返回 true
circularQueue.deQueue(); // 返回 true
circularQueue.enQueue(4); // 返回 true
circularQueue.Rear(); // 返回 4
提示：
- 所有的值都在 0 至 1000 的范围内；
- 操作数将在 1 至 1000 的范围内；
- 请不要使用内置的队列库。
思路：
可以使用数组的方式实现循环队列，在结构体中定义一个一级指针
int* arr、队头下标front、队尾下标rear以及要开辟的队列长度k；然后通过开辟空间及上面关于循环队列的知识完成循环队列的设计。
注：下面提供的代码第一个是通过if来计算插入时rear下标和删除时front下标的，第二个是通过公式计算的。
代码1：
typedef struct {
int* arr; //用来指向空间的指针
int front;//队头下标
int rear;//队尾下标
int k;//队列长度
} MyCircularQueue;
构造器，设置队列长度为 k
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* r = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//申请一个结构体指针
int* tmp = (int*)malloc(sizeof(int) * (k + 1));//多开一个空间
if(tmp == NULL)
{
perror("malloc");
exit(0);
}
r->arr = tmp;//给指针赋值
r->front = 0;//设置队头下标
r->rear = 0;//设置队尾下标
r->k = k;//队列长度
return r;
}
//检查循环队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
if(obj->rear == obj->front)//相等时为空
return true;
return false;
}
// 检查循环队列是否已满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
if((obj->rear + 1)%( obj->k + 1) == obj->front)
return true;
return false;
}
//向循环队列插入一个元素。如果成功插入则返回真
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if(myCircularQueueIsFull(obj))//队列满时不能再插入
return false;
obj->arr[obj->rear++] = value;//插入数据
if(obj->rear > obj->k)//计算rear下标
{
obj->rear = 0;
}
return true;
}
//从循环队列中删除一个元素。如果成功删除则返回真
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))//为空时不能删除
return false;
obj->front++;
if(obj->front > obj->k)//计算front下标
{
obj->front = 0;
}
return true;
}
//从队首获取元素。如果队列为空，返回 -1
int myCircularQueueFront(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
return -1;
return obj->arr[obj->front];
}
//获取队尾元素。如果队列为空，返回 -1
int myCircularQueueRear(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
return -1;
int n = obj->rear-1;
if(n < 0)
{
n = obj->k;
}
return obj->arr[n];
}
//释放空间
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->arr);
free(obj);
}
代码2：
typedef struct {
int* arr; //用来指向空间的指针
int front;//队头下标
int rear;//队尾下标
int k;//队列长度
} MyCircularQueue;
//构造器，设置队列长度为 k 。
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));//申请一个结构体指针
obj->arr=(int*)malloc(sizeof(int)*(k+1));//开辟k+1个int空间用来存储数据，要多开辟一个
obj->k=k;//队列长度
obj->front = obj->rear = 0;
return obj;
}
//检查循环队列是否为空。
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
assert(obj);
return obj->front == obj->rear; //相等时为空
}
// 检查循环队列是否已满。
bool myCircularQueueIsFull(MyCircularQueue* obj) {
assert(obj);
return ((obj->rear+1)%(obj->k+1) == obj->front);
}
//向循环队列插入一个元素。如果成功插入则返回真。
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
assert(obj);
if(myCircularQueueIsFull(obj))//队列满时不能再插入
return false;
obj->arr[obj->rear++] = value;//插入数据
obj->rear = obj->rear%(obj->k+1);//计算rear下标
return true;
}
//从循环队列中删除一个元素。如果成功删除则返回真。
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
assert(obj);
if(myCircularQueueIsEmpty(obj))//为空时不能删除
return false;
obj->front++;
obj->front = obj->front % (obj->k+1);//计算front下标
return true;
}
//从队首获取元素。如果队列为空，返回 -1 。
int myCircularQueueFront(MyCircularQueue* obj) {
assert(obj);
if(myCircularQueueIsEmpty(obj))
return -1;
return obj->arr[obj->front];
}
//获取队尾元素。如果队列为空，返回 -1 。
int myCircularQueueRear(MyCircularQueue* obj) {
assert(obj);
if(myCircularQueueIsEmpty(obj))
return -1;
return obj->arr[(obj->rear+obj->k)%(obj->k+1)];
}
//释放空间
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->arr);
free(obj);
}
文章出处登录后可见！
