download：PyTorch入门到进阶 实战计算机视觉与自然语言解决我的项目内附材料文档

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的幂次方。