Java中Deque和ArrayDeque

Deque类

一个线性的可在双端插入、删除节点的结构。他名字时Deque，实际上时“double ended queue”的简写；

ArrayDeque类

对于ArrayDeque中的数组，它是一个逻辑上的循环数组，所谓循环是指元素到数组尾之后可以接着从数组头开始，数组的长度、第一个和最后一个元素都与head和tail这两个变量有关

构造方法

ArrayDeque就像他的名字一样，使用Array数组来实现Deque结构。构造方法和以前提到的ArrayList相似。

public ArrayDeque() {
// 初始化的数组大小是16
        elements = new Object[16];
    }

public ArrayDeque(int numElements) {
        allocateElements(numElements);
    }

public ArrayDeque(Collection<? extends E> c) {
        allocateElements(c.size());
        // addAll方法就是为c 进行for循环添加
        addAll(c);
    }

添加和移除方法

• add方法

// 在前面添加元素，也就是在数组的第一个位置上加元素
public void addFirst(E e) {
        if (e == null)
            throw new NullPointerException();
            // 在前面添加的时候，head-1 的位置上插入 e
        elements[head = (head - 1) & (elements.length - 1)] = e;
        if (head == tail)
            doubleCapacity();
    }

public void addLast(E e) {
        if (e == null)
            throw new NullPointerException();
            添加到下一个位置
        elements[tail] = e;
        /* 
         * 如果当前添加位置的下一个位置 与上 长度-1 
         *（因为长度都是2的倍数，所以-1之后，2进制后几位都是1，保证负数的时候也能够找到正确的索引）
         * 如果tail和head相等说明数组满了，需要扩容
         */
        if ( (tail = (tail + 1) & (elements.length - 1)) == head)
            doubleCapacity();
    }

有了这两种方法，队列或者栈的方法都可以轻松实现了。

在进行增加元素的时候涉及到 doubleCapacity 这个方法，这个方法主要用来扩充数组的容量。

private void doubleCapacity() {
        assert head == tail;
        int p = head;
        int n = elements.length;
        int r = n - p; // head右边元素的个数
        int newCapacity = n << 1; // 扩充为原来的2倍
        if (newCapacity < 0)
            throw new IllegalStateException("Sorry, deque too big");
        Object[] a = new Object[newCapacity]; //创建新数组
        Systkkem.arraycopy(elements, p, a, 0, r); 
        System.arraycopy(elements, 0, a, r, p);// 两部copy数组相当于从 head -> tail 重新排序了
        elements = a;
        head = 0;
        tail = n;
    }

• remove方法

public E remove() {
        return removeFirst();
    }

public E removeFirst() {
        E x = pollFirst();
        if (x == null)
            throw new NoSuchElementException();
        return x;
    }

public E pollFirst() {
        int h = head;
        @SuppressWarnings("unchecked")
        E result = (E) elements[h];
        // Element is null if deque empty
        if (result == null)
            return null;
        elements[h] = null;     // Must null out slot
        // 把element的头部位置置空后，将head向前移
        head = (h + 1) & (elements.length - 1);
        return result;
    }

• toArray方法

toArray方法主要是方便输出。用来真正的按照逻辑顺序，进行物理重排，实现方法和doubleCapacity实现相同。

public Object[] toArray() {
        return copyElements(new Object[size()]);
    }

private <T> T[] copyElements(T[] a) {
        if (head < tail) {
         // 如果顺序正常
            System.arraycopy(elements, head, a, 0, size());
        } else if (head > tail) {
         // 否则将head右侧的先copy到数组中，在copy剩下的
            int headPortionLen = elements.length - head;
            System.arraycopy(elements, head, a, 0, headPortionLen);
            System.arraycopy(elements, 0, a, headPortionLen, tail);
        }
        return a;
   }

• size方法

和很多数据结构类不同的是，他的size并不是依靠本身的变量字段进行维护，而是通过size方法计算而来。

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

总结一下，ArrayDeque实现了双端队列的特点，能够完成栈和队列的功能，效率比同样继承Deque的LinkedList效率高，因为在ArrayDeque中的计算大部分为位运算。ArrayDeque逻辑上循环的数组，但实际上并不是。