LeetCode——622设计循环队列
. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。
https://leetcode.cn/problems/design-circular-queue/
1.题目
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 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 的范围内；
- 请不要使用内置的队列库。
2.解析
我们设计循环队列的关键是要有效地利用数组空间，并且能够处理队列满和队列空的情况。下面是一种使用数组实现循环队列的解法，其中back=k+1的含义是为了区分队列满和队列空的情况。
- 首先，我们需要定义一个固定大小的数组a来存储队列元素，以及两个指针front和back来标记队列的头部和尾部。
- 初始化时，将front和back都设置为0，表示队列为空。
- 判断队列是否为空（isEmpty）：
- 判断front是否等于back，如果相等，则表示队列为空，返回true;否则，返回false。
- 判断队列是否已满（isFull）：
- 判断（back+1）%k是否等于front，如果相等，则表示队列已满，返回true;否则，返回false。
- 入队操作（enqueue）：
- 首先，判断队列是否已满，即（back+1）%k是否等于front。如果相等，则表示队列已满，无法继续入队。
- 如果队列未满，则将元素放入back指向的位置，并将back指针向后移动一位，即back=（back+1）%k。
- 出队操作（dequeue）：
- 首先，判断队列是否为空，即front是否等于back。如果相等，则表示队列为空，无法进行出队操作。
- 如果队列不为空，则将front指向的元素出队，并将front指针向后移动一位，即front=（front+1）%k。
- 获取队头元素（getFront）：
- 首先，判断队列是否为空，即front是否等于back。如果相等，则表示队列为空，无法获取队头元素。
- 如果队列不为空，则返回front指向的元素。
3.代码总结
1.构造器函数，用于创建一个指定长度的循环队列。
首先，通过malloc函数动态分配了一个MyCircularQueue结构体的内存空间，并将其地址赋给指针变量obj。
然后，通过malloc函数再次动态分配了一个整型数组的内存空间，并将其地址赋给指针变量obj->a。这个数组的长度为k+1，多分配了一个空间用于判断队列是否满的条件。
接着，将队列的头指针front和尾指针back都初始化为0。
最后，将k的值赋给队列的长度k。
最终，返回指向创建的循环队列的指针obj。
MyCircularQueue* myCircularQueueCreate(int k)//构造器，设置队列长度为 k
{
MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->a=(int*)malloc(sizeof(int)*(k+1));
obj->front=0;
obj->back=0;
obj->k=k;
return obj;
}2. 检查循环队列是否为空
函数的返回值是一个bool类型的值，表示循环队列是否为空。
如果循环队列为空，则返回true，否则返回false。
函数的实现是通过比较循环队列的front和back的值来判断循环队列是否为空。
如果它们相等，说明队列中没有元素，即队列为空，返回true；否则返回false。
bool myCircularQueueIsEmpty(MyCircularQueue* obj)//检查循环队列是否为空。
{
return obj->front==obj->back;
}3. 检查循环队列是否已满
函数的返回值是一个bool类型的值，表示循环队列是否已满。如果循环队列已满，则返回true，否则返回false。
函数的实现是通过计算(back+1)%(k+1)与front的值是否相等来判断循环队列是否已满。
如果它们相等，说明队列已满，返回true；否则返回false。
这里使用了取模运算来实现循环队列的特性。由于循环队列的尾部和头部相连，所以需要将back的下一个位置计算为(back+1)%(k+1)，其中k为队列长度。如果这个值与front相等，说明队列已满。
bool myCircularQueueIsFull(MyCircularQueue* obj)//检查循环队列是否已满。
{
return (obj->back+1)%(obj->k+1)==obj->front;
}4. 向循环队列插入一个元素
函数的返回值是一个bool类型的值，表示插入操作是否成功。
如果插入成功，则返回true；否则返回false。
函数的实现首先通过调用myCircularQueueIsFull函数来检查循环队列是否已满。
如果队列已满，则表示无法插入新元素，直接返回false。
如果队列未满，则将value值插入到队列的obj->back位置，并且将obj->back的值加1。为了保证obj->back在[0, k]的范围内，需要使用取模运算进行处理，即obj->back%=(obj->k+1)。这样可以使back的值在超出队列长度时重新回到队列起始位置。
最后返回true表示插入成功。
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)//向循环队列插入一个元素。如果成功插入则返回真。
{
if(myCircularQueueIsFull(obj))
{
return false;
}
obj->a[obj->back]=value;
obj->back++;
obj->back%=(obj->k+1);//将 obj->back 除以 (obj->k+1) 的余数，然后将结果赋值给 obj->back。
return true;
}5. 循环队列中删除一个元素
函数的返回值是一个bool类型的值，表示删除操作是否成功。
如果删除成功，则返回true；否则返回false。
函数的实现首先通过调用myCircularQueueIsEmpty函数来检查循环队列是否为空。
如果队列为空，则表示无法执行删除操作，直接返回false。
如果队列不为空，就执行删除操作。
即将obj->front的值加1，然后使用取模运算来确保obj->front在[0, k]的范围内。
最后返回true表示删除成功。
bool myCircularQueueDeQueue(MyCircularQueue* obj)//从循环队列中删除一个元素。如果成功删除则返回真。
{
if(myCircularQueueIsEmpty(obj))
{
return false;
}
obj->front++;
obj->front%=(obj->k+1);
return true;
}6.循环队列中获取队首元素
函数的返回值是一个int类型的值，表示队首元素。如果队列为空，则返回-1。
函数的实现首先通过调用myCircularQueueIsEmpty函数来检查循环队列是否为空。如果队列为空，则返回-1。
如果队列不为空，则直接返回obj->a[obj->front]，即队首元素的值。
int myCircularQueueFront(MyCircularQueue* obj)//从队首获取元素。如果队列为空，返回 -1 。
{
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
return obj->a[obj->front];
}7.获取循环队列的队尾元素
- 首先判断队列是否为空，通过调用函数
myCircularQueueIsEmpty(obj)来判断。如果队列为空，则返回-1。 - 如果队列不为空，使用取模运算
(obj->back+obj->k)%(obj->k+1)来计算队尾元素的下标。这里obj->back表示队尾元素的下标，obj->k表示队列的容量减1。这样做是为了实现循环队列的封装。 - 返回队尾元素
obj->a[(obj->back+obj->k)%(obj->k+1)]，即对应下标位置上的元素值。
int myCircularQueueRear(MyCircularQueue* obj)//: 获取队尾元素。如果队列为空，返回 -1 。
{
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
return obj->a[(obj->back+obj->k)%(obj->k+1)];
}8.释放循环队列的内存空间
首先，通过调用free(obj->a)来释放存储队列元素的数组的内存空间。obj->a指向数组的起始地址，free(obj->a)将释放该内存空间。
然后，通过调用free(obj)来释放存储循环队列结构体的内存空间。obj指向循环队列结构体的起始地址，free(obj)将释放该内存空间。
通过这两个free()函数的调用，可以确保循环队列所占用的所有内存空间都被释放，防止内存泄漏。
void myCircularQueueFree(MyCircularQueue* obj)
{
free(obj->a);
free(obj);
}9.总的代码
typedef struct
{
int *a;
int front;
int back;
int k;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k)//构造器，设置队列长度为 k
{
MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->a=(int*)malloc(sizeof(int)*(k+1));
obj->front=0;
obj->back=0;
obj->k=k;
return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj)//检查循环队列是否为空。
{
return obj->front==obj->back;
}
bool myCircularQueueIsFull(MyCircularQueue* obj)//检查循环队列是否已满。
{
return (obj->back+1)%(obj->k+1)==obj->front;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)//向循环队列插入一个元素。如果成功插入则返回真。
{
if(myCircularQueueIsFull(obj))
{
return false;
}
obj->a[obj->back]=value;
obj->back++;
obj->back%=(obj->k+1);//将 obj->back 除以 (obj->k+1) 的余数，然后将结果赋值给 obj->back。
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj)//从循环队列中删除一个元素。如果成功删除则返回真。
{
if(myCircularQueueIsEmpty(obj))
{
return false;
}
obj->front++;
obj->front%=(obj->k+1);
return true;
}
int myCircularQueueFront(MyCircularQueue* obj)//从队首获取元素。如果队列为空，返回 -1 。
{
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
return obj->a[obj->front];
}
int myCircularQueueRear(MyCircularQueue* obj)//: 获取队尾元素。如果队列为空，返回 -1 。
{
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
return obj->a[(obj->back+obj->k)%(obj->k+1)];
}
void myCircularQueueFree(MyCircularQueue* obj)
{
free(obj->a);
free(obj);
}腾讯云开发者
