1、Deque-接口包含方法-简介

public interface Deque<E> extends Queue<E> {
    // 添加元素到队列头
    void addFirst(E e);
    // 添加元素到队列尾
    void addLast(E e);
    // 添加元素到队列头
    boolean offerFirst(E e);
    // 添加元素到队列尾
    boolean offerLast(E e);
    // 从队列头移除元素
    E removeFirst();
    // 从队列尾移除元素
    E removeLast();
    // 从队列头移除元素
    E pollFirst();
    // 从队列尾移除元素
    E pollLast();
    // 查看队列头元素
    E getFirst();
    // 查看队列尾元素
    E getLast();
    // 查看队列头元素
    E peekFirst();
    // 查看队列尾元素
    E peekLast();
    // 从队列头向后遍历移除指定元素
    boolean removeFirstOccurrence(Object o);
    // 从队列尾向前遍历移除指定元素
    boolean removeLastOccurrence(Object o);
    // *** 队列中的方法 ***
    // 添加元素，等于addLast(e)
    boolean add(E e);
     // 添加元素，等于offerLast(e)
    boolean offer(E e);
    // 移除元素，等于removeFirst()
    E remove();
    // 移除元素，等于pollFirst()
    E poll();
    // 查看元素，等于getFirst()
    E element();
    // 查看元素，等于peekFirst()
    E peek();
    // *** 栈方法 ***
    // 入栈，等于addFirst(e)
    void push(E e);
    // 出栈，等于removeFirst()
    E pop();
    // *** Collection中的方法 ***
    // 删除指定元素，等于removeFirstOccurrence(o)
    boolean remove(Object o);
    // 检查是否包含某个元素
    boolean contains(Object o);
    // 元素个数
    public int size();
    // 迭代器
    Iterator<E> iterator();
    // 反向迭代器
    Iterator<E> descendingIterator();
}

2、ArrayDeque-底层数据结构

1、ArrayDeque底层使用了数组来存储数据，同时用两个int值head和tail来表示头部和尾部。
    //用数组存储元素
    transient Object[] elements; // non-private to simplify nested class access
    //头部元素的索引
    transient int head;
    //尾部元素的下一位，即下一个将要被加入的元素的索引[!!!]
    transient int tail;
    //最小容量，必须为2的幂次方
    private static final int MIN_INITIAL_CAPACITY = 8;

3、ArrayDeque-构造方法

1、ArrayDeque有三个构造函数来初始化，除了无参的构造函数使用了默认容量，其它两个构造函数会通过allocateElements来计算初始容量。
2、源码:
    public ArrayDeque() {  
        elements = (E[]) new Object[16]; // 默认的数组长度大小  
    }  
    public ArrayDeque(int numElements) {  
        allocateElements(numElements); // 需要的数组长度大小，指定元素个数初始化  
    }  
    public ArrayDeque(Collection<? extends E> c) {  
        allocateElements(c.size()); // 根据集合来分配数组大小  
        addAll(c); // 把集合中元素放到数组中  
    }

4、ArrayDeque-分配数组大小

1、ArrayDeque 对数组的大小(即队列的容量)有特殊的要求，必须是 2^n[!!!]。
2、源码：
    //初始化数组,计算出大于var1的最接近的2的n次方且大于等于8
    //比如：3-->8、9-->16
    //对于一个小于2^30的值，经过五次右移和位或操作后，可以得到一个2^k - 1的值。最后再将这个值+1，得到2^k。
    //如果传入的值大于等于2^30，那么经过转化会变成负值，即< 0，此时会把初始值设置为2^30，即最大的容量只有2^30。
    //无符号右移再进行按位或操作，就是将其低位全部补成1，然后再自加加一次，就是再向前进一位。
    //这样就能得到其最小的2次幂。之所以需要最多移16位，是为了能够处理大于2^16次方数。
    private void allocateElements(int var1) {
        int var2 = 8;
        if (var1 >= var2) {
            // 5次位移可以得到2的n次幂减1
            var2 = var1 | var1 >>> 1;
            var2 |= var2 >>> 2;
            var2 |= var2 >>> 4;
            var2 |= var2 >>> 8;
            var2 |= var2 >>> 16;
            ++var2;
            // 传2的n次幂会有问题，最终的值是2的n+1次幂
            if (var2 < 0) {
                var2 >>>= 1;
            }
        }
        this.elements = (Object[])(new Object[var2]);
    }

5、ArrayDeque-扩容

1、扩容：无论是从头部还是从尾部添加元素，都会判断tail==head，如果两个索引相遇，说明数组空间已满，需要扩容操作。
2、源码：    
    private void doubleCapacity() {
        assert this.head == this.tail;    //扩容时头部索引和尾部索引肯定相等
        int var1 = this.head;    //头指针的位置
        int var2 = this.elements.length; //旧数组的长度
        int var3 = var2 - var1;    //旧数组中，头指针离数组尾部的距离
        int var4 = var2 << 1; //左移一位，相当于*2，即把新数组长度变为原来的两倍
        //判断数组的长度是否小于0，也是判断是否有溢出
        if (var4 < 0) {
            throw new IllegalStateException("Sorry, deque too big");
        } else {
            Object[] var5 = new Object[var4]; //新建一个数组，长度为旧长度的两倍
            System.arraycopy(this.elements, var1, var5, 0, var3);//将旧数组head之后的元素拷贝到新数组中
            System.arraycopy(this.elements, 0, var5, var3, var1);//将旧数组下标0到head之间的元素拷贝到新数组中
            this.elements = (Object[])var5;// 赋值为新数组
            // head指向0，tail指向旧数组长度表示的位置
            this.head = 0;
            this.tail = var2;
        }
    }
    // 拷贝该数组的所有元素到目标数组  
    private <T> T[] copyElements(T[] a) {  
        if (head < tail) { // 开始索引大于结束索引，一次拷贝  
            System.arraycopy(elements, head, a, 0, size());  
        } else if (head > tail) { // 开始索引在结束索引的右边，分两段拷贝  
            int headPortionLen = elements.length - head;  
            System.arraycopy(elements, head, a, 0, headPortionLen);  
            System.arraycopy(elements, 0, a, headPortionLen, tail);  
        }  
        return a;  
    }

5-1、ArrayDeque-扩容-源码分析-示意图

6、ArrayDeque-添加元素

1、添加元素，此处也是指入队，主要有两种方式：从队列头部、从队列尾部、
2、入队的方法，有很多，此处分析，addFirst(E e)和addLast(E e)
    2-1、.addFirst(E e)源码：在head的前面插入元素，在空间足够且下标没有越界的情况下，只需要将elements[--head] = e            
        //将元素从数组的最后一个位置向前依次存放。
        public void addFirst(E var1) {
            if (var1 == null) {
                throw new NullPointerException();
            } else {
                /**
                    1、将head指针减1并与数组长度减1取模,防止数组到头了边界溢出,如果到头了就从尾再向前。
                    2、elements.length一定是2的n次幂，转换为二进制就是n+1位为1，其他位为0。
                        [比如：4 = 2^2(10) = 100(2)] 
                    3、那么elements.length-1，从右到左n位都是1，比如4(10)=100(2)-1=011(2)。
                    4、第一次添加时，head=0，head-1=-1(10)=[00000001]原=[11111110]反
                    5、举例：elements.length=16，那么第一次添加：this.head = this.head - 1 & this.elements.length - 1 =
                            11111110
                          &    01111000
                        ------------
                            01111000 ==> 15
                            第二次添加时head=15 head - 1 = 14 转为二进制 1110，1110 & 1111结果为1110(14)
                    6、可推出：实际上head = (head - 1) & (elements.length - 1)就是最后一位开始递减
                */
                //从最后一位开始依次向前添加元素
                //x & (len - 1) = x % len，使用&的方式更快；
                //相当于取余，同时解决了head为负值的情况
                this.elements[this.head = this.head - 1 & this.elements.length - 1] = var1;
                // 当head==tail时进行扩容
                if (this.head == this.tail) {
                    this.doubleCapacity();
                }
            }
        }
    2-2、.addLast(E e)源码：在tail的位置插入元素，由于tail总是指向下一个可以插入的空位，因此只需要elements[tail] = e;
        //将元素从数组的第一个位置依次向后存放。
        public void addLast(E var1) {
            if (var1 == null) {
                throw new NullPointerException();
            } else {
                //tail指针指向的是队列最后一个元素的下一个位置,在尾指针的位置放入元素。
                //是把元素放在tail位置之后再把tail+1的，也就是说tail下标位置是没有值的，也就是含头不含尾。
                this.elements[this.tail] = var1;
                //为了处理临界情况 (tail为length - 1时)，和length - 1进行与操作，结果为0。 
                //比如：elements.length = 16，当head为0，tail当前值为15时实际上数组这时已经满了，那么tail + 1 = 16, elements.length - 1 = 15， head = 0，那么10000 & 1111 = 00000000 == head
                //x & (len - 1) = x % len，使用&的方式更快；
                if ((this.tail = this.tail + 1 & this.elements.length - 1) == this.head) {
                    this.doubleCapacity();
                }
            }
        }
    2-3、
        public boolean offerFirst(E e) {  
            addFirst(e);  
            return true;  
        }  
    2-4、
        public boolean offerLast(E e) {  
            addLast(e);  
            return true;  
        }

6-1、ArrayDeque-头部添加元素-示意图

6-2、ArrayDeque-尾部添加元素-示意图

7、ArrayDeque-取出元素

1、取出元素，方法有很多，此处只介绍.pollFirst()和.pollLast()。    
2、源码分析：
    //删除并返回Deque首端元素，也即是head位置处的元素。
    public E pollFirst() {
        int var1 = this.head;
        //取出队列头元素
        Object var2 = this.elements[var1];
        if (var2 == null) {
            return null;
        } else {
            this.elements[var1] = null;//将队列头置为空
            // 队列头指针右移一位，即头指针加1再和数组最大下标按位与计算出新的head
            this.head = var1 + 1 & this.elements.length - 1;
            return var2;
        }
    }
    //删除并返回Deque尾端元素，也即是tail位置前面的那个元素。
    //注意：出队之后没有缩容
    //每次pollLast()前tail先减1，然后再删除，tail指向的位置在元素的上一个位置。
    //pollLast() 也是绕着数组循环删除的。tail一直绕着数组循环转动。
    public E pollLast() {
        //尾指针左移一位, 取模的方式让头尾指针在数组范围内循环
        int var1 = this.tail - 1 & this.elements.length - 1;
        //取当前尾指针处元素
        Object var2 = this.elements[var1];
        if (var2 == null) {
            return null;
        } else {
            // 将当前尾指针处置为空
            this.elements[var1] = null;
            // tail指向新的尾指针处，将取出到的元素位置索引赋给tail，tail处值为null，含头不含尾
            this.tail = var1;
            // 返回取得的元素
            return var2;
        }
    }
    //返回但不删除Deque首端元素，也即是head位置处的元素，直接返回elements[head]即可。
    public E peekFirst() {
        return this.elements[this.head];
    }
    //返回但不删除Deque尾端元素，也即是tail位置前面的那个元素。
    public E peekLast() {
        return this.elements[this.tail - 1 & this.elements.length - 1];
    }

8、ArrayDeque-删除元素

1、删除元素 删除首尾元素
2、源码：
    //removeFirst() 就是调用pollFirst() 不同之处在于在当pollFirst()返回null removeFirst() 抛出 null 元素异常。
    public E removeFirst() {
        Object var1 = this.pollFirst();
        if (var1 == null) {
            throw new NoSuchElementException();
        } else {
            return var1;
        }
    }
    //removeLast() 就是调用pollLast() 不同之处在于在当pollLast()返回null removeLast() 抛出 null 元素异常。
    public E removeLast() {
        Object var1 = this.pollLast();
        if (var1 == null) {
            throw new NoSuchElementException();
        } else {
            return var1;
        }
    }
    public boolean removeFirstOccurrence(Object var1) {
        if (var1 == null) {
            return false;
        } else {
            int var2 = this.elements.length - 1;
            Object var4;
            for(int var3 = this.head; (var4 = this.elements[var3]) != null; var3 = var3 + 1 & var2) {
                if (var1.equals(var4)) {
                    this.delete(var3);
                    return true;
                }
            }
            return false;
        }
    }
    public boolean removeLastOccurrence(Object var1) {
        if (var1 == null) {
            return false;
        } else {
            int var2 = this.elements.length - 1;
            Object var4;
            for(int var3 = this.tail - 1 & var2; (var4 = this.elements[var3]) != null; var3 = var3 - 1 & var2) {
                if (var1.equals(var4)) {
                    this.delete(var3);
                    return true;
                }
            }
            return false;
        }
    }

9、ArrayDeque-栈|队列-操作方法

1、栈-操作 
    public void push(E e) {
        addFirst(e);
    }
    public E pop() {
        return removeFirst();
    }
2、队列操作
    public boolean add(E e) {  
        addLast(e);  
        return true;  
    }  
    public boolean offer(E e) {  
        return offerLast(e);  
    }  
    public E remove() {  
        return removeFirst();  
    }  
    public E poll() {  
        return pollFirst();  
    }  
    public E element() {  
        return getFirst();  
    }  
    public E peek() {  
        return peekFirst();  
    }

10、ArrayDeque-获取元素

public E getFirst() {  
    E x = elements[head];  
    if (x == null)  
        throw new NoSuchElementException();  
    return x;  
}  
public E getLast() {  
    E x = elements[(tail - 1) & (elements.length - 1)]; // 处理临界情况（当tail为0时），与后的结果为elements.length - 1。  
    if (x == null)  
        throw new NoSuchElementException();  
    return x;  
}  
public E peekFirst() {  
    return elements[head]; // elements[head] is null if deque empty  
}  
public E peekLast() {  
    return elements[(tail - 1) & (elements.length - 1)];  
}

11、ArrayDeque-Object方法

public ArrayDeque<E> clone() {  
    try {  
        ArrayDeque<E> result = (ArrayDeque<E>) super.clone();  
        result.elements = Arrays.copyOf(elements, elements.length); // 深度复制。  
        return result;  
    } catch (CloneNotSupportedException e) {  
        throw new AssertionError();  
    }  
}

https://blog.csdn.net/ztx114/article/details/89712772
https://www.cnblogs.com/chenglc/p/10722304.html
https://www.pdai.tech/md/java/collection/java-collection-Queue&Stack.html
https://www.cnblogs.com/lxyit/p/9080590.html