上一篇看了ArrayDeque的添加元素，這篇我們來看刪除元素是怎樣實現(xiàn)的。

    /**
     * @throws NoSuchElementException {@inheritDoc}
     */
    public E removeFirst() {
        E e = pollFirst();
        if (e == null)
            throw new NoSuchElementException();
        return e;
    }

原來removeFirst調(diào)用了pollFirst，我們來看看pollFirst：

    public E pollFirst() {
        final Object[] es;
        final int h;
        E e = elementAt(es = elements, h = head);
        if (e != null) {
            es[h] = null;
            head = inc(h, es.length);
        }
        return e;
    }

調(diào)用了elementAt從elements獲取了head位置的元素：

    static final <E> E elementAt(Object[] es, int i) {
        return (E) es[i];
    }

因為是數(shù)組，所以直接通過下標(biāo)訪問即可，時間復(fù)雜度O(1)。

然后將head元素置空，通過head = inc(h, es.length);將head位置加一。如果超過數(shù)組長度，根據(jù)循環(huán)數(shù)組的特點，變?yōu)閿?shù)組第0個下標(biāo)。

而pollLast實現(xiàn)也是差不多的，就不多啰嗦了。

而peekFirst、peekLast就更簡單了，直接通過elementAt通過數(shù)組下標(biāo)快速訪問元素即可：

    public E peekFirst() {
        return elementAt(elements, head);
    }

    public E peekLast() {
        final Object[] es;
        return elementAt(es = elements, dec(tail, es.length));
    }

由于是數(shù)組，所以極度不推薦刪除元素的，所以removeFirstOccurrence和removeLastOccurrence這2個極度浪費性能操作能不用盡量不用。

    /**
     * Removes the first occurrence of the specified element in this
     * deque (when traversing the deque from head to tail).
     * If the deque does not contain the element, it is unchanged.
     * More formally, removes the first element {@code e} such that
     * {@code o.equals(e)} (if such an element exists).
     * Returns {@code true} if this deque contained the specified element
     * (or equivalently, if this deque changed as a result of the call).
     *
     * @param o element to be removed from this deque, if present
     * @return {@code true} if the deque contained the specified element
     */
    public boolean removeFirstOccurrence(Object o) {
        if (o != null) {
            final Object[] es = elements;
            for (int i = head, end = tail, to = (i <= end) ? end : es.length;
                 ; i = 0, to = end) {
                for (; i < to; i++)
                    if (o.equals(es[i])) {
                        delete(i);
                        return true;
                    }
                if (to == end) break;
            }
        }
        return false;
    }

這個removeFirstOccurrence就是刪除第一個找到的元素。如果雙端隊列不包含某個元素，那么就不會變。如果該元素被刪除，就會使得數(shù)組的元素向前或向后運動。 delete函數(shù)作者已經(jīng)優(yōu)化了算法，使得每次挪動最少的元素。

    /**
     * Removes the element at the specified position in the elements array.
     * This can result in forward or backwards motion of array elements.
     * We optimize for least element motion.
     *
     * <p>This method is called delete rather than remove to emphasize
     * that its semantics differ from those of {@link List#remove(int)}.
     *
     * @return true if elements near tail moved backwards
     */
    boolean delete(int i) {
        final Object[] es = elements;
        final int capacity = es.length;
        final int h, t;
        // number of elements before to-be-deleted elt
        final int front = sub(i, h = head, capacity);
        // number of elements after to-be-deleted elt
        final int back = sub(t = tail, i, capacity) - 1;
        if (front < back) {
            // move front elements forwards
            if (h <= i) {
                System.arraycopy(es, h, es, h + 1, front);
            } else { // Wrap around
                System.arraycopy(es, 0, es, 1, i);
                es[0] = es[capacity - 1];
                System.arraycopy(es, h, es, h + 1, front - (i + 1));
            }
            es[h] = null;
            head = inc(h, capacity);
            return false;
        } else {
            // move back elements backwards
            tail = dec(t, capacity);
            if (i <= tail) {
                System.arraycopy(es, i + 1, es, i, back);
            } else { // Wrap around
                System.arraycopy(es, i + 1, es, i, capacity - (i + 1));
                es[capacity - 1] = es[0];
                System.arraycopy(es, 1, es, 0, t - 1);
            }
            es[tail] = null;
            return true;
        }
    }

每刪除一個元素，都要挪動其他元素，非常劃不來。那如果用了ArrayDeque，但是迫不得已要刪除元素，怎么辦？我建議在保存的元素Object里面添加一個叫isDelete的boolean屬性。使用前先判斷isDelete即可。這就像居委大媽跟普通大媽區(qū)別，就是袖子上多一個紅袖標(biāo)，大大寫著“居委”兩字。