arraydeque方法_双端队列如何理解

arraydeque方法_双端队列如何理解ArrayDeque双端队列完全解析重点:底层通过循环数组实现俩个重要属性headtail不能添加null值,不然会报空指针每次扩容都是2的n次方可以实现普通队列先进先出排序,也可以实现栈先进后出的排序特别留意,它里面通过二进制方式判断数组是否已满(tail=(tail+1)&(elements.length-1))==head注意操作插入…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

ArrayDeque双端队列完全解析

重点:

  • 底层通过循环数组实现 俩个重要属性 head tail
  • 不能添加null值,不然会报空指针
  • 每次扩容都是2的n次方
  • 可以实现普通队列先进先出排序,也可以实现栈先进后出的排序
  • 特别留意,它里面通过二进制方式判断数组是否已满
    (tail = (tail + 1) & (elements.length – 1)) == head
  • 注意操作插入和移除时,有Throws exception 和 return Special value 俩种情况

循环数组概念

我们知道,ArrayDeque是通过数组实现队列功能 的;而且具有对数组头尾双端添加和移除对象的功能,但如果数组不能实现循环功能,会出现以下情况

图一

图一

在构建一个ArrayDeque对象时,会初始化head和tail的值为0.当有对象加入数组时,tail的值加1,当有对象出列时,head的值会加1.
而head值 == tail值 ,可以帮我们判断数组是已经满。

如果数组容量固定的情况下,从尾追加数据,从头出列数据,会出现实际数组有空的单元,但却tail会超过数组容量的情况,这种现象称为“假溢出” ;但往往,不可能是一种容量固定的数组,一般会有实现自动扩容的方法,但即便可以扩容,按照上面的逻辑,数组容量不断扩大,tail值一直向后,但从头出列的数据越来起多,前面空的内存单造成的浪费更是不能忽略了。

再往下想,不是说Deque接口实现了头和尾添加和删除数据的功能吗?那它不是可以从头添加数据,不就可以利用到前面已经出列的空的单元吗?
但如果就是单纯的就是在往后追加数据呢?那前面空出的内存单元,就这样舍弃掉?简直“暴殄天物”。

所以,为了解决数组单元浪费的问题,就产生了循环数组。且看图
图二

图二

从上图可知,当tail值超过数组索引后,就回到了索引为0的地方,实现了内存单元循环利用。
你可以想象成,数组尾和头尾首相连,形成逻辑上的”环形“。
但同时,你要清楚,上图中的例子,是头部已经有出列,有空的单元时,tail值回到的索引0的地方,但如果索引为0的地方有值时,此时,想要实现新对象的保存,也只能重新去扩容了。
可知,循环数组可以实现有限数组容量的的高效利用,但新值不会覆盖原值。

讲到这里,如果有细心猿会现,我图一在初始化时,tail和head都是对应索引为0的数组,我说数据从尾部追加,那应该调用的是addlast方法,但上图添加数据分明是从索引0开始追加的,是按照数组顺序的,和实际情况不相符啊。而且,如果从后面追加数据的话,你的tail值怎么移动?

正如猿发现的问题一样,确实,我上面的例子不够严谨,请看下图

图三

图三

我先调用addLast方法,把1加入数组,1位于数组尾部
我再调用addLast方法,把2加入数组,2替换1的位置,追加尾部,1向前存储一个单元
我先调用addFirst方法,把A加入数组,A位于数组头部
我再调用addFirst方法,把B加入数组,B替换A的位置,放置数组头部,A向后存储一个单元

所以,严格来说,无论是addLast 还是addFirst方法,都不按照数组顺序加入数据的(按照索引顺序);而是根据头尾,新追加数据会占用头尾位置,原来头尾位置的数据后移或前移 ;

那么,tail值和head值怎么移动呢?
其实,每增加一个对象,tail值就会+1 ,每移除一个对象,head值+1 ;
并非如图一那样,head和tail值都要从左到右移动的那种样式。
tail值和head值可以理作为一个标的,最后,通过tail和head值来确定数组是否已满

那么这个标的是怎么实现判断数组已满的呢?


循环数组已满判断

jdk源码里面,通过 (tail = (tail + 1) & (elements.length – 1)) == head 来判断数组已满 ,并且要求数组每次扩容的长度为2的n次方来使得上面的等式有效;

这个怎么理解呢?

在这里插入图片描述

注意,

  • 上图选取是长度为8的数组
  • index[0,7]
  • 上图中tail的值已为公式tail=(tail+1)中+1后的tail值

我们来看一个源码

   public void addLast(E e) {
        if (e == null)
            throw new NullPointerException();
        elements[tail] = e;
        if ( (tail = (tail + 1) & (elements.length - 1)) == head)
            doubleCapacity();
    }  

在这个方法中,tail值的+1是放在if判断中的,并没有单独写tail++ 这样的语句,而不管if条件是否成立,tail的值都是会+1,而我上图中的标注的tail值是已+1过的。

情况一,数组未出列,往数组里添加8个元素后,tail值每次+1,最后值为8
代入公式中(tail = (tail + 1) & (elements.length – 1)) == head
为(8 & 7)==0 转为二进制为(1000 & 111 )==0 000 结果返回true.

情况二,数组出列2个,往数里面加了10个数据,tail值变为10.代入公式为 (10 & 7)==2 转为二进制为(1010 & 111)=10 ,返回true.

可见,上述公式是在数组为2的n次长度时,是成立的。但如果是非2的n次方容量呢,还成立吗?

举例
在这里插入图片描述

代入公式为 (7 & 6)==0 转为二进制为 ((111 & 110)=110 )≠ 000

当然上面的例子你也可以再多找几个,你会发现真的只有当数组容量为2的n次方时,jdk提供的等式是成立的。

另外,ArrayDeque提供了可以指定数组容量的构造器,那我输入非2的n次方数值,内部会发生什么?


private void allocateElements(int numElements) {
        elements = new Object[calculateSize(numElements)];
    }   

private static int calculateSize(int numElements) {
        int initialCapacity = MIN_INITIAL_CAPACITY;
     
        if (numElements >= initialCapacity) {
            initialCapacity = numElements;
            initialCapacity |= (initialCapacity >>>  1);
            initialCapacity |= (initialCapacity >>>  2);
            initialCapacity |= (initialCapacity >>>  4);
            initialCapacity |= (initialCapacity >>>  8);
            initialCapacity |= (initialCapacity >>> 16);
            initialCapacity++;

            if (initialCapacity < 0)   // Too many elements, must back off
                initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
        }
        return initialCapacity;
    }  

它的内部是通过位移动算符 >>> 和 位运算符 | 实现的
| = 这样的符号表示右边的值和左边的值 通过 位运算符 | 操作后赋值给左边的值。
通过一系列的运算符操作,随机输入的数值,最后转换成比原数值大,且和它最近的2的n次方数值。

费话不说, 我们来举例 传入 12

在这里插入图片描述

真是妙哉!


ArrayDeque 既可实现普通队列 FIFO 先进先出,也可实现栈的先进后出功能

其实也好理解,因为ArrayDeque实现了双端的操作 所以使得这一切都成为了可能

  • 先进先出
    addFirst() 方法 配合pollLast() 方法
    addLast() 方法 配合 pollFirst()方法

  • 先进后出(栈)
    addFirst() 方法配合 pollFirst()方法
    addLast()方法配合pollLast()方法


Throws exception 和 return Special value

特别注意,在操作数组时,有些方法遇问题,会直接抛出异常;有些方法,会反回Special value 也就是null值

在这里插入图片描述

更多简析思路,可参考以下博文

Java 容器源码分析之 Deque 与 ArrayDeque

Java进阶–ArrayDeque双端队列完全解析
End!


在这里插入图片描述

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/191274.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 激光导航和slam导航区别_激光导航和视觉导航的区别

    激光导航和slam导航区别_激光导航和视觉导航的区别激光SLAM基本原理基本原理

  • android Glide 4.0图片加载失败

    android Glide 4.0图片加载失败项目中查看大图,并可以拖拽缩放,但是在加载图片等时候有些图片不能加载出来,报了一个错误:classcom.bumptech.glide.load.engine.GlideException:Failedtoloadresource原因:DragPhotoView图片在加载的时候进行了缩放,导致图片失帧,不能加载,解决方法:必须是加载原图//加载原图的操作RequestOpt…

  • java responsebody_SpringBoot ResponseBody返回值处理的实现「建议收藏」

    java responsebody_SpringBoot ResponseBody返回值处理的实现「建议收藏」1.springbootresponsebody返回值中null值处理@postmapping(path=”/test”,produces=mediatype.application_json_value)publicobjecttest(){jsonobjectjsonobject=newjsonobject();jsonobject.put(“test”,”tes…

  • vue中解决跨域问题_js跨域解决方案

    vue中解决跨域问题_js跨域解决方案如果你是一个Web前端工程师,那么跨域这个问题肯定是绕不开的!1.创建vue.config.js设置devServer属性module.exports={devServer:{//webpack-dev-server配置host:’localhost’,port:8080,//配置本项目运行端口proxy:{…

  • 02-Epicor二次开发常用代码

    02-Epicor二次开发常用代码二次开发,俗称客制。是程序员根据需求,进入开发模式对Epicor进行代码修改。1、获取到的完整的SQL,可以将SQL语句弹出来2、每个公司的代码是一样的,不一样请清理系统缓存,并退出系统重新进入3、隐藏一列4、关于界面居中问题5、测试跟正式的水晶报表文件都在192.168.100.250的EpicorData\CustomReports文件夹中6、关于报表位置不够问题7、将DataView的数据转化为xml的文件,用于更新水晶报表8、vb.net中换行…

  • Linux怎么卸载jdk_下载jdk的步骤

    Linux怎么卸载jdk_下载jdk的步骤一、手动安装jdk卸载1、先输入java-version查看是否安装了jdkjava-version2、如果安装了,检查下安装的路径whichjava(查看JDK的安装路径)whichjava3、卸载rm-rfJDK地址(卸载JDK)rm-rf/usr/java/jdk/jdk1.8.0_172/4、vim命令编辑文件profilevim/etc/profile将配置文件注解或删除#setjavaevironment#exportJAVA_HOME

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号