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

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

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

ArrayDeque禁止插入空元素。

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

ArrayDeque是Java Collections Framework的一个成员。

1.   ArrayDeque的声明

ArrayDeque的接口和继承关系如下

public class ArrayDeque extends 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