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

 

一、队列

队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

二、双端队列

双端队列是只既可以在表的前端进行插入和删除操作，又可以在表的后端进行插入和删除操作。

三、ArrayDeque的实现

Java中的双端队列是用数组实现的，类的全限名称是java.util.ArrayDeque，该类的声明如下：

 

public class ArrayDeque<E> extends AbstractCollection<E>implements Deque<E>, Cloneable, Serializable{}

 

 

该类继承了AbstractCollection类，实现了Deque、Cloneable和Serializable接口。实现Cloneable和Serializable接口的主要目的是为了实现克隆和序列化。

该类中定义了四个个成员变量

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 作为数组的最小长度。

其构造函数有一下几种：

 

public ArrayDeque() {
        elements = (E[]) new Object[16];
    }

 

 

第一种构造函数，默认情况下，数组的长度为16。

 

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

 

第二种构造函数，给定数组长度，则调用allocateElements()函数，分配数组空间。allocateElements()函数的实现如下：

private void allocateElements(int numElements) {
        int initialCapacity = MIN_INITIAL_CAPACITY;
        if (numElements >= initialCapacity) {
            initialCapacity = numElements;
            initialCapacity |= (initialCapacity >>>  1);
            initialCapacity |= (initialCapacity >>>  2);
            initialCapacity |= (initialCapacity >>>  4);
            initialCapacity |= (initialCapacity >>>  8);
            initialCapacity |= (initialCapacity >>> 16);
            initialCapacity++;

            if (initialCapacity < 0)   // Too many elements, must back off
                initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
        }
        elements = (E[]) new Object[initialCapacity];
    }

 

 

对于一个给定长度，先判断是否小于定义的最小长度，如果小于，则使用定义的最小长度作为数组的长度。否则，找到比给定长度大的最小的2的幂数（在if里面的以为语句实现这一功能）。

 

public ArrayDeque(Collection<? extends E> c) {
        allocateElements(c.size());
        addAll(c);
    }

 

 

第三种构造函数，给定一个集合，先分配空间，然后添加到集合中。

从上面的三种构造函数中，可以判断出来，数组的长度是2的幂数，定义为2的幂数个人认为有两个原因：

1.伙伴系统

操作系统分配内存的方法使用伙伴系统的话，每一块的大小都是2的幂数，如果分配的内存大小为2的幂数，可以减少内存分配的时间。

伙伴系统在百度百科中的解释：http://baike.baidu.com/view/4935190.htm

2.插入和删除的速度

对于数组，如果head的值为0,时，在队首插入元素，有一种方法是将全部元素都向后移动一位，然后将新的元素插入。这样子的话，插入和删除的速度会非常慢，特别是在元素很多的情况下。另一种方法就是在head的值为0时，在队首插入元素，可以将head的值置为（数组的长度-1）。也就是将新插入的元素放到数组的最后，以此类推。在计算插入元素位置下标的时候，数组长度是2的幂数就用处了。下面是插入元素时，计算插入位置的值的语句

 

head = (head - 1) & (elements.length - 1)

 

 

length-1的值为高位全为0，低位全为1，通过按位相与，可以得出应该插入元素的位置。
然后就是该类的一些方法了，有点面向对象的思想的都应该会想到，应该有头插，头删，尾插，尾删等等一些操作，在此就不一一列出了，实现起来也比较简单。关键还是要了解ArrayDeque的实现机制。

 

评论

2 楼 long_yu2 2012-05-21  

1 楼 bk_lin 2012-05-20  

以前没听说过，学习了