【力扣刷题实战】设计循环队列
大家好，我是小卡皮巴拉
文章目录
目录
力扣题目： 设计循环队列
题目描述
示例：
解题思路
问题理解
算法选择
具体思路
解题要点
完整代码（C语言）
兄弟们共勉 ！！！
每篇前言
博客主页：小卡皮巴拉
咱的口号：🌹小比特，大梦想🌹
作者请求：由于博主水平有限，难免会有错误和不准之处，我也非常渴望知道这些错误，恳请大佬们批评斧正。
力扣题目： 设计循环队列
原题链接：设计循环队列
题目描述
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 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
解题思路
问题理解
设计一个循环队列的数据结构，该数据结构遵循FIFO（先进先出）原则，且队尾连接到队首形成一个闭环。这个队列能够利用之前使用过的空间来存储新元素，从而避免了传统队列在满时无法插入新元素的问题，即使队列前端有空闲空间。
算法选择
数据结构选择：
选择数组作为底层数据结构来实现循环队列，因为数组在内存中是连续存储的，这有利于快速访问队列中的元素。同时，数组可以方便地通过模运算（取余操作）来实现循环效果。操作实现：
- 使用两个指针（或索引）分别表示队首（
front）和队尾（rear）的位置。- 使用一个计数器（
size）来跟踪队列中当前元素的数量。- 使用一个固定长度的数组来存储队列中的元素。
具体思路
构造器
MyCircularQueue(k)：
初始化一个长度为
k + 1的数组queue（为了区分队列为空和队列满的情况，我们实际上不使用数组的第一个位置，即索引为0的位置）。初始化
front和rear指针为 -1，表示队列为空。这里front指向队列的首个有效元素，rear指向队列最后一个有效元素的下一个位置（为了保持front和rear之间始终有size个有效元素，即使队列为空）。初始化
capacity为k，表示队列的最大容量。初始化
size为 0，表示队列中当前元素的数量。
Front方法：
检查
isEmpty()是否返回真，如果是，则直接返回 -1。否则，返回
queue[front]，即队列首个有效元素的值。
Rear方法：
检查
isEmpty()是否返回真，如果是，则直接返回 -1。否则，由于
rear指向的是队列最后一个有效元素的下一个位置，我们需要返回queue[(rear - 1 + capacity) % capacity]，这里使用模运算来确保索引在有效范围内内循环。
enQueue(value)方法：
检查
isFull()是否返回真，如果是，则插入失败，返回假。否则，更新
rear为(rear + 1) % capacity，将新元素value插入到queue[rear]中，并增加size计数器。返回真。
deQueue()方法：
检查
isEmpty()是否返回真，如果是，则删除失败，返回假。否则，更新
front为(front + 1) % capacity，并减少size计数器。如果更新后front == rear且size == 0，则将front和rear都设为 -1，表示队列为空。返回真。
isEmpty方法：
检查
size是否为 0，如果是，则返回真；否则返回假。
isFull方法：
检查
size是否等于capacity（注意这里不是k，而是capacity，但在这个特定实现中，由于我们预留了一个位置，所以capacity实际上等于k + 1的值减去预留的一个位置，但逻辑上我们仍将其视为capacity），如果是，则返回真；否则返回假。
解题要点
循环特性：
使用模运算
% capacity来实现数组的循环访问。
front和rear指针的更新需要考虑循环效果。队列操作：
插入（
enQueue）、删除（deQueue）、获取队首（Front）、获取队尾（Rear）、检查是否为空（isEmpty）和检查是否已满（isFull）等操作均通过操作queue数组和更新front、rear、size等变量来实现。边界条件：
处理队列为空（
front == -1或size == 0）和队列已满（size == k）时的特殊情况。确保在插入和删除元素时，
front和rear指针以及size变量的正确更新。性能要求：
所有操作都应在常数时间内完成（O(1) 时间复杂度），这得益于对数组的直接访问和指针的算术运算。
完整代码（C语言）
//思路：留1个空位，申请capacity+1个空间 //循环队列为空：front == rear //循环队列满了：(rear+1)%(capacity+1) == fronttypedef struct {int* arr;int front;//队头int rear; //队尾int capacity;//循环队列的空间大小 } MyCircularQueue;//循环队列的初始化 MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* pq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//申请k+1个空间pq->arr = (int*)malloc(sizeof(int)*(k+1));pq->front = pq->rear = 0;pq->capacity = k;return pq; } //判断队列是否为空 bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front == obj->rear; } //判断队列是否装满 bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->rear+1)%(obj->capacity+1) == obj->front; } //向循环队列中插入一个元素 bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj)){return false;}//没有满obj->arr[obj->rear++] = value;obj->rear %= obj->capacity+1;//obj->rear = obj->rear%(obj->capacity+1);return true; } //删除循环队列中的元素 bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return false;}//队列不为空++obj->front;obj->front %= obj->capacity+1;return true; } //取队头 int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}return obj->arr[obj->front]; } //取队尾 int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}int prev = obj->rear-1;//若是指向循环队列尾的指针指向第一个数组元素，则它的真实队尾为数组的最后一个元素，即capacity对应的下标if(obj->rear == 0){prev = obj->capacity;}return obj->arr[prev]; } //销毁循环队列 void myCircularQueueFree(MyCircularQueue* obj) {if(obj->arr)//数组不为空free(obj->arr);free(obj);obj == NULL; }
兄弟们共勉 ！！！
码字不易，求个三连
抱拳了兄弟们！
