当前位置：首页 > news >正文

Leetcode622.设计循环队列

news 2025/7/4 9:30:06

本专栏内容为：leetcode刷题专栏，记录了leetcode热门题目以及重难点题目的详细记录

💓博主csdn个人主页：小小unicorn
⏩专栏分类：Leetcode
🚚代码仓库：小小unicorn的代码仓库🚚
🌹🌹🌹关注我带你学习编程知识

循环队列

题目描述
解题思路：
代码解决：
结果与总结：

题目描述

题目来源：Leetcode622.设计循环队列

设计你的循环队列实现。循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

1.MyCircularQueue(k): 构造器，设置队列长度为 k 。
2.Front: 从队首获取元素。如果队列为空，返回 -1 。
3.Rear: 获取队尾元素。如果队列为空，返回 -1 。
4.enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
5.deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
6.isEmpty(): 检查循环队列是否为空。
7.isFull(): 检查循环队列是否已满。

解题思路：

在环形队列中，队列为空时，队头队尾指向同一个位置。当队列不为空时，队头指向插入的第一个数据，队尾指向最后一个数据的下一个位置。当tail+1等于front时，说明环形队列已满。
注意：环形队列的队尾不能像常规队列中队尾一样指向最后一个数据，如果这样的话，我们将不能区别环形队列的状态是空还是满，因为此时队头和队尾都指向同一个位置。这就意味着，我们必须留出一个空间，这个空间不能存放数据，这样我们才能很好的区别环形队列的状态是空还是满。
在这里插入图片描述
我们如果用一个数组来实现这个环形队列的话，上面这三种状态就对应于以下三种状态：

可以看出，此时这个数组和环形完全扯不上关系，这其实很简单，我们只需注意判断两个地方：
1.当指针指向整个数组的后方的时候，让该指针重新指向数组的第一个元素。
2.当指针指向整个数组的前方的时候，让该指针直接指向数组最后一个有效元素的后面。
这样就使得该数组在逻辑上是“环形”的了。
在这里插入图片描述

代码解决：

typedef struct 
{int* a;//数组模拟环形队列int k;//队列可存储的有效数据总数int front;//队头int tail;//队尾的后一个位置
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) 
{MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//申请一个环形队列obj->a = (int*)malloc(sizeof(int)*(k+1));//开辟队列空间//初始时，队头和队尾均为0obj->front = 0;obj->tail = 0;obj->k = k;//设置队列可存储的有效数据个数return obj;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{return obj->front == obj->tail;//当front和tail指向同一位置时，队列为空
}bool myCircularQueueIsFull(MyCircularQueue* obj) 
{int tailNext = obj->tail+1;if(tailNext == obj->k+1)//当指针指到队列末尾时，指针返回队列开头，使队列循环{tailNext = 0;}return tailNext == obj->front;//当tail+1指向的位置与front相同时，队列满
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
{if(myCircularQueueIsFull(obj))//队列已满，不能再插入数据{return false;}else//插入数据{obj->a[obj->tail] = value;obj->tail++;if(obj->tail == obj->k+1)//使队列循环obj->tail = 0;return true;}
}bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{if(myCircularQueueIsEmpty(obj))//当队列为空时，无法再删除数据{return false;}else//删除数据{obj->front++;if(obj->front == obj->k+1)//使队列循环obj->front = 0;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//返回tail-1指向位置的数据{int tailPrev = obj->tail-1;if(tailPrev == -1)//使队列循环tailPrev = obj->k;return obj->a[tailPrev];}
}void myCircularQueueFree(MyCircularQueue* obj) 
{free(obj->a);//先释放动态开辟的数组free(obj);//再释放动态开辟的结构体
}