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

【LeetCode数据结构】设计循环队列

java 2025/9/5 11:39:37

🔥个人主页：胡萝卜3.0

🎬作者简介：C++研发方向学习者

📖个人专栏：  《C语言》、《数据结构》 、《C++干货分享》、LeetCode&牛客代码强化刷题

⭐️人生格言：不试试怎么知道自己行不行

目录

一、循环队列

二、环形队列的结构

三、实现循环队列

3.1 设计循环队列

3.1.1 题目描述

3.1.2 循环队列结构

3.1.2 循环队列的创建

3.1.3 判断队列是否为空

3.1.4 判断队列是否满

3.1.5 入数据

3.1.6 出数据

3.1.7 从队首获取元素

3.1.8 获取队尾元素

3.1.9 销毁

3.2 完整代码

一、循环队列

什么是循环队列？

一个循环队列需满足一下条件：
1、队头删数据，队尾入数据

2、给定固定的空间，使用过程中不可以扩容

3、环形队列满了，不能继续插入数据（即插入数据失败）

举个例子：

比如说一家餐厅只有6个桌子，一次性只能招待6桌客人，如果某一天6桌全坐满了，现在又有来了一桌，如果这桌客人还想继续用餐，只能等其中的一桌客人离开，才能用餐。

ok，总结一下

假设现在有6个空间，只能放6个数据，如果想继续插数据，只能删除数据；只有有空的空间，才能够插入数据，空或者没满可以插入数据

二、环形队列的结构

在队列的学习中，我们使用数组来实现队列，那环形队列还是用数组来实现的吗？

环形队列可以使用数组来实现，也可以使用循环链表来实现。那我们该选哪一个呢？

使用数组，初始化和结构相对简单！！！

三、实现循环队列

当rear越界时，我们需要将rear返回0开始，rear=rear%k，此时rear==front

我们发现，队列为空和队列满了的条件竟然是一样的，那我们该如何区分环形队列是空还是满呢？要求在环形队列中不额外增加计数器成员来保存队列中有效数据个数。

ok，我们接着看：

通过上图，我们就知道队列满时的条件为：（rear+1）%（k+1）== front

既然我们已经知道了队列满时的条件，那这里有个问题：队列已经满了，那么我们该如何继续插入数据呢？

3.1 设计循环队列

622. 设计循环队列 - 力扣（LeetCode）

3.1.1 题目描述

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

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

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

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

我们需要自己写出上图中的所有代码！！！

3.1.2 循环队列结构

通过上面的分析，我们知道循环队列使用数组来实现的，并且有两个指针，一个front为头，一个rear为尾，那这些成员足够了吗？

通过对题目给出的代码来看，我们还应该设置一个成员用来记录数据容量k

代码

//队列结构
typedef struct {int* arr;//存储数据的数组int front;//指向头int rear;//指向尾int capacity;//数据容量大小
} MyCircularQueue;
3.1.2 循环队列的创建

需要我们自己向空间申请一个队列结构，并返回地址。

代码

//申请队列结构空间
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* pq=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));pq->arr=(int*)malloc(sizeof(int)*(k+1));pq->front=0;pq->rear=0;pq->capacity=k;return pq;
}

现在我们已经有了一个循环队列，那我们是不是就可以直接往这里面进行插入和删除数据的操作？

当然不可以，在进行插入之前，我们首先要判断队列是否满，如果满，我们不能进行插入的操作；如果队列为空，我们不能进行删除数据的操作。

3.1.3 判断队列是否为空

我们发现当队列为空时，front==rear！！！

如果相等，返回true；不相等，返回false

3.1.4 判断队列是否满

我们发现，队列满时，（rear+1）%（k+1）==front！！！

3.1.5 入数据

如果队列没有满，我们在rear处入数据，入一个数据，rear++。

那有没有可能rear越界了呢？

ok，我们可以写出代码

//入队
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//判断队列是否满了if(myCircularQueueIsFull(obj)){return false;}obj->arr[obj->rear++]=value;//防止rear出界obj->rear%=(obj->capacity+1);return true;
}
3.1.6 出数据

如果队列不为空，直接front++就可以了。

那front会不会出界呢？如果会出界，那么该怎么办？

代码

//出队
bool myCircularQueueDeQueue(MyCircularQueue* obj) {//判断队列是否为空if(myCircularQueueIsEmpty(obj)){return false;}++obj->front;//front也会出界obj->front%=(obj->capacity+1);return true;
}
3.1.7 从队首获取元素

当队列不为空时，才能从队首获取元素；如果队列为空，不能从队首获取元素。

代码

//从队首获取元素
int myCircularQueueFront(MyCircularQueue* obj) {//判断队列是否为空if(myCircularQueueIsEmpty(obj)){return -1;}return obj->arr[obj->front];
}
3.1.8 获取队尾元素

代码

//获取队尾元素
int myCircularQueueRear(MyCircularQueue* obj) {//判断队列是否为空if(myCircularQueueIsEmpty(obj)){return -1;}//找rear位置的前一个位置int prev=obj->rear-1;if(obj->rear==0){prev=obj->capacity;}return obj->arr[prev];
}
3.1.9 销毁

销毁的操作就是看哪些空间是我们自己主动向操作系统申请的，自己主动申请的需要销毁！！！

代码

//销毁
void myCircularQueueFree(MyCircularQueue* obj) {if(obj->arr){free(obj->arr);}free(obj);obj=NULL;
}
3.2 完整代码
//队列结构
typedef struct {int* arr;//存储数据的数组int front;//指向头int rear;//指向尾int capacity;//数据容量大小
} MyCircularQueue;
//申请队列结构空间
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* pq=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));pq->arr=(int*)malloc(sizeof(int)*(k+1));pq->front=0;pq->rear=0;pq->capacity=k;return pq;
}
//检查循环队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front==obj->rear;
}
//检查循环队列是否已满
bool myCircularQueueIsFull(MyCircularQueue* obj) {return obj->front==(obj->rear+1)%(obj->capacity+1);
}
//入队
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//判断队列是否满了if(myCircularQueueIsFull(obj)){return false;}obj->arr[obj->rear++]=value;//防止rear出界obj->rear%=(obj->capacity+1);return true;
}
//出队
bool myCircularQueueDeQueue(MyCircularQueue* obj) {//判断队列是否为空if(myCircularQueueIsEmpty(obj)){return false;}++obj->front;//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;}//找rear位置的前一个位置int prev=obj->rear-1;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;
}

运行一下

ok，这样我们就实现了一个循环队列了！！！

http://www.xdnf.cn/news/20085.html

相关文章：

  • Java 并发编程解析：死锁成因、可重入锁与解决方案
  • 人工智能机器学习——逻辑回归
  • go 初始化组件最佳实践
  • ai生成ppt工具有哪些？10款主流AI生成PPT工具盘点
  • 中州养老:角色管理的角色分页查询
  • 渗透测试与网络安全审计的关系
  • （论文速读）Navigation World Models: 让机器人像人类一样想象和规划导航路径
  • MySQL主从复制之进阶延时同步、GTID复制、半同步复制完整实验流程
  • aippt自动生成工具有哪些？一文看懂，总有一款适合你！
  • Java数据结构——栈（Stack）和队列（Queue）
  • Qt---状态机框架QState
  • 【Sharding-JDBC】​Spring/Spring Boot 集成 Sharding-JDBC，分表策略与 API、YAML 配置实践​
  • 达梦数据库-共享内存池
  • 3.3.3 钢结构工程施工
  • Kubernetes知识点（三）
  • 探究Linux系统的SSL/TLS证书机制
  • 河南萌新联赛2025第（七）场：郑州轻工业大学
  • 直接让前端请求代理到自己的本地服务器，告别CV报文到自己的API工具，解放双手
  • android View详解—自定义ViewGroup,流式布局
  • 亚洲数字能源独角兽的 “安全密码”：Parasoft为星星充电筑牢软件防线
  • MongoDB 高可用部署：Replica Set 搭建与故障转移测试
  • SpringCloud微服务基于nacos注册中心的服务发现模式及OpenFeign的使用
  • Redis在商城开发中起到什么作用？
  • 漏洞修复 Nginx TLSSSL 弱密码套件
  • 2025国赛C题保姆级教程思路分析 NIPT 的时点选择与胎儿的异常判定
  • 【完整源码+数据集+部署教程】陶瓷物品实例分割系统源码和数据集：改进yolo11-LVMB
  • 第22节：性能监控与内存管理——构建高性能3D应用
  • 3ds Max流体模拟终极指南：打造逼真液体效果，从瀑布到杯中溢出的饮料！
  • 240. 搜索二维矩阵 II
  • 2025年含金量高的经济学专业证书工科！【纯干货分享】