ArrayDeque

谁借莪１个温暖的怀抱￠ 2022-06-03 04:27 120阅读 0赞

# ArrayDeque #

ArrayDeque类是双端队列的实现类。支持从头部尾部获取、删除、新增元素等操作。它是通过数组实现的。

初始的时候，默认大小为8，内存不溢出情况下可以无限扩容

/** * The minimum capacity that we'll use for a newly created deque. * Must be a power of 2. */
    private static final int MIN_INITIAL_CAPACITY = 8;

起初的时候, head指向数组0位置处，tail指向数组length - 1位置处

head–> ![1][] <–tail

在头部新增的时候

head = -1 & 7 = 7 ，在7的位置新增，以后每次新增在head - 1（6，5，4…）位置.

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

在尾部新增的时候，

tail = 8 & 7 = 0，在0的位置新增，以后每次新增在tail + 1(1,2,3…)位置新增

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

扩容的时候，（以扩容到16位例）

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 = (E[])a;
            head = 0;
            tail = n;
        }

当队列头部再插入一个元素，队列就会首位相接的时候 head - 1 == tail ，表示队列满了，需要扩容，每次扩容为之前的2倍。  
![这里写图片描述][SouthEast]  
从head到原内存数组末尾的元素放到新内存中从0开始的位置，原数组0到tail的部分跟在后面，如下图  
![这里写图片描述][SouthEast 1]  
之后再尾部新增时 tail继续 +1后移, 头部新增的时候head - 1前移。

[1]: /images/20220603/f3298da4505c41feafe46b44332bdadd.png
[SouthEast]: /images/20220603/627238cbcb1840dd99919061e18c1a3c.png
[SouthEast 1]: /images/20220603/aa48bc1bfa894a08abb7face0fe3d164.png