【初阶数据结构】深入解析循环队列:探索底层逻辑

请添加图片描述

🔥引言

本篇将介绍如何实现循环队列并实现过程需要注意的事项,虽然篇幅较小,但是其中逻辑还是值得引人思考的,循环队列可以采用数组或链表实现,这篇将采用数组实现循环队列

请添加图片描述
Alt

🌈个人主页:是店小二呀
🌈C语言笔记专栏:C语言笔记
🌈C++笔记专栏: C++笔记
🌈初阶数据结构笔记专栏: 初阶数据结构笔记

🌈喜欢的诗句:无人扶我青云志 我自踏雪至山巅
请添加图片描述

文章目录

  • 一、循环队列的概念
  • 二、实现循环队列的知识铺垫(核心实现逻辑)
    • 2.1 队列满足什么条件为空
    • 2.2 解决何时为空何时为满的方案
    • 2.3 小总结
    • 2.4 循环队列中如何保证闭环
    • 2.5 计算循环队列的数据个数
  • 三、实现循环队列相关步骤
    • 3.1 循环队列的搭建
    • 3.2 构建器(设置队列长度为 k)
    • 3.3 判断循环队列是否为满和空的情况
    • 3.4 检查是否能插入数据和删除数据
    • 3.5 获得队首元素和队尾元素
    • 3.6 循环的销毁

一、循环队列的概念

循环队列是一种用数组实现的队列数据结构,与普通队列不同的是,循环队列允许队列的头尾相接,实现循环利用数组空间。它解决了普通队列在出队操作频繁时需要大量元素迁移的效率问题。循环队列通常通过两个指针来实现:一个指向队列的头部(front),一个指向队列的尾部(rear)。当队列满时,rear 指针可以绕回到数组的起始位置,实现循环存储;当队列为空时,front 和 rear 指针指向同一个位置。

在这里插入图片描述

在这里插入图片描述

二、实现循环队列的知识铺垫(核心实现逻辑)

2.1 队列满足什么条件为空

当front==back时不一定为空。这里是循环队列,如果出现front= =back时会出现下列两种情况

  • back通过循环与front相遇,此时front==back,则队列满了
  • 一开始back没有移动,back和front在同位置,此时front==back,则队列为空

对此我们无法通过front==back区分开空和满的情况,需要重新定义为空或满的标志

2.2 解决何时为空何时为满的方案

关于front和back初始位置,front指向对头,而由于back指向队尾会很难看,需要手动back置为-1,对此这里back指向队尾的下一个元素(跟栈中top定义问题是类似的)

判断满的两种方案:

  • 增加一个size,当front== back并且size= =0就为空,size!=0就是为满
  • 多开一个空间,这样的好处就是back+1==front为满(不要存储数据,这样又回到了不能判断空或满)

2.3 小总结

这里我们选择第二种方案进行实现,对此我们总结下,定义好的方式。

  1. front == back就是为空
  2. back + 1 == front就是为满

2.4 循环队列中如何保证闭环

如果遇到循环相关问题,可以考虑取模(解决问题上十分巧妙)。我们想要达到的目的是当back到达空位置时,就是相当于到了头位置。

同时取模中,如果左边小于右边,没有改变。如果左边大于左边,就会删除右边的倍数,直到左边小于右边(这里就是取模的逻辑,如果很难理解,可以通过图来理解下)

在这里插入图片描述

在这里插入图片描述

这里需要注意的是:这张图我们需要关注的地方back + 1和 head的位置k +1是空位置下标为4和0位置重叠处三处。这里size为有效元素个数,这里只多开一个空间并没有算上有效元素,然后k + 1到达空位置,我们想要的结果是我们想要达到的目的是当back到达空位置时,就是相当于到了头位置,这里(obj->back+1)%(obj->size+1)==obj->head;就满足了这种情况,相同数据取模模为0,意味着下标为0

2.5 计算循环队列的数据个数

如果是计算队列的数据个数,通常就是back - front,但是这里是循环队列可能会出现back在front前面的特殊情况。

在这里插入图片描述

解决措施:(back+(k+1)-front)%k+1。这里担心back - front出现负数,个数不是存在负数这种情况的。那么可以将back + (k + 1) - front % k + 1这样保证了back - front + (k + 1) % k + 1当back - front出现负数,增加k + 1保证了正数再取模保证数据没有超过循环队列的长度,那么这样得到数据个数是否正确呢?通过画图在整个循环中的代表位置是相同的。

只要理解上面相关知识,模拟实现循环队列也变得简单起来了,让我们模拟实现起来吧!

三、实现循环队列相关步骤

3.1 循环队列的搭建

typedef struct
{int *a;int size;int head;int back;//元素的下一个位置
} MyCircularQueue;
//head 和 back都为下标

这里需要注意的是:这里没有跟队列一样采用两个结构体设计,而是采用在结构体对象内开辟一块空间用于存储节点,再调用结构体成员进行头尾操作,达到循环队列的功能。

3.2 构建器(设置队列长度为 k)

MyCircularQueue* myCircularQueueCreate(int k) //为结构体开辟空间
{   MyCircularQueue *obj=(MyCircularQueue *)malloc(sizeof(MyCircularQueue));if(obj==NULL)return NULL;obj->a=(int *)malloc(sizeof(int)*(k+1));//多开一个空间if(obj->a==NULL)return NULL;obj->size=k;obj->back=obj->head=0;return obj;
}

这里需要注意的是:关于两次调用malloc函数开辟空间,第一次malloc开辟空间,用于为该结构体对象开辟空间,第二次malloc开辟空间,是为了队列元素开辟空间(包含了不存放数据的空间),这空间是关联在一起的,对此需要搞清楚需要开辟多大的空间和交给什么数据类型维护

3.3 判断循环队列是否为满和空的情况

bool myCircularQueueIsFull(MyCircularQueue* obj) 
{return (obj->back+1)%(obj->size+1)==obj->head;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{assert(obj);return obj->head==obj->back;
}

这里需要注意的是:对于判断是否为空,不是重点,对于判断是否为满,根据取模的特点进行处理,对于数据结构处理建议画图分析

3.4 检查是否能插入数据和删除数据

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value){if(myCircularQueueIsFull(obj))return false;obj->a[obj->back]=value;obj->back++;//防止越界obj->back%=(obj->size+1);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj)
{if(myCircularQueueIsEmpty(obj))return false;obj->head++;//防止越界obj->head%=(obj->size+1);return true;
}

这里需要注意的是:这里无论是插入还是删除数据,需要对x %= (obj->size+1);防止超过队列长度,而且这里需要注意顺序问题

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

3.5 获得队首元素和队尾元素

int myCircularQueueFront(MyCircularQueue* obj){if(myCircularQueueIsEmpty(obj))return -1;return obj->a[obj->head];
}
int myCircularQueueRear(MyCircularQueue* obj)
{if(myCircularQueueIsEmpty(obj))return -1;if(obj->back==0)//插入的时候return obj->a[obj->size];//表示尾的情况elsereturn obj->a[obj->back-1];//return obj->a[(obj->back-1+obj->size+1)%(obj->size+1)];
}

这里需要注意的是:这里获得队首元素和队尾元素,都需要先判断循环队列是否为空。在获得队尾元素中,一般情况下 obj->a[obj->back-1]是没有问题的,但是如果在插入一个数据,back回到首元素位置上,back-1就会出现问题,会导致越界访问,对此obj->a[(obj->back-1+obj->size+1)%(obj->size+1)]; 可以将这个循环队列展开一段,加obj->size+1再取obj->size+1模,这里同计算循环队列有效数据长度的方式是一样的。

3.6 循环的销毁

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

请添加图片描述

以上就是本篇文章的所有内容,在此感谢大家的观看!这里是店小二初阶数据结构笔记,希望对你在学习初阶数据结构中有所帮助!

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

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

相关文章

【数据结构】05.双向链表

一、双向链表的结构 注意:这里的“带头”跟前面我们说的“头节点”是两个概念,带头链表里的头节点,实际为“哨兵位”,哨兵位节点不存储任何有效元素,只是站在这里“放哨的”。 “哨兵位”存在的意义:遍历循…

cs231n作业1——KNN

参考文章:assignment1——KNN KNN 测试时分别计算测试样本和训练集中的每个样本的距离,然后选取距离最近的k个样本的标签信息来进行分类。 方法1:Two Loops for i in range(num_test):for j in range(num_train):dist X[i, :] - self.X…

Python爬虫获取视频

验证电脑是否安装python 1.winr输入cmd 2.在黑窗口输入 python.exe 3.不是命令不存在就说明python环境安装完成 抓取快手视频 1.在phcharm应用中新建一个项目 3.新建一个python文件 4.选择python文件,随便起一个名字后按回车 5.安装requests pip install requests 6.寻找需要的…

苹果电脑能玩赛博朋克2077吗 如何在mac上运行赛博朋克2077 crossover能玩什么游戏

各位喜欢赛博朋克风的一定不能错过《赛博朋克2077》。那么《赛博朋克2077》是一款什么样的游戏?《赛博朋克2077》在苹果电脑上可以运行吗?一起来看看介绍吧。 一、《赛博朋克2077》是一款什么样的游戏? 《赛博朋克2077》是一款由CD Projekt …

【Java探索之旅】初识多态_概念_实现条件

文章目录 📑前言一、多态1.1 概念1.2 多态的实现条件 🌤️全篇总结 📑前言 多态作为面向对象编程中的重要概念,为我们提供了一种灵活而强大的编程方式。通过多态,同一种操作可以应用于不同的对象,并根据对象…

Spring Boot基础篇

快速上手 SpringBoot是由Pivotal团队提高的全新框架,其设计目的是用来简化Spring应用的初始化搭建以及开发过程 入门案例 在Idea创建 创建时要选择Spring Initializr。 Server URL为要连接的网站,默认为官网start.spring.io(访问速度慢&…

【教程】新的Selenium!整合了隐藏浏览器指纹等功能

转载请注明出处:小锋学长生活大爆炸[xfxuezhagn.cn] 如果本文帮助到了你,欢迎[点赞、收藏、关注]哦~ 目录 前景提要 driver Driver() 常用driver 接口 最后的话 前景提要 新的selenium,整合了隐藏浏览器指纹,非常好用&#x…

树状数组求三元上升子序列

分析一下,感觉没什么思路,再想一下,结果不就是每一位的数小于它的数乘以大于大于这位数的相乘之和吗,我们可以利用逆序对的思维求得 关键点在于求解逆序对的时候值相同的时候,位置大的优先级更高处理 #define _CRT_SEC…

大型能源电力集团需要什么样的总部数据下发系统?

能源电力集团的组织结构是一个复杂的系统,包括多个职能部门和子分公司。这些子分公司负责具体的电力生产、销售、运维等业务。这些部门和公司协同工作,确保电力生产的顺利进行,同时关注公司的长期发展、市场拓展、人力资源管理、财务管理和公…

算法 —— 滑动窗口

目录 长度最小的子数组 无重复字符的最长子串 最大连续1的个数 将x减到0的最小操作数 找到字符串中所有字母异位词 最小覆盖子串 长度最小的子数组 sum比target小就进窗口,sum比target大就出窗口,由于数组是正数,所以相加会使sum变大&…

数据结构基础--------【二叉树基础】

二叉树基础 二叉树是一种常见的数据结构,由节点组成,每个节点最多有两个子节点,左子节点和右子节点。二叉树可以用来表示许多实际问题,如计算机程序中的表达式、组织结构等。以下是一些二叉树的概念: 二叉树的深度&a…

Ubuntu 20.04下多版本CUDA的安装与切换 超详细教程

目录 前言一、安装 CUDA1.找到所需版本对应命令2.下载 .run 文件3.安装 CUDA4.配置环境变量4.1 写入环境变量4.2 软连接 5.验证安装 二、安装 cudnn1.下载 cudnn2.解压文件3.替换文件4.验证安装 三、切换 CUDA 版本1.切换版本2.检查版本 前言 当我们复现代码时,总会…

计算机如何存储浮点数

浮点数组成 在计算机中浮点数通常由三部分组成:符号位、指数位、尾数位。IEEE-754中32位浮点数如下: 上图32bit浮点数包含1bit的符号位,8比特的指数位和23bit的尾数位。对于一个常规浮点数,我们来看看它是如何存储和计算的。这里…

数据库系统原理 | 查询作业2

整理自博主本科《数据库系统原理》专业课自己完成的实验课查询作业,以便各位学习数据库系统概论的小伙伴们参考、学习。 *文中若存在书写不合理的地方,欢迎各位斧正。 专业课本: ​ ​ ———— 本次实验使用到的图形化工具:Heidi…

CTF常用sql注入(一)联合注入和宽字节

0x01 前言 给自己总结一下sql注入的常用姿势吧,记录一下学习 0x02 联合 联合注入的关键词是union SQL的union联合注入原理是联合两个表进行注入攻击,使用union select关键词来进行联合查询。 那么为什么我们在题目中一般是只写一个呢 因为 $sql &quo…

SwiftData 模型对象的多个实例在 SwiftUI 中不能及时同步的解决

概览 我们已经知道,用 CoreData 在背后默默支持的 SwiftUI 视图在使用 @FetchRequest 来查询托管对象集合时,若查询结果中的托管对象在别处被改变将不会在 FetchedResults 中得到及时的刷新。 那么这一“囧境”在 SwiftData 里是否也会“卷土重来”呢?空说无益,就让我们在…

redis 如何使用 scan, go语言

建议用方案乙 文章目录 场景方案方案甲方案乙 拓展 场景 redis 中存在大量 key。 其中有一部分是用户登陆的 session_id, 结构是 : session_id:1session_id:2session_id:3需求: 有多少用户在线 方案 方案甲 keys session_id:*这种方式简…

FlinkSQL 开发经验分享

作者:汤包 最近做了几个实时数据开发需求,也不可避免地在使用 Flink 的过程中遇到了一些问题,比如数据倾斜导致的反压、interval join、开窗导致的水位线失效等问题,通过思考并解决这些问题,加深了我对 Flink 原理与机…

华为云简介

前言 华为云是华为的云服务品牌,将华为30多年在ICT领域的技术积累和产品解决方案开放给客户,致力于提供稳定可靠、安全可信、可持续创新的云服务,赋能应用、使能数据、做智能世界的“黑土地”,推进实现“用得起、用得好、用得放心…

鸿蒙应用笔记

安装就跳过了,一直点点就可以了 配置跳过,就自动下了点东西。 鸿蒙那个下载要12g个内存,大的有点吓人。 里面跟idea没区别 模拟器或者真机运行 真机要鸿蒙4.0,就可以实机调试 直接在手机里面跑,这个牛逼&#xf…