如何设计循环队列（两种方法）

文章目录

  • 前言
  • 一、方法一:数组法
  • 二、方法二.链表法
  • 总结

前言

前面有提到过队列的知识，这次来说一下怎么设计一个循环队列

一.循环队列（力扣）

. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/design-circular-queue/description/

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

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

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

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

思路:循环队列无论使用数组实现还是链表实现，都要多开一个空间，也就意味着要是存K个数据的循环队列，就要开K+1个空间，不然无法实现判空和判满

方法一:数组法

注意数组法的判空和判满

判空:就是front==tail的时候就是空的，判满:当（tail+1)%(k+1)==front就是满的

1.0初始化

初始化一个数组，有头front，尾tail，数组明a

typedef struct {int* a;int front;int tail;int k;} MyCircularQueue;

1.1创建

MyCircularQueue* myCircularQueueCreate(int k) 
{//开辟一个循环队列的空间MyCircularQueue* q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//开辟一个数组的空间用来实现循环队列，要多开辟一个q->a = (int*)malloc(sizeof(int) * (k + 1));//初始化q->front = q->tail = 0;q->k = k;return q;
}

1.2判空，判满

判空:就是front==tail的时候就是空的，判满:当（tail+1)%(k+1)==front就是满的

//判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front == obj->tail;
}
//判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->tail + 1) % (obj->k + 1) == obj->front;
}

1.3插入

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//如果循环队列是满的就不能插入if (myCircularQueueIsFull(obj))return false;//把末尾的值插入值obj->a[obj->tail] = value;//然后tail的往后走++obj->tail;//防止数组越界，%(k+1)把下标都控制在k之内//把越界的重置obj->tail %= (obj->k + 1);return true;
}

1.4删除

数组的删除不用向链表这些Pop，直接覆盖就可以了

//数组的删除不用向链表这些Pop，直接覆盖就可以了
bool myCircularQueueDeQueue(MyCircularQueue* obj) {//如果是空的就不能删if (myCircularQueueIsEmpty(obj))return false;//头往前走++obj->front;//止数组越界，%(k+1)把下标都控制在k之内obj->front %= (obj->k + 1);return true;
}

1.5拿出最后一个数

int myCircularQueueRear(MyCircularQueue* obj) {//如果是空的就拿不了if (myCircularQueueIsEmpty(obj)){return -1;}//存在特殊情况，当tail为0时，尾才最后，所以不能直接拿出tail之前的数if (obj->tail == 0)return obj->a[obj->k];elsereturn obj->a[obj->tail - 1];
}

1.6拿出头数据和销毁

//直接拿出
int myCircularQueueFront(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return -1;}return obj->a[obj->front];}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}

1.7总代码

注意把判空判满提前引用！！！

typedef struct {int* a;int front;int tail;int k;} MyCircularQueue;
bool myCircularQueueIsFull(MyCircularQueue* obj);
bool myCircularQueueIsEmpty(MyCircularQueue* obj);MyCircularQueue* myCircularQueueCreate(int k) 
{//开辟一个循环队列的空间MyCircularQueue* q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//开辟一个数组的空间用来实现循环队列，要多开辟一个q->a = (int*)malloc(sizeof(int) * (k + 1));//初始化q->front = q->tail = 0;q->k = k;return q;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//如果循环队列是满的就不能插入if (myCircularQueueIsFull(obj))return false;//把末尾的值插入值obj->a[obj->tail] = value;//然后tail的往后走++obj->tail;//防止数组越界，%(k+1)把下标都控制在k之内obj->tail %= (obj->k + 1);return true;
}//数组的删除不用向链表这些Pop，直接覆盖就可以了
bool myCircularQueueDeQueue(MyCircularQueue* obj) {//如果是空的就不能删if (myCircularQueueIsEmpty(obj))return false;//头往前走++obj->front;//止数组越界，%(k+1)把下标都控制在k之内obj->front %= (obj->k + 1);return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return -1;}return obj->a[obj->front];}int myCircularQueueRear(MyCircularQueue* obj) {//如果是空的就拿不了if (myCircularQueueIsEmpty(obj)){return -1;}//存在特殊情况，当tail为0时，尾才最后，所以不能直接拿出tail之前的数if (obj->tail == 0)return obj->a[obj->k];elsereturn obj->a[obj->tail - 1];
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front == obj->tail;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->tail + 1) % (obj->k + 1) == obj->front;
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}

方法二.链表法

2.0初始化

先初始化一个链表，在定义结构

typedef struct listNode {int data;struct Node* next;
}Node;typedef struct {Node* front;Node* tail;int k;
}MyCircularQueue;

2.1创建

这个是最难的部分，就是在创建的时候要创造一个循环链表，注意:这里其实已经开辟了k+1个空间了,不懂的自己画图

MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));cq->front = cq->tail = (Node*)malloc(sizeof(Node));cq->k = k;//创造一个循环链表//这里其实已经开辟了k+1个空间了注意while (k){Node* cur= (Node*)malloc(sizeof(Node));cur->data = 0;cur->next = NULL;cq->tail->next =cur;cq->tail= cq->tail->next;k--;}//开辟好了之后还要把尾和头发一起cq->tail->next =cq->front;cq->tail= cq->front;return cq;
}

2.2判空，判满

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front == obj->tail;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return obj->tail->next == obj->front;
}

2.3插入

//插入
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//先判满if (myCircularQueueIsFull(obj))return false;//直接在尾上插入obj->tail->data = value;obj->tail= obj->tail->next;return true;
}

2.4删除

//删除
bool myCircularQueueDeQueue(MyCircularQueue* obj) {//先判空if (myCircularQueueIsEmpty(obj))return false;//头删obj->front = obj->front->next;return true;
}

2.5去头元素

int myCircularQueueFront(MyCircularQueue* obj)
{if(myCircularQueueIsEmpty(obj))return -1;return obj->front->data;
}

2.6去尾元素

注意尾是前一个元素，所以不可以直接拿出，实在不理解看一下直接的动图

int myCircularQueueRear(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj))return -1;//去找尾Node* cur= obj->front;while (cur->next != obj->tail)cur= cur->next;return cur->data;}

2.7销毁

这个是我自己犯的错误

cur=cur->next,为什么不可以，因为cur等于头节点，cur等于cur->next，再释放cur，相当于把头节点next释放掉了，那我头节点后面的后面怎么去找呢？所以我们是从头节点开始释放的，把头节点用cur记录下来，释放之前让头节点走了，但是cur是头节点的傀儡节点，所以释放cur相当于是释放头节点了。

void myCircularQueueFree(MyCircularQueue* obj) {//和单链表的销毁一样Node* tmp = obj->front;while (obj->k + 1){//cur=cur->next；为什么不可以obj->front = obj->front->next;free(tmp);tmp = obj->front;obj->k--;}free(obj);
}

2.8总代码

注意把判空判满提前引用！！！

typedef struct listNode {int data;struct Node* next;
}Node;typedef struct {Node* front;Node* tail;int k;
}MyCircularQueue;bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));cq->front = cq->tail = (Node*)malloc(sizeof(Node));cq->k = k;//创造一个循环链表//这里其实已经开辟了k+1个空间了注意while (k){Node* cur= (Node*)malloc(sizeof(Node));cur->data = 0;cur->next = NULL;cq->tail->next =cur;cq->tail= cq->tail->next;k--;}//开辟好了之后还要把尾和头发一起cq->tail->next =cq->front;cq->tail= cq->front;return cq;
}
//插入
//他这个题目其实是提前开辟好了，让你直接插入就可以了
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//先判满if (myCircularQueueIsFull(obj))return false;//直接在尾上插入obj->tail->data = value;obj->tail= obj->tail->next;return true;
}
//删除
bool myCircularQueueDeQueue(MyCircularQueue* obj) {//先判空if (myCircularQueueIsEmpty(obj))return false;//头删obj->front = obj->front->next;return true;
}int myCircularQueueFront(MyCircularQueue* obj)
{if(myCircularQueueIsEmpty(obj))return -1;return obj->front->data;
}int myCircularQueueRear(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj))return -1;//去找尾Node* cur= obj->front;while (cur->next != obj->tail)cur= cur->next;return cur->data;}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front == obj->tail;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return obj->tail->next == obj->front;
}void myCircularQueueFree(MyCircularQueue* obj) {//和单链表的销毁一样Node* tmp = obj->front;while (obj->k + 1){obj->front = obj->front->next;free(tmp);tmp = obj->front;obj->k--;}free(obj);
}

总结

用两种解法理解了循环队列，想必对链表和队列的知识做到了巩固

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/285174.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Java Synchronized

Java Synchronized

Synchronized Synchronized 原理偏向锁轻量级锁重量级锁 Synchronized特征jdk1.8Synchronized优化了什么？Synchronized修饰范围Synchronized lock 区别 Synchronized 原理 在Java对象内存布局中，每个对象都有一个对象头，其中包含锁状态信息。…
阅读更多...
【stable diffusion扩散模型】一篇文章讲透

【stable diffusion扩散模型】一篇文章讲透

目录 一、引言 二、Stable Diffusion的基本原理 1 扩散模型 2 Stable Diffusion模型架构 3 训练过程与算法细节 三、Stable Diffusion的应用领域 1 图像生成与艺术创作 2 图像补全与修复 3 其他领域 四、Stable Diffusion的优势与挑战 👉优势 &#x1f…
阅读更多...
SpringBoot3集成PostgreSQL

SpringBoot3集成PostgreSQL

标签：PostgreSQL.Druid.Mybatis.Plus； 一、简介 PostgreSQL是一个功能强大的开源数据库系统，具有可靠性、稳定性、数据一致性等特点，且可以运行在所有主流操作系统上，包括Linux、Unix、Windows等。 通过官方文档可以…
阅读更多...
抠门精出游记之吉隆坡篇

抠门精出游记之吉隆坡篇

我在新加坡一直是个街溜子，每天就是到处溜达，当然，时髦的词叫做citywalk。anyway，叫啥不重要，新加坡走腻了，跟老婆申请，去吉隆坡溜达一下，为啥要来吉隆坡呢，说起来还是因…
阅读更多...
day3-QT

day3-QT

1>使用手动连接，将登录框中的取消按钮使用qt4版本的连接到自定义的槽函数中，在自定义的槽函数中调用关闭函。将登录按钮使用qt5版本的连接到自定义的槽函数中，在槽函数中判断ui界面上输入的账号是否为"admin"，密码是…
阅读更多...
【循环神经网络rnn】一篇文章讲透

【循环神经网络rnn】一篇文章讲透

目录 引言 二、RNN的基本原理 代码事例 三、RNN的优化方法 1 长短期记忆网络（LSTM） 2 门控循环单元（GRU） 四、更多优化方法 1 选择合适的RNN结构 2 使用并行化技术 3 优化超参数 4 使用梯度裁剪 5 使用混合精度训练 …
阅读更多...
科技云报道：造完“大模型”，“具身智能”将引领AI下一个浪潮？

科技云报道：造完“大模型”，“具身智能”将引领AI下一个浪潮？

科技云报道原创。 资深机器人专家Eric Jang不久前曾预言：“ChatGPT 曾在一夜之间出现。我认为，有智慧的机器人技术也将如此。” 3月13日深夜，一段人形机器人的视频开始热传。 在视频中，Figure的人形机器人，可以完全…
阅读更多...
研华工控机610L学习笔记2：visualstudio与第一个C#程序

研华工控机610L学习笔记2：visualstudio与第一个C#程序

今日继续学习工控机 C# 编程相关知识： 这篇结束后我将先进行一段时间的C#的学习研究，并写一些C#的笔记 后续再更新工控机编程设计相关 目录 1、安装visualstudio： 2、创建第一个C#程序： 3、寻找C#解决方案源文件： …
阅读更多...
【Godot4.2】基础知识 - Godot中的2D向量

【Godot4.2】基础知识 - Godot中的2D向量

概述 在Godot中，乃至一切游戏编程中，你应该都躲不开向量。这是每一个初学者都应该知道和掌握的内容，否则你将很难理解和实现某些其实原理非常简单的东西。 估计很多刚入坑Godot的小伙伴和我一样，不一定是计算机专业或编程相关专…
阅读更多...
pytorch 实现多层神经网络MLP（Pytorch 05）

pytorch 实现多层神经网络MLP（Pytorch 05）

一 多层感知机 最简单的深度网络称为多层感知机。多层感知机由 多层神经元 组成，每一层与它的上一层相连，从中接收输入；同时每一层也与它的下一层相连，影响当前层的神经元。 softmax 实现了 如何处理数据，如何将 输出…
阅读更多...
SpringAOP+自定义注解实现限制接口访问频率，利用滑动窗口思想Redis的ZSet（附带整个Demo）

SpringAOP+自定义注解实现限制接口访问频率，利用滑动窗口思想Redis的ZSet（附带整个Demo）

目录 1.创建切面 2.创建自定义注解 3.自定义异常类 4.全局异常捕获 5.Controller层 demo的地址，自行获取《《—————————————————————————— Spring Boot整合Aop面向切面编程实现权限校验，SpringAop自定义注解自定义异常全局…
阅读更多...
【微服务】Gateway服务网关

【微服务】Gateway服务网关

📝个人主页：五敷有你 🔥系列专栏：微服务 ⛺️稳中求进，晒太阳 Spring Cloud Gateway 是 Spring Cloud 的一个全新项目，该项目是基于 Spring 5.0，Spring Boot 2.0 和 Project Reactor 等响…
阅读更多...
Windows 设置多显示器显示

Windows 设置多显示器显示

Windows 设置多显示器显示 1. Windows 7 设置 HDMI 输出2. Windows 11 设置多显示器显示References 1. Windows 7 设置 HDMI 输出 2. Windows 11 设置多显示器显示 ​​​ References [1] Yongqiang Cheng, https://yongqiang.blog.csdn.net/
阅读更多...
Ubuntu Desktop 安装谷歌拼音输入法

Ubuntu Desktop 安装谷歌拼音输入法

Ubuntu Desktop 安装谷歌拼音输入法 1. Installation1.1. 汉语语言包​1.2. 谷歌拼音输入法1.3. 安装语言包1.4. 键盘输入方式系统1.5. 重启电脑1.6. 输入法配置 2. configuration2.1. Text Entry Settings… 3. ExecutionReferences 1. Installation 1.1. 汉语语言包 strong…
阅读更多...
odoo扩展导出pdf功能

odoo扩展导出pdf功能

1. 说明: odoo原生导出功能扩展导出pdf文件功能, 如有额外需求请联系博主 2. 版本说明: odoo版本: odoo15 其他odoo版本未进行测试,如有需要自行测试 3. 地址: 该补丁代码放在github仓库, 地址: https://github.com/YSL-Alpaca/odoo_export_pdf 4. 改补丁依赖于第三方软件wkh…
阅读更多...
网盘——数据库操作

网盘——数据库操作

关于网盘的数据库模块，主要有以下几个内容：定义数据库操作类、将数据库操作类定义成单例模式、数据库操作 数据库是在Qt里面，定义成操作类，专门用这个类产生对象，对数据库实现操作，那么我们在产生对象的时…
阅读更多...
音视频领域首个，阿里云推出华为鸿蒙 HarmonyOS NEXT 版音视频 SDK

音视频领域首个，阿里云推出华为鸿蒙 HarmonyOS NEXT 版音视频 SDK

近日，阿里云在官网音视频终端 SDK 栏目发布适配 HarmonyOS NEXT 的操作文档和 SDK，官宣 MediaBox 音视频终端 SDK 全面适配 HarmonyOS NEXT。 此外，阿里云播放器 SDK 也在华为开发者联盟官网鸿蒙生态伙伴 SDK 专区同步上线，面向所…
阅读更多...
Linux系统——硬件命令

Linux系统——硬件命令

目录 一.网卡带宽 1.查看网卡速率——ethtool 网卡名 2.查看mac地址——ethtool -P 网卡名 二、内存相关 1.显示系统中内存使用情况——free -h 2.显示内存模块的详细信息——dmidecode -t memory 三、CPU相关 1.查看CPU架构信息——lscpu 2.性能模式 四、其他硬件命…
阅读更多...
Java微服务分布式分库分表ShardingSphere - ShardingSphere-JDBC

Java微服务分布式分库分表ShardingSphere - ShardingSphere-JDBC

🌹作者主页：青花锁 🌹简介：Java领域优质创作者🏆、Java微服务架构公号作者😄 🌹简历模板、学习资料、面试题库、技术互助 🌹文末获取联系方式 📝 往期热门专栏回顾 专栏…
阅读更多...
个人博客系列-后端项目-系统角色配置（8）

个人博客系列-后端项目-系统角色配置（8）

系统角色配置需要设置的接口 用户可以绑定多个角色，角色对应有多个路由权限。用户绑定角色后，可以访问当前角色下的各个api路由和菜单路由。 用户注册时设置用户角色修改用户角色（同时对应用户可以访问的路由将会同步变更）添加修…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023