(rear + maxSize - front) % maxSize 公式的理解(文图详解,手把手)_Be-make的博客-程序员秘密_front和rear怎么计算

技术标签: python  个人遇到的难题和思考  数据结构  

关于循环队列求队列值有多少值

在B站上学习了数据结构与算法的时候的时候,在环形队列里面有这样一个公式
( r e a r + m a x S i z e − f r o n t ) % m a x S i z e (rear + maxSize - front) \% maxSize (rear+maxSizefront)%maxSize

为了更加深入的了解这个算式为什么是这样,从而窥探算法的大门,于是我思考了一下,并且发现解法

看完这个保证细致到位,各种算式计算例题一步到位

转换我们的公式

( r e a r + m a x S i z e − f r o n t ) % m a x S i z e = ( r e a r − f r o n t + m a x S i z e ) % m a x S i z e (rear + maxSize - front) \% maxSize = (rear - front + maxSize) \% maxSize (rear+maxSizefront)%maxSize=(rearfront+maxSize)%maxSize

为什么要这样转换这个算式,因为这样方便我们进行理解

搞清楚几个问题,我们就能知道这个算式为什么要这样子

  1. 假如是一个正常的队列,我要怎么计算有多少有效数值?
  2. 当我们的索引超出我们的队列,如何让他回归数列?
  3. 当我们使用%的时候,rear和front谁在前谁在后对结果和结果的分析

计算正常队列的有效数字

正常数列就是我们之前学到的,数值只能一次性不能重新循环的版本,在那个版本里面计算有效数值非常简单

于是我们可以想象一个无法循环的循环队列,这听起来很怪,但是我们可以通过简化过后的循环队列来算值
有 效 数 值 = r e a r − f r o n t 有效数值 = rear - front =rearfront

但是这里注意了,我们的rear并非真的是指向我们的最后一个元素,而是指向最后一个元素的后一个位置,所以公式应该变为

有 效 数 值 = r e a r + 1 − f r o n t 有效数值 = rear + 1 - front =rear+1front

当我们的索引超出队列,使用百分号让他回来

使用%可以让那些超过的数字回到队列里面来

比如当我们的rear已经指向了队列.length(实际上这是一个虚拟的位,实际上指向 - 队列.length - 1),这已经没有下一位,于是我们要想办法让他回到我们的队列开头

我们可以看到当我们队列长度为5的时候,不管我们的数值有多大,最终都无法超过5,请看下方GIF

百分号的作用

rear和front在循环队列中的计算

当我们的rear在front的前面(队列已经超过了长度开始循环了)

rear在front的前面

这个时候你可以给我们的尾指针加上我们的数组长度让我们的队列变成这样:

新的队列

这个时候我们的有效值计算公式是什么呢?
r e a r + m a x S i z e − f r o n t rear + maxSize - front rear+maxSizefront

可以看到,已经有点上面的形状了,但是在这种情况下我们不需要加上百分号,可是这个算式就这样结束了吗?

当我们的rear在front的后面(正常情况)

虽然我们现在已经知道循环之后尾巴在前面的有效值怎么算,那么带入刚刚那个算式我们来看看这个正常情况能不能用:

正常情况下的队列

现在使用算式 r e a r + m a x S i z e rear + maxSize rear+maxSize

新的队列

这个时候玩笑就开大了,我们再使用 r e a r + m a x S i z e − f r o n t rear + maxSize - front rear+maxSizefront的话,结果就偏差到十万八千里去了

r e a r + m a x S i z e − f r o n t = 7 ( 个 有 效 元 素 , 实 际 上 只 有 3 个 ) rear + maxSize - front = 7(个有效元素,实际上只有3个) rear+maxSizefront=7(,3)

我们需要让他落在我们的队列里面,所以我们给他百分号

( r e a r + m a x S i z e − f r o n t ) % m a x S i z e = 7 % 4 = 3 (rear + maxSize - front) \% maxSize = 7 \% 4 = 3 (rear+maxSizefront)%maxSize=7%4=3

可以看到加上百分号之后我们的算式又能用了,而且刚好等于正确答案3

测试一下我们当我们的rear在front的前面的情况是否能使用

rear在front的前面

KaTeX parse error: No such environment: align* at position 8: \begin{̲a̲l̲i̲g̲n̲*̲}̲ &(rear + maxSi…

备注:因为rear是指向当前位置的下一位,所以在参加运算的时候要+1
    如图,当前尾指针的序号是1,但是此时我们需要给他+1,让他变成2再参与运算

到这里我们就结束了,最终我们得到结论如何算出一个循环队列的有效值

( r e a r + m a x S i z e − f r o n t ) % m a x S i z e (rear + maxSize - front) \% maxSize (rear+maxSizefront)%maxSize

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/m0_52475295/article/details/123977557

智能推荐

POJ 2912 Rochambeau 【种类并查集】_HungTeen的博客-程序员秘密

题目来源:http://poj.org/problem?id=2912★好久没写题了,又回到了并查集,发现并查集都没学好,写个锤子线段树翻译:有一群孩子在玩剪刀石头布游戏(真的是没看到剪刀石头布 半天不会写,一看到就明白了一二分)一个人是裁判,其他的分为三组(可能有些组没人)除了裁判可以变换着出,其他人都只能出固定的,并且同组的人是平局然后给出m组胜负结果,让你判断能不能找到裁判...

一张图理解对分、增长函数、打散、突破点、VC维_梧桐雪的博客-程序员秘密

对分(Dichotomy)、增长函数(Growth Function)、突破点(Break Point)是计算学习理论中非常重要的概念,也是机器学习的基石。可以说如果不理解计算学习理论,那就不能从根本上理解机器学习。机器学习最基本的问题是二分类和回归,在这里我们讨论的是二分类的问题。我们知道有很多二分类的模型,我们把这些模型称为分类器,常见的分类器有下面几种:正射线正间隔一维感知机二维...

关于OnPaint函数的工作原理(很详细,很实用)_foreverhuylee的博客-程序员秘密_onpaint

用了两年的VC,其实对OnPaint的工作原理一直都是一知半解。这两天心血来潮,到BBS上到处发帖询问,总算搞清楚了,现在总结一下。     对于窗口程序,一般有个特点:窗口大部分的区域保持不变,只有不分区域需要重新绘制。如果将整个窗口全部刷新的画,就做了许多不必要的工作,因而,MFC采用了一套基于无效区的处理机制。在分析无效区处理之前,我们要明白一个现实,现在的机器还不够牛,如果够牛的话

Git版本控制工具的浅谈(一)Git的安装及创建版本库_王俊凯夫人的博客-程序员秘密

一、初识Git:Git是目前世界上最先进的分布式版本控制系统(没有之一)。它的开发者就是大名鼎鼎的Linux操作系统的作者Linus Torvalds。Git被开发出来的初衷是为了更好的管理Linux内核,而现在却广泛应用于各种项目中。Git迅速成为最流行的分布式版本控制系统,尤其是2008年,GitHub网站上线了,它为开源项目免费提供Git存储,无数开源项目开始迁移至GitHub,包括

AMOS分析技术:正交验证性因子分析;模型拟合质量好,模型就一定好吗?_SPSS生活统计学的博客-程序员秘密

基础准备前面草堂君介绍了斜交验证性因子分析的操作过程以及如何将分析结果整理成论文需要的发表格式,大家可以点击下方文章链接回顾: AMOS分析技术:斜交验证性因子分析;介绍如何整理出能够放入论文的模型信效度结果今天草堂君接着斜交验证性因子分析的内容,介绍如何用Amos进行正交验证性因子分析,并对模型的拟合效果指标进行讲解,斜交验证性因子分析因为模型拟合质量良好,所以没有对拟合指标进行说明。正交验证性

map hash_map unordered_map 性能测试_程序员黄老师的博客-程序员秘密

测试环境: 测试工具:      Microsoft Visual Studio Enterprise 2015   版本 14.0.25431.01 Update 3     Microsoft .NET Framework      版本 4.6.01586测试代码: 插入操作#include <stdio.h>#include <windows.h> #inc...

随便推点

EnterCriticalSection和LeaveCriticalSection_djimon的博客-程序员秘密

通俗解释就像上厕所: 门锁了,就等着,等到别人出来了,进去锁上,然后该干什么干什么,干完了,把门打开 门没锁,就进去,锁上,然后该干什么干什么,干完了,把门打开 -------------------------------------------------- 多线程中用来确保同一时刻只有一个线程操作被保护的数据 InitializeCriticalSection(&cs);//初始化临界区 E

pycharm新建项目环境设置详解_胡祺GISer的博客-程序员秘密_pycharm创建新环境

1引言pycharm是当前最热门的python编译器。使用pycharm新建一个python项目时,需要设置项目路径、选择环境或新建环境,初学者往往很难理解这几个概念的区别和关系,就无法对项目结构的透彻理解,从而导致后续的一系列问题。本文环境管理器使用anaconda,尽量使用图文的方式来解释这几个概念和用法。2详解2.1几个概念项目(project):在python中,通常是代码文件(.py)的集合。解释器(interpreter):可以理解为,读懂你的python代码的机器,解释器的类型要与p

web日志埋点_wangqiaowqo的博客-程序员秘密

1、log4j.xml [code="java"] [/code] 2、applicationContext-servlet.xml [code="java"] [/code]3、com.youku.ddshow.cont...

极路由的正确玩法_幸运之神2055的博客-程序员秘密

楔子1家里的无线路由器的位置相当坑爹,台式机一直的信号都不怎么好,再加上坑爹的e家宽。反正家里的网络很坑爹很不科学就是了。所以我一直都在等待@暗铁家的路由器面世。等着等着极路由就做活动了,本着有活动不能放过的精神,熬着夜抢到了一只。附一下极路由的参数:CPU:AR9331 400mhzRAM:64MBROM:16MB板载一个4G的存储空间,据说官版是8G的。整体来说不算高端,也

js04 递归,数组的曾删改查_༺༽༾ཊ方觉ཏ༿༼༻的博客-程序员秘密

写代码不是从上倒下而是按照思路写的;自定义的 函数和 系统自带的函数的区别;是有没有反回值;如果函数处理的结果或数据,需要二次使用。怎么有返回值return 的作用可以将函数处理的结果或数据,返回到函数外部进行外部使用;立即函数执行一个函数中最多只能执行一次return;所有函数都有返回值 没有return 返回值是underfinder函数功能函数 有返回值但不需要...

推荐文章

热门文章

相关标签