图灵JAVA互联网架构师五期内附资料文档
download链接：https://pan.baidu.com/s/1Fat1jEVOkKlqU03gLZJWBw?pwd=2thn
提取码：2thn
--来自百度网盘超级会员V5的分享
ArrayDeque深度解析
概述
ArrayDeque这个容器不知道大家在平常的工作中运用的多吗？它是一个非常强大的容器，既可以作为队列完成FIFO先进先出的功用，也具备栈的功用完成FILO先进后出的功用，那么它究竟是怎样样的呢？性能又如何？
ArrayDeque引见
ArrayDeque主要是基于数组完成的Deque(Double Ended Queue)双端队列，即双端队列，它既可以当作栈运用，也可以当作队列运用。

ArrayDeque是一个没有容量限制的双端队列，底层是基于数组完成，会自动扩容。
ArrayDeque不是线程安全的。
ArrayDeque不可以存取null元素。
当作为栈运用时，性能比Stack好；当作为队列运用时，性能比LinkedList好。

完成了Queue接口，它理论上是一个单端队列，只能操作队列的一端。
完成了Deque接口，Deque集成了Queue接口，有api可以同时操作队列的双端。
完成了Cloneable接口，说明该队列支持clone。
完成了Serializable接口，标志该接口支持序列化操作。

构造方法

方法说明ArrayDeque()构造一个初始容量为16的数组双端队列ArrayDeque(int numElements)构造一个初始容量为numElements的数组双端队列ArrayDeque(Collection<? extends E> c)构造一个初始内容未c的数组双端队列
关键方法
添加相关方法

等价方法说明add(e)addLast(e)向队列尾部添加元素offer(e)offerLast(e)向队列尾部添加元素addFirst(e)offerFirst(e)向队列头部添加元素

add前缀的方法，假设超越容量限制，添加失败，会抛出运转时异常
offer前缀的方法，比较特殊，假设超越容量限制，会返回指定值true false

队列获取元素相关方法

等价方法说明remove()removeFirst()获取并且删除队列头部元素poll()pollFirst()获取并且删除队列头部元素removeLast()pollLast()获取并且删除队列尾部

remove前缀的方法，假设容量为空，会抛出运转时异常
offer前缀的方法，假设容量为空，会返回指定值null

方法等价方法说明element()getFirst()查看队列头部元素peek()peekFirst()查看队列头部元素getLast()peekLast()查看队列尾部元素

peek前缀的方法，假设容量为空，会返回指定true，false，其他方法失败会抛出异常。

栈相关方法等价方法说明push(e)addFirst(e)向栈中添加元素pop()removeFirst()获取栈顶元素peek()peekFirst()查看栈顶元素
其他方法
说明removeFirstOccurrence(Object o)删除队列中第一次相等的元素removeLastOccurrence(Object o)删除队列中最后一个相等的元素
tips：细致操作是返回指定值还是抛出异常，建议看源码的javadoc，写的非常清楚了。
运用案例

测试队列功用

  @Test
    public void test1() {
        Deque<String> deque = new ArrayDeque<>();
        deque.add("1");
        deque.offer("2");
        deque.offerLast("3");
        System.out.println(deque);
        String poll = deque.poll();
        System.out.println(poll);
        System.out.println(deque);
    }

测试栈的功用

@Test
    public void test2() {
        Deque<String> deque = new ArrayDeque<>();
        deque.push("1");
        deque.push("2");
        deque.push("3");
        String pop = deque.pop();
        System.out.println(pop);
    }

测试存储null数据

@Test
    public void test3() {
        Deque<String> deque = new ArrayDeque<>();
        boolean offerResult = deque.offer(null);
        System.out.println(offerResult);
        System.out.println(deque);
    }

测试poll和remove的区别

@Test
    public void test4() {
        Deque<String> deque = new ArrayDeque<>();
        String poll = deque.poll();
        //取出为null
        System.out.println(poll);

        // 由于容量为空了，会抛出异常
        String remove = deque.remove();
        System.out.println(remove);
        System.out.println(deque);
    }
中心机制
完成机制
从名字可以看出ArrayDeque底层经过数组完成，为了满足可以同时在数组两端插入或删除元素的需求，该数组还必需是循环的，即循环数组，也就是说数组的任何一点都可能被看作起点或者终点。
总的来说，ArrayDeque内部它是一个动态扩展的循环数组，经过head和tail变量维护数组的开端和结尾，数组长度为2的幂次方，运用高效的位操作中止各种判别，以及对head和tail的维护。
源码解析

构造放方法ArrayDeque(int numElements)

public ArrayDeque(int numElements) {
        // 初始化数组
        allocateElements(numElements);
    }

private void allocateElements(int numElements) {
        // 初始化数组，经过calculateSize方法计算数组长度
        elements = new Object[calculateSize(numElements)];
    }
复制代码
private static int calculateSize(int numElements) {
        // 设置初始容量等于8
        int initialCapacity = MIN_INITIAL_CAPACITY;
        //  假设numElement大于等于初始容量               
        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;
    }

程序运转到第五行时，numElements >= initialCapacity成立，10>=8，则会进入到if语句内部。
程序运转到第六行时， initialCapacity = numElements，initialCapacity 设置为10，10的二进制表示方式是1010。
程序运转到第七行时， initialCapacity无符号向右移动一位，1010无符号向右移动一位是0101，1010|0101=1111，十进制表示方式是15。
程序运转到第八行时， initialCapacity无符号向右移动2位，1111无符号向右移动一位是0011，1111|0011=1111，十进制表示方式是15，不时持续下去都是15，当程序运转到第12行时，15中止加1操作，则变成16。这个时分16就是2的幂次方返回。

整体思绪是每次移动将位数最高的值变成1，从而将二进制一切位数都变成1，变成1之后得到的十进制加上1之后得到值就是2的幂次方的值。最终，数组长度永远都是是2的幂次方。