ArrayDeque

几句话证明你看过ArrayDeque的源码
Deque: double ended queue，双端队列，它既可以当作栈使用，也可以当作队列
推荐栈和队列（即对两端进行操作）使用AarryDeque，根据索引位置增删使用LinkedList
不允许存储null，非线程安全，不允许放 null 元素，无索引位置概念，默认容量是16且默认容量必须是 2 的幂次，不足2的幂次会自动向上调整为2的幂次

1.动态循环数组

ArrayList底层是一个动态数组transient Object[] elementData
size 则是动态数组的实际大小
transient int head头索引
transient int tail尾索引

循环数组.png

2.构造方法

ArrayDeque中的数组的容量总是2的幂，在取余的时候可以直接用位运算(&)来替代原本的取余操作(%)
只有容量为 2 的幂次时 ((tail + 1) & (elements.length - 1)) 操作中的 (elements.length - 1) 二进制最高位永远为 0，当 (tail + 1) 与其按位与操作时才能保证循环归零置位

/**
     * 默认数组长度16
     */
    public ArrayDeque() {
        elements = new Object[16];
    }

    /**
     * 指定长度
     */
    public ArrayDeque(int numElements) {
        allocateElements(numElements);
    }

    private void allocateElements(int numElements) {
        elements = new Object[calculateSize(numElements)];
    }

    /**
     * 数组长度为2的幂
     * 在取余的时候可以直接用位运算(&)来替代原本的取余操作(%)
     */
    private static int calculateSize(int numElements) {
        int initialCapacity = MIN_INITIAL_CAPACITY;
        // Find the best power of two to hold elements.
        // Tests "<=" because arrays aren't kept full.
        // 指定长度大于等于默认长度，改为合适的2的n次幂，否则默认长度
        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;
    }

3.push方法

/**
     * 用作stack，则是栈顶插入元素
     */
    public void addFirst(E e) {
        if (e == null)
            throw new NullPointerException();
        //由于数组长度必须为2的幂，在取余的时候可以直接用位运算(&)来替代原本的取余操作(%)
        //循环数组 防下标越界+head循环  (head - 1) % (elements.length)
        //head新角标，将元素存到head角标
        elements[head = (head - 1) & (elements.length - 1)] = e;
        //头尾在同一角标，说明循环数组被填满，触发扩容条件
        if (head == tail)
            doubleCapacity();
    }

    /**
     * 用作queue，则是队尾插入元素
     */
    public void addLast(E e) {
        if (e == null)
            throw new NullPointerException();
        //将元素存到tail角标 tail指向下一个可以插入的空位
        elements[tail] = e;
        //由于数组长度必须为2的幂，在取余的时候可以直接用位运算(&)来替代原本的取余操作(%)
        //循环数组 防下标越界+tail循环  (tail + 1) % (elements.length)
        //tail新角标 头尾在同一角标，说明循环数组被填满，触发扩容条件
        if ( (tail = (tail + 1) & (elements.length - 1)) == head)
            doubleCapacity();
    }

    /**
     * 扩容
     */
    private void doubleCapacity() {
        assert head == tail;
        int p = head;
        int n = elements.length;
        //head右边元素的个数
        int r = n - p; // number of elements to the right of p
        //原空间的2倍
        int newCapacity = n << 1;
        if (newCapacity < 0)
            throw new IllegalStateException("Sorry, deque too big");
        Object[] a = new Object[newCapacity];
        //复制右半部分到新数组，新数组从0开始
        System.arraycopy(elements, p, a, 0, r);
        //复制左半部分
        System.arraycopy(elements, 0, a, r, p);
        elements = a;
        //更新头尾节点，tail指向的是下一个可插入的位置
        head = 0;
        tail = n;
    }

4.pop方法

/**
     * 用作queue，获取并删除队首元素
     * 用作stack，获取并删除栈顶元素
     */
    public E pollFirst() {
        int h = head;
        @SuppressWarnings("unchecked")
        E result = (E) elements[h];
        // Element is null if deque empty
        if (result == null)
            return null;
        //赋值空，GC
        elements[h] = null;     // Must null out slot
        //循环数组 防下标越界+head循环  (h + 1) % (elements.length)
        head = (h + 1) & (elements.length - 1);
        return result;
    }

5.fast-fail机制

与ArrayList类似

6.自定义ArrayDeque练习

public class MyArrayDeque<E> implements MyDeque<E> {

    private static final int DEAULT_CAPACITY = 5;

    private E[] data;

    private int size;

    /**
     * 队列：先进先出，记录头尾
     */
    private int first;
    private int last;

    public MyArrayDeque(int capacity) {
        this.first = -1;
        this.last = -1;
        data = (E[]) new Object[capacity];
    }

    public MyArrayDeque() {
        this(DEAULT_CAPACITY);
    }

    @Override
    public void push(E e) {
        final int minCapacity = size + 1;
        if (minCapacity == data.length) {
            grow(minCapacity);
        }

        if (size == 0) {
            first = 0;
        }

        //如果元素弹出队列，由于从头开始弹出元素会导致数组靠前角标的元素弹出后，产生大量占用角标，数据却为空的情况
        //所以采用循环数组，当插入元素时，实际长度没有达到数组长度时，通过对数组长度取余，实现将尾部角标移动到前方的空角标
        //相当于first在前，last在后  
        last = (last + 1) % data.length;//last循环
        data[last] = e;

        size++;
    }

    private void grow(int minCapacity) {
        int newCapacity = data.length + (data.length >> 1);
        if (newCapacity < minCapacity) {
            newCapacity = minCapacity;
        }

        E[] newData = (E[]) new Object[newCapacity];
        //从原数组的头角标开始，复制整个数组到一个新数组上
        //新数组头角标为0，尾角标为实际长度-1
        System.arraycopy(data, first, newData, 0, size);
        data = newData;
        first = 0;
        last = size - 1;
    }

    @Override
    public E pop() {
        final E e = data[this.first];
        data[this.first] = null;
        size--;
        //弹出元素，头角标+1 因采用循环数组，通过取余数确认头角标
        this.first = (first + 1) % data.length;//first循环
        return e;
    }

    @Override
    public E peek() {
        return data[this.first];
    }

    @Override
    public boolean empty() {
        return size == 0;
    }

    @Override
    public int size() {
        return size;
    }

    public static void main(String[] args) {
        MyDeque<Integer> deque = new MyArrayDeque<>();
        for (int i = 0; i < 20; i++) {
            deque.push(i + 1);
        }
        System.out.println(deque.peek());
        System.out.println(deque.pop());
        int size = deque.size();
        for (int i = 0; i < size; i++) {
            Integer pop = deque.pop();
            System.out.println(pop);
        }
    }
}

7.自定义LinkedDeque练习

public class MyLinkedDeque<E> implements MyDeque<E> {

    private int size;

    private Node<E> first;

    private Node<E> last;


    @Override
    public void push(E e) {

        //前队尾结点
        Node<E> prev = this.last;

        //新的队尾结点
        last = new Node<>(e, null);

        //无数据时更新头结点
        if (size == 0) {
            first = last;
        }else{
            //前队尾结点的下一个元素指向新的队尾结点
            prev.next = last;
        }

        size++;
    }

    /**
     * 先进先出pop first
     *
     * @return
     */
    @Override
    public E pop() {
        //新队头结点
        Node<E> newFirstNode = first.next;
        E item = first.item;

        //更新队头结点
        first = newFirstNode;
        size--;

        //无数据时更新尾结点
        if (size == 0) {
            last = null;
        }

        return item;
    }

    @Override
    public E peek() {
        return first.item;
    }

    @Override
    public boolean empty() {
        return size == 0;
    }

    @Override
    public int size() {
        return size;
    }

    private static class Node<E> {
        E item;
        Node<E> next;

        public Node(E item, Node<E> next) {
            this.item = item;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        MyDeque<Integer> deque = new MyLinkedDeque<>();
        for (int i = 0; i < 20; i++) {
            deque.push(i + 1);
        }
        System.out.println(deque.peek());
        System.out.println(deque.pop());
        int size = deque.size();
        for (int i = 0; i < size; i++) {
            Integer pop = deque.pop();
            System.out.println(pop);
        }
    }
}

参考：https://www.cnblogs.com/CarpenterLee/p/5468803.html
https://www.rabbitwfly.com/