菜鸟看源码之ArrayDeque

菜鸟看源码之ArrayDeque先扯点别的:今天上海风不小,现在窗外依然是狂风呜咽,不禁让人想起山科的风。今天分析一下ArrayDeque的源码ArrayDeque的继承关系图ArrayDeque实现了Deque接口,内部使用一个可调整大小的数组来存放元素。数组没有容量限制,必要的时候数组的容量会增加。ArrayDeque不是线程安全的。不允许添加Null元素。当ArrayDeque作为一个栈来使用的时候,Ar…

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

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

先扯点别的:今天上海风不小,现在窗外依然是狂风呜咽,不禁让人想起山科的风。

今天分析一下ArrayDeque的源码

ArrayDeque的继承关系图
这里写图片描述
ArrayDeque实现了Deque接口,内部使用一个可调整大小的数组来存放元素。数组没有容量限制,必要的时候数组的容量会增加。ArrayDeque不是线程安全的。不允许添加Null元素。当ArrayDeque 作为一个栈来使用的时候,ArrayDeque 可能会比Stack 快。当ArrayDeque 作为 队列使用的时候,可能会比 LinkedList 速度要快。

看一下ArrayDeque中几个成员变量

//储存元素的数组,长度总是2的次幂,数组不允许饱和,在使用addX方法添加元素以后,如果数组饱和了,那么就会立即扩容到原来长度的两倍
transient Object[] elements;
//双端队列的头部元素的下标
transient int head;
//标志:如果一个新元素要被添加到双端队列尾部(通过 addLast(E), add(E), or push(E)),那么这个新元素在双端队列的下标就是tail
transient int tail;
//elements最小初始容量,如果构造函数指定初始容量下限小于8,那么就选择8作为初始容量
private static final int MIN_INITIAL_CAPACITY = 8;

构造函数

public ArrayDeque() {
        elements = new Object[16];
    }

//指定初始容量下限,最终初始容量是大于等于numElements并且是2的次幂的一个数,比如指定numElements=9,那么初始容量最终会是16
public ArrayDeque(int numElements) {
        allocateElements(numElements);
    }

//使用一个集合初始化队列
public ArrayDeque(Collection<? extends E> c) {
        allocateElements(c.size());
        addAll(c);
    }

我们指定队列的初始容量为8,然后来看看常用的方法

  • addFirst(E e) 把元素插入到队列的前面
public void addFirst(E e) {
        if (e == null)
            throw new NullPointerException();
        elements[head = (head - 1) & (elements.length - 1)] = e;
        if (head == tail)
            doubleCapacity();
    }

可以看到元素是不允许为null的,初始的时候headtail都是0,elements.length=8。

ArrayDeque<Integer> deque = new ArrayDeque<>(7);
for (int i = 0; i < 8; i++) {
            deque.addFirst(i);
        }

添加第一个元素,表达式head = (head - 1) & (elements.length - 1)就等价于(-1&7)=7,所以elements[7]=0
中间插一句,关于按位与(&)和按位或(|) 操作不清楚的可以看一看 原码, 反码, 补码 详解

插入以后 head=7,不等于tail,不需要扩容

添加第二个元素 ,表达式head = (head - 1) & (elements.length - 1)就等价于(6&7)=6,所以elements[6]=1。当我们添加完第8个元素时,
elements=[7,6,5,4,3,2,1,0],这时,head=0,head=tail,这时候需要扩容
doubleCapacity(),这个方法的作用就是把elements长度增加两倍,然后使用System.arraycopy()方法重新放置元素,我们在后面会进行详细分析。

  • addLast(E e) 把元素插入到队列的尾部
public void addLast(E e) {
        if (e == null)
            throw new NullPointerException();
        elements[tail] = e;
        if ( (tail = (tail + 1) & (elements.length - 1)) == head)
            doubleCapacity();
    }
ArrayDeque<Integer> deque = new ArrayDeque<>(7);
for (int i = 0; i < 8; i++) {
            deque.addLast(i);
        }

这个方法和addFirst(E e)正好是相反的,添加完8个元素以后,elements=[0,1,2,3,4,5,6,7]

  • offerFirst(E e) 内部调用addFirst(e)方法实现,不再赘述
public boolean offerFirst(E e) {
        addFirst(e);
        return true;
    }
  • offerLast(E e) 内部调用addLast(e)方法实现,不再赘述
public boolean offerLast(E e) {
        addLast(e);
        return true;
    }
  • pollFirst() 查询第一个元素
public E pollFirst() {
        int h = head;
        @SuppressWarnings("unchecked")
        E result = (E) elements[h];
        // Element is null if deque empty
        if (result == null)
            return null;
        elements[h] = null;     // Must null out slot
        head = (h + 1) & (elements.length - 1);
        return result;
    }

当队列为空的时候,返回null。不为空时,删除并返回head下标上的元素,然后把head向后移动一个位置。
* pollLast() 查询最后一个元素

public E pollLast() {
        int t = (tail - 1) & (elements.length - 1);
        @SuppressWarnings("unchecked")
        E result = (E) elements[t];
        if (result == null)
            return null;
        elements[t] = null;
        tail = t;
        return result;
    }

当队列为空的时候,返回null。不为空时,删除并返回最后一个元素,然后把tail向前移动一个位置。

  • removeFirst() 内部调用pollFirst(),如果元素为null,则抛出异常
public E removeFirst() {
        E x = pollFirst();
        if (x == null)
            throw new NoSuchElementException();
        return x;
    }
  • removeLast() 内部调用pollLast(),如果元素为null,则抛出异常
public E removeLast() {
        E x = pollLast();
        if (x == null)
            throw new NoSuchElementException();
        return x;
    }

下面几个方法比较简单一起说了

//返回队列第一个元素,但是不删除,如果为null,怎抛出异常
public E getFirst() {
        @SuppressWarnings("unchecked")
        E result = (E) elements[head];
        if (result == null)
            throw new NoSuchElementException();
        return result;
    }

//返回队列最后一个元素,但是不删除,如果为null,怎抛出异常
    public E getLast() {
        @SuppressWarnings("unchecked")
        E result = (E) elements[(tail - 1) & (elements.length - 1)];
        if (result == null)
            throw new NoSuchElementException();
        return result;
    }
//返回队列第一个元素,但是不删除,返回值可以为null
    @SuppressWarnings("unchecked")
    public E peekFirst() {
        // elements[head] is null if deque empty
        return (E) elements[head];
    }
//返回队列最后一个元素,但是不删除,返回值可以为null
    @SuppressWarnings("unchecked")
    public E peekLast() {
        return (E) elements[(tail - 1) & (elements.length - 1)];
    }
  • removeFirstOccurrence(Object o) 删除队列中第一个和指定元素相等的元素,从head到tail遍历。如果指定元素为null,或者删除失败返回false,删除成功返回true。
public boolean removeFirstOccurrence(Object o) {
        if (o == null)
            return false;
        int mask = elements.length - 1;
        int i = head;
        Object x;
        while ( (x = elements[i]) != null) {
            if (o.equals(x)) {
                //调用delete删除,delete方法通过移动elelemts中的元素,来覆盖要删除位置上的元素,并对移动元素做了相关优化,并相应的改变head和tail
                delete(i);
                return true;
            }
            i = (i + 1) & mask;
        }
        return false;
    }
  • removeLastOccurrence(Object o) 删除队列中最后一个和指定元素相等的元素
public boolean removeLastOccurrence(Object o) {
        if (o == null)
            return false;
        int mask = elements.length - 1;
        int i = (tail - 1) & mask;
        Object x;
        while ( (x = elements[i]) != null) {
            if (o.equals(x)) {
                delete(i);
                return true;
            }
            i = (i - 1) & mask;
        }
        return false;
    }

*分析一下 doubleCapacity() 增加elements容量为原来的两倍,重新放置元素

 private void doubleCapacity() {
        assert head == tail;
        int p = head;
        int n = elements.length;
        int r = n - p; // number of elements to the right of p
        int newCapacity = n << 1;
        if (newCapacity < 0)
            throw new IllegalStateException("Sorry, deque too big");
        Object[] a = new Object[newCapacity];
        System.arraycopy(elements, p, a, 0, r);
        System.arraycopy(elements, 0, a, r, p);
        elements = a;
        head = 0;
        tail = n;
    }

这个方法中为什么System.arraycopy()方法为什么要调用两次呢,下面来分析一下。
首先这个方法调用的地方有两个,addFirst()和addLast()

第一种情况:只使用addFirst()方法添加元素,当我们添加完了第8个元素,此时elements=[7,6,5,4,3,2,1,0],需要进行扩容了

此时
head = tail=0;
p=0;
n=8;
r=8;
首先把数组容量增加两倍,然后
System.arraycopy(elements, p, a, 0, r);会把elements中的元素从下标p=0拷贝到a中,一共拷贝r=8个元素,a从下标为0开始放置元素

//第二次拷贝因为p=0,所以并不会改变a。
System.arraycopy(elements, 0, a, r, p);
最后让elements指向a。拷贝完成后 elements=[7,6,5,4,3,2,1,0,null,null,null,null,null,null,null,null],head=0,tail=8;

再用addFirst()方法添加一个元素8,结果elements=[7,6,5,4,3,2,1,0,null,null,null,null,null,null,null,8]

再用addFirst()方法添加一个元素9,结果elements=[7,6,5,4,3,2,1,0,null,null,null,null,null,null,9,8]

当我们继续添加元素elements=[7,6,5,4,3,2,1,0,15,14,13,12,11,10,9,8],此时数组满了又需要扩容了
此时
head == tail=8;
p=8;
n=16;
r=8;
首先把数组容量增加两倍,然后
System.arraycopy(elements, p, a, 0, r);会把elements中的元素从下标p=8拷贝到a中,一共拷贝r=8个元素,a从下标为0开始放置元素
拷贝完成后a=[15,14,13,12,11,10,9,8,...]
//第二次拷贝p=8,会把elements中的元素从下标0拷贝到a中,一共拷贝p=8个元素,a从下标r=8开始放置元素
System.arraycopy(elements, 0, a, r, p);
最后让elements指向a。拷贝完成后 a=[15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,...],head=0,tail=16;

插一句,到这里隐隐感觉到写这个代码的人真是厉害,佩服!

第二种情况:只使用addLast()方法添加元素,当我们添加完了第8个元素,此时elements=[0,1,2,3,4,5,6,7],需要进行扩容了
此时
head = tail=0;
p=0;
n=8;
r=8;
首先把数组容量增加两倍,然后
System.arraycopy(elements, p, a, 0, r);会把elements中的元素从下标p=0拷贝到a中,一共拷贝r=8个元素,a从下标为0开始放置元素
//第二次拷贝因为p=0,所以并不会改变a。
System.arraycopy(elements, 0, a, r, p);
最后让elements指向a。拷贝完成后 elements=[0,1,2,3,4,5,6,7,null,null,null,null,null,null,null,null],head=0,tail=8;
再用addLast()方法添加一个元素8,结果elements=[0,1,2,3,4,5,6,7,8,null,null,null,null,null,null,null]
再用addLast()方法添加个一个元素9,结果elements=[0,1,2,3,4,5,6,7,8,9,null,null,null,null,null,null]

当我们继续添加元素elements=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15],此时数组满了又需要扩容了
此时
head = tail=0;
p=0;
n=16;
r=16;
首先把数组容量增加两倍,然后
System.arraycopy(elements, p, a, 0, r);会把elements中的元素从下标p=0拷贝到a中,一共拷贝r=16个元素,a从下标为0开始放置元素
//第二次拷贝因为p=0,所以并不会改变a。
System.arraycopy(elements, 0, a, r, p);
最后让elements指向a。拷贝完成后 elements=[0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,...],head=0,tail=16;

插一句,到这里深深感觉到写这个代码的人真是厉害,佩服!

再分析一种情况
使用addFirst()方法添加元素,当我们添加完了第7个元素,此时elements=[null,6,5,4,3,2,1,0],然后使用addLast()方法添加一个元素7,
此时elements=[7,6,5,4,3,2,1,0]然后数组满了需要扩容
此时
head = tail=1;
p=1;
n=8;
r=7;
数组容量增加两倍
System.arraycopy(elements, p, a, 0, r);会把elements中的元素从下标p=1拷贝到a中,一共拷贝r=7个元素,a从下标为0开始放置元素,拷贝
完成后a=[6,5,4,3,2,1,0,...]
第二次拷贝
System.arraycopy(elements, 0, a, r, p);会把elements中的元素从下标0拷贝到a中,一共拷贝p=1个元素,a从下标为r=7开始放置元素,拷贝完成后
a=[6,5,4,3,2,1,0,7,...]此时elements=[6,5,4,3,2,1,0,7,...],head = 0``tail=8
如果此时继续用然后使用addLast()添加8个元素element=[6,5,4,3,2,1,0,7,8,9,10,11,12,13,14,15],此时数组饱和,扩容
head = tail=0;
p=0;
n=16;
r=16;
数组容量增加两倍
System.arraycopy(elements, p, a, 0, r);会把elements中的元素从下标p=0拷贝到a中,一共拷贝r=16个元素,a从下标为0开始放置元素,拷贝
完成后a=[6,5,4,3,2,1,0,7,8,9,10,11,12,13,14,15,...]
第二次拷贝p=0,a不会改变。
最后elements=[6,5,4,3,2,1,0,7,8,9,10,11,12,13,14,15,...],head = 0``tail=16

结尾:今天是美好的一天,明天也将会使美好的一天。

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

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

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

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

(0)


相关推荐

  • 推荐|Python开源自动化运维平台[通俗易懂]

    推荐|Python开源自动化运维平台[通俗易懂]Python开源自动化运维平台介绍:开源免费,轻量级,适用于中小企业的轻量自动化运维管理平台Spug仓库地址:https://github.com/openspug/spug特性:批量执行:命令可以在线批量执行在线终端:主机支持浏览器在线终端登录任务计划:灵活的任务计划发布部署:支持自定义发布流程配置中心:支持KV、文本、json等格式的配置监控中心:支持站点、端口、进程、自定义等监控报警中心:支持短信、邮件、钉钉、微信等报警方式优雅美观:基于AntDesign

  • Python玩转emoji表情 一行代码的事儿!

    Python玩转emoji表情 一行代码的事儿!Python可以实现emoji表情一行代码的事儿!有时候在代码中加入一些有趣的操作可以使得友好度UP好几个LEVEL,正好了解到Python支持emoji表情的输出,实现方式相当简单。

  • (三)hadoop系列之__CRT(SecureCRTPortable)的使用

    (三)hadoop系列之__CRT(SecureCRTPortable)的使用  SecureCRTPortable属于终端仿真程序,支持SSH(查看此处http://blog.csdn.net/macrossdzh/article/details/5691924)协议。利用CRT可以很方便操作虚拟机终端。进入正题……1.首先,下载SecureCRTPortable软件。2.直接执行SecureCRTPortable.exe文件即可。3.执…

  • Python 实现搭建本地IP代理池

    Python 实现搭建本地IP代理池本文仅供学习交流使用,如侵立删!联系方式及demo下载见文末爬取:66ip免费代理defget_66ip(self):”””抓取66ip免费代理:return:”””forindexinrange(1,self.sixsix_url_range):count=0province=”url=’http

  • Linux(centos7)离现安装kubernetes1.19.2和docker——组件部分

    Linux(centos7)离现安装kubernetes1.19.2和docker——组件部分

  • Nmap命令详解及常用命令总结[通俗易懂]

    Nmap命令详解及常用命令总结[通俗易懂]Nmap学习文章目录Nmap学习0Nmap介绍1Nmap命令详解1.1Nmap命令help详解(内附中文翻译)1.2Nmap命令思维导图2Nmap常见使用场景以及相关命令2.1Nmap常用扫描命令2.1.1扫描固定端口,以sqlServer为例2.1.2获取远程主机的系统类型及开放端口2.1.3列出开放了指定端口的主机列表2.1.4在网络寻找所有在线主机2.1.5…

发表回复

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

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