`
mixer_a
  • 浏览: 338359 次
社区版块
存档分类
最新评论

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的实现机制。

 

7
1
分享到:
评论
2 楼 long_yu2 2012-05-21  
1 楼 bk_lin 2012-05-20  
以前没听说过,学习了

相关推荐

Global site tag (gtag.js) - Google Analytics