【JDK源码】ArrayDeque源码分析

ゝ一世哀愁。 2023-10-01 11:37 11阅读 0赞

#### 文章目录 ####

*  ArrayDeque源码分析
 *   *  1.简介
     *  2.主要属性
     *  3.主要构造方法
     *  4.入队
     *  5.扩容
     *  6.出队
     *  7.作为栈
     *  8.总结

## ArrayDeque源码分析 ##

### 1.简介 ###

双端队列是一种特殊的队列，它的两端都可以进出元素，故而得名双端队列。

`ArrayDeque`**是一种以数组方式实现的双端队列，它是非线程安全的。**

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5RVpu15X-1641083950338)(ArrayDeque源码分析.assets/image-20211229132514256.png)\]][img-5RVpu15X-1641083950338_ArrayDeque_.assets_image-20211229132514256.png]

*  通过继承体系可以看，ArrayDeque实现了`Deque`接口，Deque接口继承自`Queue`接口，它是对Queue的一种增强。
 *  从继承体系可以看出，ArrayDeque实现了`Cloneable`和`Serializable`接口，说明其可以被克隆，也可以被序列化。

### 2.主要属性 ###

//存储元素的数组
    transient Object[] elements; // non-private to simplify nested class access
    
    //队列头位置
    transient int head;
    
    //队列尾位置
    transient int tail;
    
    //最小初始容量
    private static final int MIN_INITIAL_CAPACITY = 8;

从属性我们可以看到，**ArrayDeque使用数组存储元素，并使用头尾指针标识队列的头和尾，其最小容量是`8`。**

### 3.主要构造方法 ###

//默认无参构造方法，初始容量为16
    public ArrayDeque() {
        
        elements = new Object[16];
    }
    
    //指定元素个数初始化
    public ArrayDeque(int numElements) {
        
        allocateElements(numElements);
    }
    
    //传入集合c，将其中的元素初始化到数组
    public ArrayDeque(Collection<? extends E> c) {
        
        allocateElements(c.size());
        addAll(c);
    }
    //传入指定大小，初始化数组
    private void allocateElements(int numElements) {
        
        elements = new Object[calculateSize(numElements)];
    }
    // 计算容量，这段代码的逻辑是算出大于numElements的最接近的2的n次方且不小于8
    // 比如，3算出来是8，9算出来是16，33算出来是64
    private static int calculateSize(int numElements) {
        
        int initialCapacity = MIN_INITIAL_CAPACITY;
        // Find the best power of two to hold elements.
        // Tests "<=" because arrays aren't kept full.
        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;
    }

通过构造方法，我们知道**默认初始容量是`16`，最小容量是`8`。**

### 4.入队 ###

入队有很多方法，我们这里主要分析两个，`addFirst(e)`和`addLast(e)`。

**队头入队**

//从队列头入队
    public void addFirst(E e) {
        
        //如果为null，直接抛异常
        if (e == null)
            throw new NullPointerException();
        //将head指针减1并与数组长度减1取模
        //目的是防止数组到头了边界溢出
        //如果到头了就从尾部再向前
        //相当于循环利用数组
        //栗子：head为0，数组长度为8.(-1&7)=(-1%8)=7
        elements[head = (head - 1) & (elements.length - 1)] = e;
        if (head == tail)
            //如果头尾在一起了，就触发扩容
            doubleCapacity();
    }

**队尾入队**

//从队列尾入队
    public void addLast(E e) {
        
        //不允许null元素，否则抛出异常
        if (e == null)
            throw new NullPointerException();
        //在尾指针的位置放入元素
        //可以看到tail指针指向的是队列的最后一个元素的下一个位置
        elements[tail] = e;
        //tail指针+1,如果到数组尾了就从头开始
        if ((tail = (tail + 1) & (elements.length - 1)) == head)
            doubleCapacity();
    }

整个流程：

1.  入队有两种方式，从队列头或者从队列尾
2.  如果容量不够了，**直接扩大为两倍**
3.  通过取模的方式让头尾指针在数组范围内循环
4.  `x & (len - 1) = x % len`，使用&的方式更快

### 5.扩容 ###

//两倍扩容
    private void doubleCapacity() {
        
        assert head == tail;
        //头指针的位置
        int p = head;
        //旧数组的长度
        int n = elements.length;
        // head右边元素的个数
        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];
        //将旧数组head之后的元素拷贝到新数组中
        System.arraycopy(elements, p, a, 0, r);
        //将就数组小标0到head之间的元素拷贝到新数组中
        System.arraycopy(elements, 0, a, r, p);
        //赋值给新数组
        elements = a;
        //head指向0，tail指向旧数组长度表示的位置
        head = 0;
        tail = n;
    }

下图为一个栗子，可做参考：

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4wJjh42V-1641083950341)(ArrayDeque源码分析.assets/640)\]][img-4wJjh42V-1641083950341_ArrayDeque_.assets_640]

### 6.出队 ###

出队同样有很多方法，我们主要看两个，`pollFirst()`和`pollLast()`。

**队头出队**

//从队列头出队
    public E pollFirst() {
        
        int h = head;
        @SuppressWarnings("unchecked")
        //取队列头元素
        E result = (E) elements[h];
        // 如果队列为空，就返回null
        if (result == null)
            return null;
        //将队列头置为空
        elements[h] = null;     // Must null out slot
        //队列头指针想右移动一位
        head = (h + 1) & (elements.length - 1);
        //返回取到的元素
        return result;
    }

**队尾出队**

//从队列尾出队
    public E pollLast() {
        
        //tail的上一个位置是最后一个元素
        //尾指针左移一位
        int t = (tail - 1) & (elements.length - 1);
        @SuppressWarnings("unchecked")
        //取当前尾指针处元素
        E result = (E) elements[t];
        //如果队列为空返回null
        if (result == null)
            return null;
        //将当前尾指针处置为空
        elements[t] = null;
        //tail指向新的尾指针处
        tail = t;
        //返回取得的元素
        return result;
    }

**总结**

1.  出队有两种方式，从队列头或者从队列尾
2.  通过取模的方式让头尾指针在数组范围内循环
3.  出队之后没有缩容

### 7.作为栈 ###

`Deque`可以直接作为栈来使用，`ArrayDeque`的实现。

**进栈**

public void push(E e) {
        addFirst(e);
    }

**出栈**

public E pop() {
        
        return removeFirst();
    }

### 8.总结 ###

1.  ArrayDeque是采用数组方式实现的**双端队列**
2.  ArrayDeque的出队入队是通过头尾指针循环利用**数组实现的**
3.  ArrayDeque容量不足时是会扩容的，**每次扩容容量增加一倍**
4.  ArrayDeque**可以直接作为栈使用**

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBATEwuTEVCUk9O_size_20_color_FFFFFF_t_70_g_se_x_16]

[img-5RVpu15X-1641083950338_ArrayDeque_.assets_image-20211229132514256.png]: https://img-blog.csdnimg.cn/e81d97a69227403b922e52219066250e.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBATEwuTEVCUk9O,size_20,color_FFFFFF,t_70,g_se,x_16
[img-4wJjh42V-1641083950341_ArrayDeque_.assets_640]: https://img-blog.csdnimg.cn/083cac9a2025412dbb76496f2ee07036.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBATEwuTEVCUk9O,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBATEwuTEVCUk9O_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/a417ccd3bbb549478c200161c481082c.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBATEwuTEVCUk9O,size_20,color_FFFFFF,t_70,g_se,x_16