【Java 数据结构及算法实战】系列 014：Java队列08——数组实现的双端队列ArrayDeque

ArrayDeque是基于数组实现的无界双端队列。ArrayDeque中的数组没有容量限制，它们能根据需要增长以支持使用。需要注意的是ArrayDeque不是线程安全的，因此在没有外部同步的情况下，它们不支持多线程并发访问。

ArrayDeque用作栈时可能比Stack更快，用作队列时可能比LinkedList更快。

ArrayDeque禁止插入空元素。

ArrayDeque及其迭代器实现了Collection和Iterator接口的所有可选方法。

ArrayDeque是Java Collections Framework的一个成员。

1.   ArrayDeque的声明

ArrayDeque的接口和继承关系如下

public class ArrayDequeextends AbstractCollection

      implements Deque, Cloneable, Serializable

   …

}

完整的接口继承关系如下图所示。

编辑

从上述代码可以看出，ArrayDeque既实现了java.util.Deque 、java.lang.Cloneable、java.io.Serializable接口，又继承了java.util.AbstractCollection。

2.   ArrayDeque的成员变量和构造函数

以下是ArrayDeque的构造函数和成员变量。

// 元素数组

    transient Object[] elements;

// 队列头索引

    transient int head;

// 队列尾索引

    transient int tail;

// 数组最大容量

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

public ArrayDeque() {

        elements = new Object[16 + 1];

    }

    public ArrayDeque(int numElements) {

        elements =

            new Object[(numElements < 1) ? 1 :

                       (numElements == Integer.MAX_VALUE) ? Integer.MAX_VALUE :

                       numElements + 1];

    }

    public ArrayDeque(Collection

        this(c.size());

        copyElements(c);

}

从上述代码可以看出，构造函数有3种。构造函数中的参数含义如下

l  numElements用于设置队列中内部数组的元素总数。如果没有指定，则会使用默认元素总数16。需要注意的是，实际数组的大小，是numElements+1。

l  c用于设置最初包含给定集合的元素，按集合迭代器的遍历顺序添加

类成员elements是一个数组，用于存储队列中的元素。head和tail分别表示队头索引和队尾索引。

思考：为什么实际数组的实际数组的大小，是numElements+1？

3.   ArrayDeque的核心方法

以下对ArrayDeque常用核心方法的实现原理进行解释。

3.1.     addLast(e)

执行addLast(e)方法后有两种结果

l  队列未达到容量时，直接插入，没有返回值

l  队列达到容量时，先扩容，再插入，没有返回值

ArrayDeque的addLast(e)方法源码如下：

    public void addLast(E e) {

        if (e == null)  // 判空

            throw new NullPointerException();

        final Object[] es = elements;

        es[tail] = e;

        if (head == (tail = inc(tail, es.length)))

            grow(1);  // 扩容

    }

从上面代码可以看出，addLast(e)方法会先进行判空处理，而后再将元素插入。如果插入前判断容量不够，则会执行grow()方法进行扩容。

。

grow()方法源码如下：

private void grow(int needed) {

        // overflow-conscious code

        final int oldCapacity = elements.length;

        int newCapacity;

        // Double capacity if small; else grow by 50%

        int jump = (oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1);

        if (jump < needed

            || (newCapacity = (oldCapacity + jump)) - MAX_ARRAY_SIZE > 0)

            newCapacity = newCapacity(needed, jump);

        final Object[] es = elements = Arrays.copyOf(elements, newCapacity);

        // Exceptionally, here tail == head needs to be disambiguated

        if (tail < head || (tail == head && es[head] != null)) {

            // wrap around; slide first leg forward to end of array

            int newSpace = newCapacity - oldCapacity;

            System.arraycopy(es, head,

                             es, head + newSpace,

                             oldCapacity - head);

            for (int i = head, to = (head += newSpace); i < to; i++)

                es[i] = null;

        }

    }

    /** Capacity calculation for edge conditions, especially overflow. */

    private int newCapacity(int needed, int jump) {

        final int oldCapacity = elements.length, minCapacity;

        if ((minCapacity = oldCapacity + needed) - MAX_ARRAY_SIZE > 0) {

            if (minCapacity < 0)

                throw new IllegalStateException("Sorry, deque too big");

            return Integer.MAX_VALUE;

        }

        if (needed > jump)

            return minCapacity;

        return (oldCapacity + jump - MAX_ARRAY_SIZE < 0)

            ? oldCapacity + jump

            : MAX_ARRAY_SIZE;

    }

3.2.     offerLast(e)

执行offerLast(e)方法后有两种结果

l  队列未达到容量时，返回 true

l  队列达到容量时，先扩容，再返回 true

ArrayDeque的offerLast(e)方法源码如下：

public boolean offerLast(E e) {

        addLast(e);

        return true;

    }

从上面代码可以看出，执行offerLast(e)方法直接调用的是addLast(e)

。

3.3.     addLast(e)

执行addFirst(e)方法后有两种结果

l  队列未达到容量时，直接插入，没有返回值

l  队列达到容量时，先扩容，再插入，没有返回值

ArrayDeque的addFirst(e)方法源码如下：

    public void addFirst(E e) {

        if (e == null)  // 判空

            throw new NullPointerException();

        final Object[] es = elements;

        es[head = dec(head, es.length)] = e;

        if (head == tail)

            grow(1);  // 扩容

    }

从上面代码可以看出，addFirst(e)方法会先进行判空处理，而后再将元素插入。如果插入前判断容量不够，则会执行grow()方法进行扩容。

。

3.4.     pollFirst()

执行pollFirst()方法后有两种结果：

l  队列不为空时，返回队首值并移除

l  队列为空时，返回 null

ArrayDeque的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;

}

从上面代码可以看出，执行pollFirst()方法时，分为以下几个步骤：

l  先取队列的队首元素。

l  如果队首元素不存在，直接返回null。

l  如果队首元素存在，则返回该元素同时移除元素。

3.5.     removeFirst()

执行removeFirst()方法后有两种结果：

l  队列不为空时，返回队首值并移除

l  队列为空时，抛出异常

ArrayDeque的removeFirst()方法源码如下：

public E removeFirst() {

        E e = pollFirst();

        if (e == null)

            throw new NoSuchElementException();

        return e;

}

从上面代码可以看出，removeFirst()方法直接调用了pollFirst()方法。如果pollFirst()方法返回结果为null，则抛出NoSuchElementException异常。

pollFirst()方法此处不再赘述。

3.6.     peekFirst()

执行peekFirst()方法后有两种结果：

l  队列不为空时，返回队首值但不移除

l  队列为空时，返回null

peekFirst()方法源码如下：

public E peekFirst() {

        return elementAt(elements, head);

}

static final E elementAt(Object[] es, int i) {

        return (E) es[i];

}

从上面代码可以看出，peekFirst()方法比较简单，直接就是获取了数组里面的索引为head的元素。

3.7.     getFirst()

执行getFirst()方法后有两种结果：

l  队列不为空时，返回队首值但不移除

l  队列为空时，抛出异常

getFirst()方法源码如下：

public E getFirst() {

        E e = elementAt(elements, head);

        if (e == null)

            throw new NoSuchElementException();

        return e;

}

从上面代码可以看出，执行getFirst()方法时，先是获取了数组里面的索引为head的元素。如果结果是null，则抛出NoSuchElementException异常。

4.   ArrayDeque的单元测试

ArrayDeque的单元测试如下：

package com.waylau.java.demo.datastructure;

import static org.junit.jupiter.api.Assertions.assertEquals;

import static org.junit.jupiter.api.Assertions.assertNull;

import static org.junit.jupiter.api.Assertions.assertThrows;

import static org.junit.jupiter.api.Assertions.assertTrue;

import java.util.ArrayDeque;

import java.util.Deque;

import java.util.NoSuchElementException;

import org.junit.jupiter.api.Test;

/**

 * ArrayDeque Tests

 *

 * @since 1.0.0 2020年5月3日

 * @author