java arrayqueue(ArrayDeque)-东辰安华生活网

java arrayqueue(ArrayDeque),本文通过数据整理汇集了java arrayqueue(ArrayDeque)相关信息，下面一起看看。

问题(1)什么是德雀？

(2)2)array Deque是如何实现deque的？

(3)3)array deque线程安全吗？

(4)ArrayDeque是有界的吗？

简介deque是一种特殊的队列，两端都可以进出元素，故名deque。

ArrayDeque是一个作为数组实现的Deque，它是非线程安全的。

继承制度

从继承系统可以看出，ArrayDeque实现了Deque接口，它继承了Queue接口，是对Queue的增强。

接口dequee扩展queuee {//添加元素到队列头void Add first(E E)；//在队列void addLast(E e)的末尾添加一个元素；//将元素添加到队列头布尔offer first(E E)；//将元素添加到队列的末尾布尔offer last(E E)；//从队列头中移除元素E Remove first()；//从队列末尾移除元素E Remove last()；//从队列头中删除元素E poll first()；//从队列末尾移除元素E poll last()；//检查队列头元素E get first()；//检查队列尾部元素E get last()；//检查队列头元素E peek first()；//检查队列尾部元素E peek last()；//从队列头向后遍历以移除指定元素boolean removefirstocurrence(object o)；//从队列末尾向前遍历以移除指定元素boolean removelastcoccurrence(object o)；//* * *队列中的方法* *//添加一个元素，等于add last(E)boolean add(E E)；//添加一个元素，等于offerLast(e)布尔offer(E E)；//移除元素，等于Remove first()E Remove()；//移除元素，等于poll first()E poll()；//查看元素，等于get first()E element()；//查看元素，等于peek first()E peek()；//* * *堆栈方法* * *//堆栈，等于add first(E)void push(E E E)；//退出堆栈，等于remove first()E pop()；//* * *集合中的方法* *//删除指定元素，等于removefirstocurrence(o)boolean remove(object o)；//检查是否有元素布尔包含(Object o)；//元素个数public int size()；//iterator iterator()；//反向迭代器iterator descending iterator()；}在}队列中添加了以下方法：

(1)*First，表示从队列头开始操作元素；

(2)*Last，表示该元素从队列末尾开始操作；

(3)push(e)、pop()的方法，以堆栈的方式操作元素；

分析源代码的主要属性。//数组存储元素的瞬态对象[]元素；//非私有以简化嵌套类访问//队列头位置瞬态int head//队列尾部位置瞬态int tail//最小初始容量private static final int min _ initial _ capacity=8；从属性中我们可以看到，ArrayDeque使用数组来存储元素，并使用头尾指针来标识队列的头和尾。它的最小容量是8。

主构造方法//默认构造方法，初始容量为16公共数组deque(){ elements=new object[16]；}//指定初始化公共数组deque(int num elements){ allocate elements(num elements)的元素个数；}//将集合C中的元素初始化到数组public ArrayDeque(集合？扩展E c){ allocate elements(c . size())；addAll(c)；}//初始化数组private void allocate elements(int num elements){ elements=new object[calculatesize(num elements)]；}//计算容量。这段代码的逻辑是计算最接近2的大于numElements且不小于8的n次方//比如3是8，9是16，33是64私有静态int计算器(int num elements){ int initial capacity=min _ initial _ capacity；//找到2的最佳幂来保存元素。//测试“=”，因为数组没有保持满。if(num elements=initial capacity){ initial capacity=num elements；initial capacity |=(initial capacity 1)；initial capacity |=(initial capacity 2)；initial capacity |=(initial capacity 4)；initial capacity |=(initial capacity 8)；initial capacity |=(initial capacity 16)；初始容量；if (initialCapacity 0) //元素太多，必须回退initial capacity=1；//好运分配2 ^ 30元素} return initialcapacity}通过构造方法，我们知道默认初始容量是16，最小容量是8。

加入团队的方式有很多。这里主要分析两个，addFirst(e)和addLast(e)。

//从队列头入队public void add first(E E){//null element if(E==null)throw new nullpointerexception()不允许；//将头指针减1，并将数组长度取模值减1。//这是为了防止数组末尾溢出。//如果结束了，就从末尾到前面。//相当于回收数组元素[head=(head-1)(elements . length-1)]=e；//如果头尾在一起，就扩充容量。//展开规则也很简单，直接double if(head==tail)double capacity()；}//从队列末尾入队public void add last(E E){//null element if(E==null)throw new nullpointerexception()不允许；//将一个元素放在尾指针的位置。//可以看到尾指针指向队列中最后一个元素的下一个位置。elements[tail]=e；//尾指针加1，如果到达数组末尾，从头开始if((tail=(tail 1)(elements . length-1))==head)double capacity()；}(1)加入队列有两种方式，从队列头或者从队列尾；

(2)如果容量不够，直接扩容到两倍；

(3)取模使头尾指针在数组范围内循环；

(4)x (len-1)=x% len，用的比较快；

扩展私有void double capacity(){ Asser head==tail；//头指针的位置int p=head//旧数组长度int n=elements.length//头指针到数组末尾的距离int r=n-p；//p//右边的元素个数新长度是旧长度的两倍int new capacity=n ^ 1；//判断(newcapacity 0)是否抛出新的illegalstateexception('对不起，deque太大')溢出；//创建一个新的数组对象[]a=new object[new capacity]；//将旧数组头后的元素复制到新数组system.arraycopy (elements，p，a，0，r)；//将旧数组下标0和头之间的元素复制到新数组系统中。ArrayCopy (elements，0，a，r，p)；//给新数组元素赋值=a；//head指向0，tail指向旧数组长度head=0所代表的位置；tail=n；}扩展这里的迁移元素可能有点混乱。请看下图就明白了。

也有很多方法可以出队。我们主要看两个，pollFirst()和pollLast()。

//从队列头出列public E poll first(){ int h=head；@ suppress warnings(' unchecked ')//获取队列头元素E result=(E)elements[h]；//如果队列为空，则返回null if (result==null)返回null；//将队列头设置为空元素[h]=null；//必须空出slot //队列头指针右移一位head=(h 1)(elements . length-1)；//返回获得的元素返回结果；}//从队列尾部出队public e poll last(){//尾部指针左移一位int t=(tail-1)(elements . length-1)；@ suppress warnings(' unchecked ')//在当前尾指针处取元素E result=(E)elements[t]；//如果队列为空则返回null(result==null)返回null；//将当前尾指针作为空元素[t]=null处理；//tail指向新的尾指针，其中tail=t；//返回获得的元素返回结果；}(1)出列有两种方式，从队列头或者从队列尾；

(2)取模使头尾指针在数组范围内循环；

(3)离队后不缩水哈哈

Stack我们前面介绍Deque的时候说过Deque可以直接作为堆栈使用，那么ArrayDeque是如何实现的呢？

public void push(E E){ add first(E)；} public E pop(){ return remove first()；}不是很简单吗？只要大家都操作队列头，就可以把栈推进推出去。

总结：(1)ArrayDeque是一个用数组实现的deque

(2)array queue的出队是通过回收头尾指针数组实现的；

(3)当3)ArrayDeque的容量不足时，会进行扩容，每次扩容的容量会翻倍；

(4)ArrayDeque可以直接作为栈使用；

德奎和双队列？

Deque指的是队列两端都可以进出元素的队列，真正的元素存储在里面。

双重队列是指一个队列有两个用途，队列中的节点分为数据节点和非数据节点。它是LinkedTransferQueue使用的数据结构。

还记得LinkedTransferQueue吗？点击链接直接进入【死磕java合集的LinkedTransferQueue源代码分析】。