【力扣刷题实战】设计循环队列
大家好,我是小卡皮巴拉
文章目录
目录
力扣题目: 设计循环队列
题目描述
示例:
解题思路
问题理解
算法选择
具体思路
解题要点
完整代码(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; }
兄弟们共勉 !!!
码字不易,求个三连
抱拳了兄弟们!