4.设计循环队列
描述：
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 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 的范围内；
请不要使用内置的队列库。
4.1思路：
在本题中，循环队列的大小是固定的，可重复利用之前的空间。接下来，就开始分析结构。
结构分析：
题目给定循环队列的大小为 k ，不论数组和链表，构建的大小为 k ，可行吗？
给定 front 和 rear 为0，front 标识队头，rear 标识队尾的下一个数据的位置，每当 入数据， rear++，向后走。
由于是循环队列，空间可以重复利用，当放置完最后一个数据后，rear需要回到头部。
那么问题来了，如何判空和判满 ？无论队列空或满，front 和 rear 都在一个位置。
1.解决方法一：
结构设计时，多加一个 size ，标识队列数据个数。
size=0为空，size=k就是满
2.解决方法二 ：
创建队列时，额外创建一个空间。
缺陷:单链表取尾不好取
数组：
对于数组，那么我们就开上 k + 1 个空间。
front 和 rear 分别标识队头和队尾。
每当入数据，rear 向后走一步，front 不动；每当出数据，front 向后走一步，rear 不动。当走过下标 k 处后，front 和 rear 的位置需要加以调整。比如，rear 下一步应该走到第一个空间：下标0位置。
队列空 时，front == rear。
队列满 时， rear 的下一个位置是 front 。平常只需要看 rear + 1 是否等于 front 即可。但是 放置的元素在 k 下标处时，此刻的 rear 需要特殊处理，rear 的位置会移动到 0 下标。经公式推导：(rear + 1) % (k + 1) == front 时，队列满，平常状况也不会受到公式影响。
入数据时，在 rear 位置入数据，然后 rear 向后移动，同样的，当入数据时到 k 下标的空间后，rear 需要特殊处理：rear %= k + 1。
出数据时，将 front 向后移动，当出数据到 k 下标的空间后，front 需要特殊处理：front %= k + 1。
取队头数据时，不为空取 front 处元素即可。
取队尾数据时，需要取rear 前一个位置，当队列非空时且 rear 不在 0下标时，直接取前一个；当队列非空且 rear 在 0 位置时，需要推导一下公式，前一个数据的下标为：(rear-1 + k+1) % (k + 1)，两种情况都适用。
typedef struct { int* a;//数组模拟环形队列 int front;队头 int rear;//队尾 int k;//队列可存储的有效数据总数 } MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); //申请一个环形队列 obj->a = (int*)malloc(sizeof(int) * (k + 1));//开K=1层//开辟队列空间 obj->front = obj->rear = 0; //初始时，队头和队尾均为0 obj->k = k;//设置队列可存储的有效数据个数 return obj; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->front == obj->rear; //当front和rear指向同一位置时，队列为空 } bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj->rear + 1) % (obj->k + 1) == obj->front; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if (myCircularQueueIsFull(obj)) //队列已满，不能再插入数据 return false; //插入数据 obj->a[obj->rear++] = value;//放数据 obj->rear %= (obj->k + 1); return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if (myCircularQueueIsEmpty(obj)) //当队列为空时，无法再删除数据 return false; //删除数据 obj->front++; obj->front %= (obj->k + 1); return true; } int myCircularQueueFront(MyCircularQueue* obj) { if (myCircularQueueIsEmpty(obj)) //当队列为空时，无数据可返回 return -1; else //返回队头指向的数据 return obj->a[obj->front]; } int myCircularQueueRear(MyCircularQueue* obj) { if (myCircularQueueIsEmpty(obj)) //当队列为空时，无数据可返回 return -1; else //返回rear指向位置的数据 return obj->a[(obj->rear-1 + obj->k+1) % (obj->k + 1)]; //可读性更强的方法 //int x=obj->rear==0?obj->k:obj->rear-1; //rear=0 返回k的位置 反之返回rear-1 //return obj->a[x]; } void myCircularQueueFree(MyCircularQueue* obj) { free(obj->a);//先释放动态开辟的数组 free(obj);//再释放动态开辟的结构体 }
链表：
其实对于循环队列而言，使用链表来构建是最清晰的。
注意 当构建链表时，构建的是 k + 1 个节点的 单向循环链表
front 和 rear 分别标识 队头 和 队尾。
队列空，front == rear 。
队列满，rear 的下一个节点就是 front 节点，rear->next == front。
入数据时，比数组设计简单很多，就直接让rear 迭代到下一个节点就可以。
出数据时，队列非空时，直接让front 迭代到下一个节点。
取队头元素时，如果非空，直接取 front 节点处的值。
取队尾元素时，如果非空，则从头开始迭代到rear 的前一个节点，取出元素。
需要注意 销毁的时候，由于链表不带头，所以销毁的时候可以从第二个节点开始迭代销毁，然后销毁第一个节点，最后销毁队列本身。这里比较细节，过会可以看一下代码。
typedef struct CQNode { struct CQNode* next; int data; }CQNode; typedef struct { CQNode* front; CQNode* rear; } MyCircularQueue; bool myCircularQueueIsEmpty(MyCircularQueue* obj); bool myCircularQueueIsFull(MyCircularQueue* obj); // 创建节点 CQNode* BuyNode() { CQNode* newnode = (CQNode*)malloc(sizeof(CQNode)); newnode->next = NULL; return newnode; } MyCircularQueue* myCircularQueueCreate(int k) { // 构建长度 k + 1 的单向循环链表 // 多开一个空间，防止边界问题 CQNode* head = NULL, *tail = NULL; int len = k + 1; while (len--) { CQNode* newnode = BuyNode(); if (tail == NULL) { head = tail = newnode; } else { tail->next = newnode; tail = newnode; } tail->next = head; } MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); cq->front = cq->rear = head; return cq; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if (myCircularQueueIsFull(obj)) return false; // 直接插入在rear位置，rear后移 obj->rear->data = value; obj->rear = obj->rear->next; return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if (myCircularQueueIsEmpty(obj)) return false; obj->front = obj->front->next; return true; } int myCircularQueueFront(MyCircularQueue* obj) { if (myCircularQueueIsEmpty(obj)) return -1; return obj->front->data; } int myCircularQueueRear(MyCircularQueue* obj) { if (myCircularQueueIsEmpty(obj)) return -1; // 取rear前一个元素 CQNode* cur = obj->front; while (cur->next != obj->rear) { cur = cur->next; } return cur->data; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->front == obj->rear; } bool myCircularQueueIsFull(MyCircularQueue* obj) { return obj->rear->next == obj->front; } void myCircularQueueFree(MyCircularQueue* obj) { // 销毁需要逐个销毁 CQNode* cur = obj->front->next; // 从第二个节点开始，防止找不到头 while (cur != obj->front) { CQNode* next = cur->next; free(cur); cur = next; } // 销毁 free(cur); free(obj); } /** * Your MyCircularQueue struct will be instantiated and called as such: * MyCircularQueue* obj = myCircularQueueCreate(k); * bool param_1 = myCircularQueueEnQueue(obj, value); * bool param_2 = myCircularQueueDeQueue(obj); * int param_3 = myCircularQueueFront(obj); * int param_4 = myCircularQueueRear(obj); * bool param_5 = myCircularQueueIsEmpty(obj); * bool param_6 = myCircularQueueIsFull(obj); * myCircularQueueFree(obj); */
5.总结：
今天我们分析并完成栈和队列相关OJ题，通过分析明白了原理，愿这篇博客能帮助大家理解这些OJ题，因为栈和队列相关OJ题是还是有一些难度和细节需要注意。希望我的文章和讲解能对大家的学习提供一些帮助。之后会继续更新二叉树的相关知识点。
当然，本文仍有许多不足之处，欢迎各位小伙伴们随时私信交流、批评指正！我们下期见~
