Java之ArrayDeque

梦里梦外; 2024-04-18 17:22 64阅读 0赞

### 文章目录 ###

*   *   *  一、底层数据结构
         *  二、方法思维导图
         *   *  三、 部分方法的源代码
             *  1. add
             *  2. remove
             *  3. size()

### 一、底层数据结构 ###

// 构造方法
    public ArrayDeque() {
            elements = (E[]) new Object[16];
        }

该队列是基于**数组**实现的.

### 二、方法思维导图 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NzZG5MZXJhbmVy_size_16_color_FFFFFF_t_70]  
从方法来看, ArrayDeque既可以用作**队列**(元素添加至尾部)、也可以作为**栈**(元素添加至头部).

#### 三、 部分方法的源代码 ####

#### 1. add ####

public boolean add(E e) {
            addLast(e);
            return true;
        }

public void addLast(E e) {
            if (e == null)
                throw new NullPointerException();
            elements[tail] = e;
            if ( (tail = (tail + 1) & (elements.length - 1)) == head) // 判断下一个索引是否超出数组范围
                doubleCapacity(); // 扩容
        }

为什么`(tail = (tail + 1) & (elements.length - 1)) == head`**能够判断索引是否超出范围?**

**Firstly**, 首先记住  2 n 2^n 2n & ( 2 n 2^n 2n\-1) == 0 . 比如4&3==0, 16&15==0.And 若转为二进制则分别为100&011、10000&01111

**Secondly**, 构造方法**保证了无论如何内部数组的长度总是 2 n 2^n 2n**, **且长度必定>=8**

**Lastly, 举个栗子.** 例如, 长度为16的数组, 最后一个元素的索引为(length - 1)即tail=15, 套用上面的代码`16 = (15 + 1) & 16 -1`, 即`16 & 15`.Get it?

// 构造方法一
    public ArrayDeque() {
           elements = (E[]) new Object[16]; // 长度为2^4
        }

// 其它构造方法调用
    private void allocateElements(int numElements) {
            int initialCapacity = MIN_INITIAL_CAPACITY; // 8
            // Find the best power of two to hold elements.
            // Tests "<=" because arrays aren't kept full.
            if (numElements >= initialCapacity) {  // 长度必定大于等于8
                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   // Integer.MAX_VALUE + 1
                    initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
            }
            elements = (E[]) new Object[initialCapacity];
        }

#### 2. remove ####

虽然ArrayDeque与ArrayList都是基于数组实现的, 但是ArrayDeque并**不提供根据索引访问数据**, 也就是说不能像ArrayList一样根据索引访问数据`例如：get(i)`, 因为ArrayDeque没有实现**RandomAccess**接口.

// 关键代码
    public E pollFirst() {
            int h = head;
            E result = 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;
        }

它虽然基于数组实现, 却使用2个变量来记录队列的头部和尾部的索引, 头部索引并非一定为0.  
`private transient int head // 记录首个元素所在索引`  
`private transient int tail //记录下一个元素添加时的索引`

还有一点,分清`数组长度(elements.length)`与`集合大小(size())`的区别.

#### 3. size() ####

public int size() {
       return (tail - head) & (elements.length - 1);
     }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NzZG5MZXJhbmVy_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190910183357721.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NzZG5MZXJhbmVy,size_16,color_FFFFFF,t_70