一、队列
队列是一种特殊的线性表,它只允许在表的前端(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的实现机制。
分享到:
相关推荐
用双端队列(deque)实现栈的功能, 数据结构作业 栈(先进后出)的一种数据结构 内含一个cpp文件和两个头文件。
python--双端队列deque(csdn)————程序
[4.5.1]--312双端队列抽象数据类型及Python实现+回文词判定.srt
[4.5.1]--312双端队列抽象数据类型及Python实现+回文词判定.mp4
算法-数据结构和算法-5-队列和双端队列.rar
在Java中,ArrayDeque(数组双端队列)是一种双向队列(deque),它实现了Deque接口。ArrayDeque的底层是使用数组来实现的,因此它具有快速的随机访问和高效的插入/删除操作。
java双端队列的实现-Java实现自定义双端队列(链表和数组两种方式) 数组和链表.pdf
双端队列,在基础类上派生 用来实现平移递推滤波数据存储
1. 基于双链表实现双端队列的典型操作(判空、头插、头删、尾插、尾删、普通构造、拷贝构造、赋值运算符重载、析构),编写简单程序使用该双端队列,测试和调试程序。 2. 基于双端队列的头插、头删操作,完成栈的...
自己用C++实现的双端队列数据结构,通过测试,并有注释。有需要的朋友可以看一看
双端队列(deque,double-ended queue),是一种具有队列和栈的性质的数据结构。 双端队列中每一端,都可以进行存入和取出,去其中一段,都像一个栈一样。 存取也只限定在两端,不能在中间 双端队列的实现 通过...
本文实例讲述了Python实现的数据结构与算法之双端队列。分享给大家供大家参考。具体分析如下: 一、概述 双端队列(deque,全名double-ended queue)是一种具有队列和栈性质的线性数据结构。双端队列也拥有两端:队...
* 基于双向链表实现双端队列结构 */ package dsa; public class Deque_DLNode implements Deque { protected DLNode header;//指向头节点(哨兵) protected DLNode trailer;//指向尾节点(哨兵) protected ...
行业分类-电子-关于双端通电LED日光灯的改良结构的说明分析.rar
行业分类-电子-关于双端封装的双电弧管HID氙气灯泡的说明分析.rar
VC++2010编程演练数据结构《1》循环双端队列
双端队列源代码,完整工程文件,完整代码,含注释。
所谓双端队列(double-ended queue,deque),就是在列表的两端都可以插入和删除数据。 因此它允许的操作有Create、IsEmpty、IsFull、Left、Right、AddLeft、AddRight、DeleteLeft、 DeleteRight。使用循环数组方式...
行业资料-电子功用-异步双端电力电缆振荡波局部放电识别与定位方法