Java数据结构 -ArrayDeque 双端队列的简单分析

一、队列
队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
二、双端队列
双端队列是只既可以在表的前端进行插入和删除操作，又可以在表的后端进行插入和删除操作。
三、ArrayDeque的实现
Java中的双端队列是用数组实现的，类的全限名称是java.util.ArrayDeque，该类的声明如下：
 
Java代码  
public class ArrayDeque<E> extends AbstractCollection<E>implements Deque<E>, Cloneable, Serializable{}  
 
 
该类继承了AbstractCollection类，实现了Deque、Cloneable和Serializable接口。实现Cloneable和Serializable接口的主要目的是为了实现克隆和序列化。
该类中定义了四个个成员变量
Java代码  
public class ArrayDeque<E> extends AbstractCollection<E>  
      implements Deque<E>, Cloneable, Serializable  
{  
    private transient E[] elements;  
    private transient int head;  
    private transient int tail;  
    private static final int MIN_INITIAL_CAPACITY = 8;  
}  
 
其中elements是数组的首地址，head是指向队首的下标，tail是指向队尾的下一个位置的下标。MIN_INITIAL_CAPACITY 定义了在创建队列是，如果有指定长度，而且指定长度小于MIN_INITIAL_CAPACITY，则使用MIN_INITIAL_CAPACITY 作为数组的最小长度。
其构造函数有一下几种：
 
Java代码  
public ArrayDeque() {  
      elements = (E[]) new Object[16];  
    }  
 
 
第一种构造函数，默认情况下，数组的长度为16。
 
Java代码  
public ArrayDeque(int numElements) {  
      allocateElements(numElements);  
    }  
 
第二种构造函数，给定数组长度，则调用allocateElements()函数，分配数组空间。allocateElements()函数的实现如下：
Java代码  
private void allocateElements(int numElements) {  
      int initialCapacity = MIN_INITIAL_CAPACITY;  
      if (numElements >= initialCapacity) {  
      initialCapacity = numElements;