数据结构——循环队列的实现

💞💞 前言

hello hello~ ,这里是大耳朵土土垚~💖💖 ,欢迎大家点赞🥳🥳关注💥💥收藏🌹🌹🌹
在这里插入图片描述

💥个人主页:大耳朵土土垚的博客
💥 所属专栏:数据结构学习笔记
💥对于数据结构顺序表、链表、堆有疑问的都可以在上面数据结构的专栏进行学习哦~ 有问题可以写在评论区或者私信我哦~

之前我们学习过数据结构中的栈和队列,详情可点击这里数据结构——lesson5栈和队列详解进行查看🥳🥳,队列是一种先进先出的结构,但是我们之前讲的队列都是类似于线性的物理结构,这次我们所介绍的队列则是一直类似于环状的循环结构,它依旧保持着队列的特性——先进先出。

1.循环队列的介绍

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

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

循环队列的实现应该支持如下操作:

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

题目链接——循环队列OJ题大家也可以在学习完栈和队列后自己尝试写一写。

在这里插入图片描述

2.循环队列实现思路分析

首先根据题目要求,队列长度为k,所以一开始我们要使用malloc开辟k个节点的空间,而不是和之前的队列一样在增加数据时再开辟节点,循环队列的长度是固定的,最开始就已经开辟好了,所以不需要再在使用时开辟节点空间。
在这里插入图片描述
如上图所示,已经在内存中开辟了完整的空间,最开始队列的头尾指针都指向开始的位置,每加一个元素,rear指针也就是尾指针的位置就往后挪动一位,删除数据就把头指针front往后挪一位,当rear指针指向最后一个元素时,队列满了,此时的判断条件应该时rear->pNext = front;
也就是说rear的下一个位置是front,如下图所示:
在这里插入图片描述
思考一下:rear指向的是尾部的元素还是尾部元素的下一位呢?
1.zz如果rear指向的是尾部元素,那么在实现时判断循环队列是否满的条件就是rear->pNext = front;
但是💥💥判断循环队列是否为空的条件就不简单是rear == front,因为在插入第一个元素时,front指向该元素,rear指向最后一个元素也就是刚刚插入的第一个元素,因为此时队列中只有一个元素,此时rear == front ,但此时循环队列不为空;
2.但如果循环队列的rear指针指向尾部元素的下一个就好判断了,为空时rear==front;
不为空时rear!=front;即使只有一个元素,rear也不指向该元素而是指向该元素的下一位,但是💥💥在判断循环队列是否满时又出了问题,当循环队列满了的时候,rear指向队尾元素的下一个,此时rear指向front,这不就和为空的条件冲突了吗?
解决办法
🥳🥳1.针对第一种rear指向尾部元素:
可以考虑在创建队列时不单单创建front(队列头指针)和rear(队列尾指针)这两个元素,可以增加一个 size来记录此时队列里的节点个数;
🥳🥳2.针对第二种rear指向尾部元素的下一个位置:
①也可以增加一个size来记录存放的节点个数
②考虑多开辟一个节点的空间(需要k个节点就开辟k+1个节点的空间),剩下一个节点的位置不存放数据,是专门用来防止队列满时rear的下一个元素指向front,如果增加一个空闲的位置,队列满时rear的下一个位置就不再指向front;

💫💫在决定选哪种方法之前,我们先要考虑一下是使用链表来实现还是使用数组也就是顺序表来实现循环队列;当然这里土土会将两种方法都写下来,并和大家一起分析两种方法的优劣之处,以便大家选择合适和喜欢的形式🥰🥰(对于顺序表链表有疑问的可以在土土的数据结构专栏里——数据结构学习笔记 进行查看复习哦~)

3.用单链表实现循环队列

✨✨经过我深思熟虑(其实是随便选的😎😎),决定采用第一种rear指向队尾元素的方法来实现,虽然第二种方法我给出了两种解决办法,但是我发现第一种方法在求队尾元素时异常的方便,只要return rear->data就好了,如果是第二种rear指向队尾元素的下一个,那么我们求队尾元素时还需要找到rear的前一个指针,如果我们使用双向链表就会很简单,但这里我选择使用单链表来实现;

3.1设计队列结构

前面我们提到过设计队列时考虑加上一个size记录存放节点个数以便判断队列是否为空

typedef struct {CQNode* front;CQNode* rear;int size;//记录容量
} MyCircularQueue;

队列的节点和单链表一致:data存放数据;pNext存放下一个节点指针

// 链式结构:表示队列 
typedef int CQDataType;
typedef struct CQListNode
{struct CQListNode* pNext;CQDataType data;
}CQNode;

3.2构造队列(k个节点)

MyCircularQueue(k): 构造器,设置队列长度为 k

这里我们除了需要malloc k个节点外,还需要将这k个节点串联在一起使他们物理结构上成环(对于malloc有疑问的可以查看土土的博客——C语言动态内存函数介绍)代码如下:

//构造k个节点的循环队列
MyCircularQueue* myCircularQueueCreate(int k) {//开辟k个空间并链接k个节点CQNode* kqueue = (CQNode*)malloc(sizeof(CQNode) * k);if (kqueue == NULL){perror("malloc fail1");return NULL;}for (int i = 0; i < k - 1; i++)//注意这里是k-1,因为尾节点需要单独链接头节点{(kqueue + i)->pNext = kqueue + i + 1;}//最后再把尾指针指向的下一位指向头即可成环(kqueue + k - 1)->pNext = kqueue;//开辟循环队列空间MyCircularQueue* queue = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));if (queue == NULL){perror("malloc fail2");return NULL;}queue->front = kqueue;queue->rear = kqueue;//尾指向最后一个元素,不是最后元素的下一个queue->size = 0;//记录队列大小return queue;}

调试时我们发现成功构造了循环队列:
在这里插入图片描述

后面pNext又回到了最开始的位置说明我们链接成功啦🎉🎉🎉

在这里插入图片描述

我们还将队列的头尾指针与开辟的k个节点做了连接,使得队列的头尾指针指向了k个节点的地址,并将size初始化为0;

3.3 向循环队列插入一个元素

myCircularQueueEnQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。代码如下:

//插入数据
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{assert(obj);//判断队列是否满了if(myCircularQueueIsFull(obj)){return false;}//插入队列//1.队列无元素的情况if (myCircularQueueIsEmpty(obj)){obj->front->data = value;obj->rear->data = value;obj->size++;return true;}
//2.队列有元素的情况obj->rear->pNext->data = value;obj->rear = obj->rear->pNext;obj->size++;return true;
}

🥳🥳 ①这里首先要判断队列是否满了,如果满了则不能再插入元素直接返回false;
🥳🥳② 其次因为我们的rear是指向最后一个元素的所以在插入元素时要分两种情况来看——一种只有一个节点的情况头尾指针都需要变;另一种存放多个节点的情况只需要改变尾指针;
🥳🥳③此外增加元素size++;
✨✨④最后判断循环队列是否为空函数在下面介绍;

3.4判断循环队列是否为空

myCircularQueueIsEmpty(): 检查循环队列是否为空。

bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{assert(obj);if (obj->size == 0)//size为0时队列为空return true;return false;
}

3.5判断循环队列是否满了

myCircularQueueIsFull(): 检查循环队列是否已满。

bool myCircularQueueIsFull(MyCircularQueue* obj)
{assert(obj);//?if(obj->size == k)if (obj->rear->pNext == obj->front){//只有一个节点的情况if (obj->size != 0){return true;}}return false;
}

这里我们看到我打了一个?,obj->size ==k是不能判断队列是否满了的,因为k并没有作为参数传给判满函数,我们根本不能使用k,k
只在构造队列时出现过;
✨✨我们还发现这里出现了只有一个节点的情况,因为当队列构造时传的k == 1,也就是整个循环队列只有一个节点,那么无论队列中是否有节点rear的下一个位置始终时front,此时该判断条件不成立,所以我们需要将该情况单独列出来,当rear->pNext 等于front时并且obj->size 不等于0时才能判断队列满了return true;其他情况return false;

3.6从循环队列中删除一个元素

myCircularQueueDeQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。注意队列先进先出,是头删。

//删除数据
bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{assert(obj);if(myCircularQueueIsEmpty(obj)){return false;}//头删,因为是先进先出//1.只有一个元素,此时头尾指针指向同一个位置,都需要改if (obj->front == obj->rear){obj->front = obj->front->pNext;obj->rear = obj->rear->pNext;obj->size--;return true;}//2.多个元素obj->front = obj->front->pNext;obj->size--;return true;
}

这里和插入一个元素一样也要分两种情况,size对应-1;就不过多赘述

3.7 从队首获取元素

myCircularQueueFront: 从队首获取元素。如果队列为空,返回 -1 。

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

3.8获取队尾元素

Rear: 获取队尾元素。如果队列为空,返回 -1 。

int myCircularQueueRear(MyCircularQueue* obj) 
{assert(obj);if(myCircularQueueIsEmpty(obj)){return -1;}return obj->rear->data;
}

3.9销毁循环队列

void myCircularQueueFree(MyCircularQueue* obj)
{assert(obj);free(obj->front);free(obj);return;
}

3.10结果如下

在这里插入图片描述

4.用数组实现循环队列

4.1设计队列结构

前面我们提到过设计队列时考虑加上一个size记录存放节点个数以便判断队列是否为空

typedef struct {int front;//首下标int rear;//尾下标int* a;//数组int k;//记录k值
} MyCircularQueue;

这里采用一个结构体封装,并记录数组的首尾下标,并保留一个k来记录k值,以便后面使用。

4.2构造队列(k+1个节点)

MyCircularQueue(k): 构造器,设置队列长度为 k

MyCircularQueue* myCircularQueueCreate(int k) {//开辟循环队列空间MyCircularQueue* queue = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));if (queue == NULL){perror("malloc fail1");return NULL;}//开辟数组空间queue->a = (int*)malloc(sizeof(int)*(k+1));if (queue->a == NULL){perror("malloc fail2");return NULL;}queue->front = 0;queue->rear = 0;//尾指向最后一个元素的下一个queue->k = k;//记录k,后面使用return queue;}

这里注意开辟了(k+1)个节点空间,采用的是前面说的第二种情况,rear指向最后一个元素的下一个位置。

4.3向循环队列插入一个元素

myCircularQueueEnQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。代码如下:

//插入数据
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{assert(obj);//判断队列是否满了if(myCircularQueueIsFull(obj)){return false;}//插入队列//1.队列无元素的情况if (myCircularQueueIsEmpty(obj)){obj->a[obj->front] = value;obj->rear++;obj->rear %= obj->k+1;return true;}
//2.队列有元素的情况obj->a[obj->rear] = value;obj->rear ++;obj->rear %= obj->k+1;return true;
}

这里也分两种情况来插入,💥💥此外还要注意插入元素之后rear要++,但是如果rear超过数组的长度k+1就会造成越界访问,所以这里提供了一个方法:每次rear++之后再与k+1取模运算,这样就可以得到小于等于k的值,不会造成越界访问。

4.4判断循环队列是否为空

myCircularQueueIsEmpty(): 检查循环队列是否为空。

bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{assert(obj);if (obj->front == obj->rear)return true;return false;
}

因为rear指向最后一个元素的下一个元素,所以当rear等于front时,数组为空,此时一个数据也没有插入。

4.5判断循环队列是否满了

myCircularQueueIsFull(): 检查循环队列是否已满。

bool myCircularQueueIsFull(MyCircularQueue* obj)
{assert(obj);if((obj->rear+1)%(obj->k+1)==obj->front){return true;}return false;
}

数组并非像链表那样有pNext指针指向下一个节点,链表可以形成天然的循环结构,而数组却要依靠首尾下标来模拟实现,如图所示有两种情况:
在这里插入图片描述

当删除节点时只需将front++即可,所以front位置可能不是0;

4.6从循环队列中删除一个元素

myCircularQueueDeQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。注意队列先进先出,是头删。

//删除数据
bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{assert(obj);if(myCircularQueueIsEmpty(obj)){return false;}//头删,因为是先进先出obj->front++;obj->front %= obj->k+1;return true;
}

注意这里front也是一样,在+1后可能大于k造成越界,所以要进行取模运算。

4.7 从队首获取元素

myCircularQueueFront: 从队首获取元素。如果队列为空,返回 -1 。

int myCircularQueueFront(MyCircularQueue* obj) 
{assert(obj);if(myCircularQueueIsEmpty(obj))return -1;return obj->a[obj->front];
}

4.8获取队尾元素

Rear: 获取队尾元素。如果队列为空,返回 -1 。

int myCircularQueueRear(MyCircularQueue* obj) 
{assert(obj);if(myCircularQueueIsEmpty(obj)){return -1;}return obj->a[(obj->rear+obj->k)%(obj->k+1)];
}

这里要注意本来应该返回rear-1;因为rear指向尾节点的下一位,但是如果rear值为0时,再-1就变成-1了,也会造成越界访问,所以也要进行取模运算(rear-1+k+1)%(k+1),即可,因为数组有k+1个节点所以要+(k+1)并%(k+1)

3.9销毁循环队列

void myCircularQueueFree(MyCircularQueue* obj) 
{assert(obj);free(obj->a);free(obj);return;
}

3.10结果如下:

在这里插入图片描述

5.结语

链表来实现循环队列有一个好处就是形成了天然的环形结构,对应数组实现循环队列则需要front,rear不断进行取模运算以防越界;
但是链表实现需要手动将开辟的节点链接在一起,数组则不一样它一开辟就是地址连续的一段空间;
其他的实现链表和数组都差不多;
以上就是循环队列的实现啦~ 大家有什么疑问可以写在评论区或者私信我哦~ 完结撒花~🥳🥳🎉🎉🎉

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

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

相关文章

UDS协议从入门到入坑分享

** 一、概念先行 ** UDS&#xff08;全称&#xff1a;UnifiedDiagnostic Services&#xff09;&#xff0c;诊断协议是在汽车电子ECU环境下的一种诊断通信协议&#xff0c;在ISO 14229中规定。 目前市面上的新车都具有用于车外诊断的诊断接口&#xff0c;这使得我们可以用电脑…

ArcGIS添加天地图底图服务

目录 一、注册天地图官网、申请Key 二、ArcGis配置和使用 1、配置 2、使用 三、其他方法 一、注册天地图官网、申请Key 进入官网&#xff0c;并注册账号。 地址&#xff1a;国家地理信息公共服务平台 天地图 (tianditu.gov.cn) 点击地图API&#xff0c;申请Key。 注意&am…

【Java Web基础】一些网页设计基础(四)

文章目录 1. 做Tab切换2. 下面的内容展示——Card样式3. 采供分类&#xff0c;分类用面包屑导航做4. 出名企业展示&#xff0c;就是普通的图片5. 用热门商品类似的panel做一个农博会展览 1. 做Tab切换 使用BootStrap提供的样式&#xff1a; <ul class"nav nav-tabs&q…

Python基础学习笔记(一)

Python简介 Python 语言是一种跨平台、开源、免费、解释型、面向对象、动态数据类型的高级程序设计语言。早期版本的 Python 被称作是 Python1&#xff1b;Python2 最后一个版本是 2.7&#xff1b;Python3 是目前最活跃的版 本&#xff0c;基本上新开发的 Python 代码都会支持…

视频批量爬虫下载工具|可导出视频分享链接|抖音视频提取软件

便捷的视频批量爬虫软件操作指南 抖音视频下载界面图解 主要功能&#xff1a; 关键词批量提取视频和单独视频提取&#xff0c;提取后下载功能。 功能解析&#xff1a; 1. 关键词批量采集视频的解析 对特定关键词进行搜索和视频提取&#xff0c;例如输入“汽车配件”&#x…

C#探索之路基础篇(1):编程中面向过程、数据、对象的概念辨析

文章目录 C#探索之路基础篇(1)&#xff1a;编程中面向过程、数据、对象的概念辨析1 面向过程编程1.1 概念1.2 示例代码&#xff1a;1.3 使用范围与时机&#xff1a;1.4 注意事项&#xff1a;1.5 通俗讲法 2 面向对象编程2.1 概念2.2 示例代码2.3 使用范围2.4 注意事项2.5 通俗讲…

【吾爱破解】Android初级题(二)的解题思路 _

拿到apk&#xff0c;我们模拟器打开看一下 好好&#xff0c;抽卡模拟器是吧&#x1f600; jadx反编译看一下源码 找到生成flag的地方&#xff0c;大概逻辑就是 java signatureArr getPackageManager().getPackageInfo(getPackageName(), 64).signaturesfor (int i 0; i &l…

2024.3.22 使用nginx在window下运行前端页面

2024.3.22 使用nginx在window下运行前端页面 使用nginx可以在本地运行前端程序&#xff0c;解决本地前后端程序跨域问题&#xff0c;是个前期编程及测试的好办法。 nginx下载 直接在官网下载 本次选择了1.24版本&#xff08;stable version&#xff09; nginx安装 解压后…

公司系统中了.rmallox勒索病毒如何恢复数据?

早晨上班时刻&#xff1a; 当阳光逐渐洒满大地&#xff0c;城市的喧嚣开始涌动&#xff0c;某公司的员工们纷纷踏入办公大楼&#xff0c;准备开始新的一天的工作。他们像往常一样打开电脑&#xff0c;准备接收邮件、查看日程、浏览项目进展。 病毒悄然发作&#xff1a; 就在员…

【计算机】——51单片机

单片机是一种内部包含CPU、存储器和输入/输出接口等电路的集成电路&#xff08;IC芯片&#xff09; 单片机是单片微型计算机&#xff08;Single Chip Microcomputer&#xff09;的简称&#xff0c;用于控制领域&#xff0c;所以又称为微型控制器&#xff08;Microcontroller U…

Eclipse For ABAP:安装依赖报错

1.安装好Eclipse后需要添加依赖,这里的地址: https://tools.hana.ondemand.com/latest 全部勾选等待安装结束; 重启后报错:ABAP communication layer is not configured properly. This might be caused by missing Microsoft Visual C++ 2013 (x64) Runtime DLLs. Consu…

Http中Host,Referer,Origin和Access-Control-Allow-Origin

Http中Host&#xff0c;Referer&#xff0c;Origin和Access-Control-Allow-Origin 文章目录 Http中Host&#xff0c;Referer&#xff0c;Origin和Access-Control-Allow-OriginHost定义特性作用 Referer定义特性作用 Origin定义特性作用 Access-Control-Allow-Origin定义特性作用…

【Arxml专题】-29-使用Cantools将CAN Matrix Arxml自动生成C语言代码

目录 1 安装Python和Cantools 1.1 查看Python已安装的Package包 1.2 在Python中安装Cantools插件包 1.3 获取更多Cantools工具的更新动态 2 CAN Matrix Arxml自动生成C语言代码 2.1 批处理文件CAN_Matrix_Arxml_To_C.bat内容说明 2.2 CAN Matrix Arxml文件要求 2.3 如何…

ideaSSM 人才引进管理系统bootstrap开发mysql数据库web结构java编程计算机网页源码maven项目

一、源码特点 idea 开发 SSM 人才引进管理系统是一套完善的信息管理系统&#xff0c;结合SSM框架和bootstrap完成本系统&#xff0c;对理解JSP java编程开发语言有帮助系统采用SSM框架&#xff08;MVC模式开发&#xff09;&#xff0c;系统具有完整的源代码和数据库&#xff…

复旦大学MBA首场公开课:独具特色的培养体系和招生政策

3月2日&#xff0c;2025年入学复旦MBA首场公开课暨招生政策发布会圆满收官。心怀梦想、力求突破的青年精英们相聚于复旦&#xff0c;共同聆听一场精彩纷呈的知识盛宴&#xff0c;了解复旦MBA独具特色的培养体系和招生政策&#xff0c;在明媚的春光中迈向崭新的未来。      …

Svg Flow Editor 原生svg流程图编辑器(三)

系列文章 Svg Flow Editor 原生svg流程图编辑器&#xff08;一&#xff09; Svg Flow Editor 原生svg流程图编辑器&#xff08;二&#xff09; Svg Flow Editor 原生svg流程图编辑器&#xff08;三&#xff09; 实现对齐辅助线 在 logicFlow 中&#xff0c;辅助线的实现是通…

易快报与国贸SAP秒同步,数据同步不再是难题!

客户介绍 某国际贸易有限公司是一家在中国享有广泛声誉的国际贸易企业&#xff0c;专注于促进中美两国之间的经贸合作与交流。公司凭借深厚的行业经验和专业的团队&#xff0c;致力于为客户提供高效、可靠的贸易服务&#xff0c;涵盖了多个领域&#xff0c;包括商品进出口、供…

MAC本安装telnet

Linux运维工具-ywtool 目录 1.打开终端1.先安装brew命令2.写入环境变量4.安装telnet 1.打开终端 访达 - 应用程序(左侧) - 实用工具(右侧) - 终端 #注意:登入终端用普通用户,不要用MAC的root用户1.先安装brew命令 /bin/zsh -c "$(curl -fsSL https://gitee.com/cunkai/H…

基于python+vue共享单车信息系统的设计与实现flask-django-php-nodejs

课题主要分为二大模块&#xff1a;即管理员模块和用户模块&#xff0c;主要功能包括&#xff1a;用户、区域、共享单车、单车租赁、租赁归还、报修信息、检修信息等&#xff1b;快速发展的社会中&#xff0c;人们的生活水平都在提高&#xff0c;生活节奏也在逐渐加快。为了节省…

2024全国水科技大会【高峰对话】北京排水集团(附部分报告题目)

北京排水集团坚持“服务社会、造福百姓、企业利益与公众利益高度一致”的宗旨&#xff0c;充分认知自身在地区经济发展中的社会责任&#xff0c;以满足政府与公众对公用事业企业服务的需求为首要任务&#xff0c;通过“现代化的队伍、现代化的手段、现代化的设备和现代化的管理…