基于JDK11的 ArrayDeque 源码分析

川长思鸟来 2023-01-20 04:52 29阅读 0赞

# ArrayDeque源码分析 #

### 文章目录 ###

*  ArrayDeque源码分析
 *   *  一、基本介绍
     *  二、源码分析
     *   *  1. 成员属性
         *  2. 构造方法
         *  3. 入队方法
         *   *  3.1 addFirst(E e)方法
             *  3.2 addLast(E e)方法
         *  4. 扩容方法
         *  5. 出队方法
         *   *  5.1 pollFirst()方法
             *  5.2 pollLast()方法
         *  6. 栈方法
         *   *  6.1 push(E e)方法
             *  6.2 pop()方法

## 一、基本介绍 ##

*  ArrayDeque是一种以数组方式实现的双端队列，它是非线程安全的
    
     *  双端队列是一种特殊的队列，它的两端都可以进出元素，故而得名双端队列
 *  ArrayDeque使用的是循环数组，如下图所示：
    
    ![image-20210430134016869][]
    
    从上图中可以看到，head指向首端第一个有效元素，tail指向尾端第一个可以插入元素的空位；因为是循环数组，所以head不一定总等于0，tail也不一定总是比head大
 *  ArrayDeque不允许添加null值
 *  可以当作队列来使用，也可以当作栈来使用
    
     *  官方推荐使用ArrayDeque用作栈和队列
     *  做栈（Stack）时性能比 `Stack` 好，做队列（Queue）时性能比 `LinkedList` 好
 *  继承体系
    
    ![image-20210430130346974][]
    
    通过继承体系可以看到，ArrayDeque实现了Deque接口，Deque接口继承自Queue接口，它是对Queue的一种增强。

## 二、源码分析 ##

### 1. 成员属性 ###

//存储元素的数组
    transient Object[] elements;
    
    //头节点的索引值
    transient int head;
    
    //尾节点的索引值
    transient int tail;
    
    //数组的最大容量
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

### 2. 构造方法 ###

//空参构造器
    public ArrayDeque() { 
        elements = new Object[16]; //数组默认容量是16
    }
    
    //指定初始容量的构造器
    public ArrayDeque(int numElements) { 
        elements =
            new Object[(numElements < 1) ? 1 :
                       (numElements == Integer.MAX_VALUE) ? Integer.MAX_VALUE :
                       numElements + 1];
    }
    //数组容量 = 指定的容量 + 1
    //数组的最小容量是1
    
    //指定初始数据的构造器
    public ArrayDeque(Collection<? extends E> c) { 
        this(c.size());
        copyElements(c);
    }

### 3. 入队方法 ###

#### 3.1 addFirst(E e)方法 ####

`addFirst(E e)` 方法源码如下：

//从队列头部添加元素
    public void addFirst(E e) { 
    
        //不允许添加null值
        if (e == null)
            throw new NullPointerException();
    
        final Object[] es = elements;
    
        //调用dec方法找到新的头节点位置，并将e插入
        es[head = dec(head, es.length)] = e;
    
        //如果头尾指向同一个节点，就调用grow方法扩容
        if (head == tail)
            grow(1); //扩容方法之后会讲述
    }

`dec(int i, int modulus)` 方法源码如下：

有两种情况：

*  如果原头节点不是数组首元素，如下图所示：
    
    ![image-20210430135409845][]
    
    将head向前移动一位，成为新的头节点
 *  如果原头节点是数组首元素
    
    数组的最后一个元素作为头节点，第二个元素是数组首元素

//参数i表示原头节点的索引值
    //参数modulus表示原数组的长度
    static final int dec(int i, int modulus) { 
    
        //如果原头节点是数组首元素
        if (--i < 0) i = modulus - 1;
    
        //返回新的头节点索引
        return i;
    }

#### 3.2 addLast(E e)方法 ####

`addLast(E e)` 方法源码如下：

//从队列尾添加元素
    public void addLast(E e) { 
        if (e == null)
            throw new NullPointerException();
    
        final Object[] es = elements;
    
        //tail指向尾端第一个可以插入元素的空位，所以tail的索引可以直接添加元素
        es[tail] = e;
    
        //如果头尾指向同一个节点，就调用grow方法扩容
        //调用inc方法得到新的尾索引
        if (head == (tail = inc(tail, es.length)))
            grow(1);
    }

`inc(int i, int modulus)` 方法源码如下：

有两种情况：

*  如果原尾索引不是数组最后一个元素的位置，如下图所示：
    
    ![image-20210430135409845][]
    
    新尾索引 = 原尾索引 + 1
 *  如果原尾索引是数组最后一个元素的位置
    
    新尾索引是数组第一个元素的位置，即0

//参数i表示原尾索引
    //参数modulus表示原数组长度
    static final int inc(int i, int modulus) { 
    
        //如果原尾索引是数组最后一个元素的位置
        if (++i >= modulus) i = 0;
    
        //返回新尾索引
        return i;
    }

### 4. 扩容方法 ###

扩容大致思路图示：

![image-20210430154849826][]

`grow(int needed)` 方法源码如下：

//入参needed为当前添加操作所需要的空间，当只添加一个元素时为1，添加多个元素时就是多个元素的长度
    private void grow(int needed) { 
    
        final int oldCapacity = elements.length;
        int newCapacity;
    
        //如果原数组容量 < 64，新容量 = 旧容量的2倍 + 2
        //如果原数组容量 >= 64，新容量 = 旧容量的1.5倍
        int jump = (oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1);
        if (jump < needed
            || (newCapacity = (oldCapacity + jump)) - MAX_ARRAY_SIZE > 0)
            newCapacity = newCapacity(needed, jump);
    
        //将旧数组的内容拷贝到扩容后的新数组中并赋值给elements和es
        final Object[] es = elements = Arrays.copyOf(elements, newCapacity);
    
        //此时仅仅将数组容量扩大，head和tail仍指向同一个节点
    
        if (tail < head || (tail == head && es[head] != null)) { 
    
            //将旧数据复制到新的位置
            int newSpace = newCapacity - oldCapacity;
            System.arraycopy(es, head,
                             es, head + newSpace,
                             oldCapacity - head);
    
            //将旧位置的旧数据全部清空
            //head成为了新位置的首元素的位置
            for (int i = head, to = (head += newSpace); i < to; i++)
                es[i] = null;
        }
    }

### 5. 出队方法 ###

#### 5.1 pollFirst()方法 ####

`pollFirst()` 方法源码如下：

public E pollFirst() { 
        final Object[] es;
        final int h;
    
        E e = elementAt(es = elements, h = head); 
        //elementAt方法返回es[h]，即head位置的元素
    
        if (e != null) { 
            es[h] = null; //head位置的元素置为null
    
            //head要么向后移动一位，要么成为数组首元素的位置，不再赘述
            head = inc(h, es.length);
        }
    
        return e; //返回原head位置的元素
    }

#### 5.2 pollLast()方法 ####

`pollLast()` 方法源码如下：

public E pollLast() { 
        final Object[] es;
        final int t;
    
        //调用dec方法，tail要么向前移动一位，要么成为数组尾元素的位置
        E e = elementAt(es = elements, t = dec(tail, es.length));
    
        if (e != null)
            es[tail = t] = null; //tail位置的元素被赋予null值
    
        return e; //返回tail位置原来还没有被赋予null值的元素
    }

观察出队的两个方法的源码，发现出队之后没有缩容

### 6. 栈方法 ###

#### 6.1 push(E e)方法 ####

`push(E e)` 方法源码如下：

public void push(E e) { 
        addFirst(e); //调用了addFirst方法从队列头部添加元素，不再赘述
    }

#### 6.2 pop()方法 ####

`pop()` 方法源码如下：

public E pop() { 
        return removeFirst();
    }
    
    public E removeFirst() { 
        E e = pollFirst(); //调用了pollFirst方法弹出首元素，不再赘述
        if (e == null)
            throw new NoSuchElementException();
        return e;
    }

观察上述源码发现，ArrayDeque满足栈的特性，从队列头部增 / 删元素

[image-20210430134016869]: /images/20221021/401d756971064fbbbd160a14d0b5477e.png
[image-20210430130346974]: /images/20221021/57ceef927c3a4c8db267c1c6dae0e8f4.png
[image-20210430135409845]: /images/20221021/0314d547e4124a03bf9f0fa95253142a.png
[image-20210430154849826]: /images/20221021/8277b7c2b0124143be4d36e852acfebd.png