java arraydeque poll,Java ArrayDeque「建议收藏」

java arraydeque poll,Java ArrayDeque「建议收藏」Queue是什么Queue是具有队列特性的接口Queue具有先进先出的特点Queue所有新元素都插入队列的末尾,移除元素都移除队列的头部publicinterfaceQueueextendsCollection{//往队列插入元素,如果出现异常会抛出异常booleanadd(Ee);//往队列插入元素,如果出现异常则返回falsebooleanoffer(Ee);//移除队列元素…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

Queue是什么

Queue是具有队列特性的接口

Queue具有先进先出的特点

Queue所有新元素都插入队列的末尾,移除元素都移除队列的头部

public interface Queue extends Collection {

//往队列插入元素,如果出现异常会抛出异常

boolean add(E e);

//往队列插入元素,如果出现异常则返回false

boolean offer(E e);

//移除队列元素,如果出现异常会抛出异常

E remove();

//移除队列元素,如果出现异常则返回null

E poll();

//获取队列头部元素,如果出现异常会抛出异常

E element();

//获取队列头部元素,如果出现异常则返回null

E peek();

}

可以将上面的方法画成以下表格

操作

抛出异常

返回特殊值

插入

add()

offer()

删除

remove()

poll()

查询

element()

peek()

Deque是什么

Deque是一个双端队列

Deque继承自Queue

Deque具有先进先出或后进先出的特点

Deque支持所有元素在头部和尾部进行插入、删除、获取

public interface Deque extends Queue {

void addFirst(E e);//插入头部,异常会报错

boolean offerFirst(E e);//插入头部,异常返回false

E getFirst();//获取头部,异常会报错

E peekFirst();//获取头部,异常不报错

E removeFirst();//移除头部,异常会报错

E pollFirst();//移除头部,异常不报错

void addLast(E e);//插入尾部,异常会报错

boolean offerLast(E e);//插入尾部,异常返回false

E getLast();//获取尾部,异常会报错

E peekLast();//获取尾部,异常不报错

E removeLast();//移除尾部,异常会报错

E pollLast();//移除尾部,异常不报错

}

可以将上面的方法画成以下表格,只不过Deque是有头部和尾部的

操作

抛出异常

返回特殊值

插入

add()

offer()

删除

remove()

poll()

查询

element()

peek()

ArrayDeque是什么

实现于Deque,拥有队列或者栈特性的接口

实现于Cloneable,拥有克隆对象的特性

实现于Serializable,拥有序列化的能力

public class ArrayDeque extends AbstractCollection

implements Deque, Cloneable, Serializable{}

ArrayDeque的成员变量

//数组存储元素

transient Object[] elements;

//头部元素索引

transient int head;

//尾部元素索引

transient int tail;

//最小容量

private static final int MIN_INITIAL_CAPACITY = 8;

ArrayDeque底层使用数组存储元素,同时还使用head和tail来表示索引,但注意tail不是尾部元素的索引,而是尾部元素的下一位,即下一个将要被加入的元素的索引

ArrayDeque的初始化

public ArrayDeque() {

elements = new Object[16];

}

public ArrayDeque(int numElements) {

allocateElements(numElements);

}

public ArrayDeque(Collection extends E> c) {

allocateElements(c.size());

addAll(c);

}

private void allocateElements(int numElements) {

int initialCapacity = MIN_INITIAL_CAPACITY;

// Find the best power of two to hold elements.

// Tests “<=” because arrays aren’t kept full.

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 = new Object[initialCapacity];

}

在初始化中,数组要求的大小必须为2^n,所以有这么一个算法,如果当前的大小大于默认规定的大小时,就会去计算出新的大小,那么这个计算过程是怎么样的呢?我们举一个例子进行分析

如果initialCapacity为10的时候,那么二进制为 1010

经过initialCapacity |= (initialCapacity >>> 1)时,那么二进制为 1010 | 0101 = 1111

经过initialCapacity |= (initialCapacity >>> 2)时,那么二进制为 1111 | 0011 = 1111

后面计算的结果都是1111,可以理解为将二进制的低位数都补上1,这样出来的结果都是2^n-1

最后initialCapacity++,2^n-1+1出来的结果就是2^n

这里又有人会有疑问了,为什么initialCapacity>>>16,右移到5位就可以结束呢?那是因为用的是|=符号,从右移1位到5位累加,其实就是整体右移了15位,刚好int值是16位的数,这就刚好满足16位二进制的低位都被补上了1

ArrayDeque的插入

public void addFirst(E e) {

if (e == null)

throw new NullPointerException();

elements[head = (head – 1) & (elements.length – 1)] = e;

if (head == tail)

doubleCapacity();

}

public void addLast(E e) {

if (e == null)

throw new NullPointerException();

//tail中保存的是即将加入末尾的元素的索引

elements[tail] = e;

//tail向后移动一位

if ( (tail = (tail + 1) & (elements.length – 1)) == head)

//tail和head相遇,空间用尽,需要扩容

doubleCapacity();

}

在存储的过程中,这里有个有趣的算法,就是tail的计算公式(tail = (tail + 1) & (elements.length – 1)),注意这里的存储采用的是环形队列的形式,也就是当tail到达容量最后一个的时候,tail就为等于0,否则tail的值tail+1

(tail = (tail + 1) & (elements.length – 1))

证明:(elements.length – 1) = 2^n-1 即二进制的所有低位都为1,假设为 11111111

假设:tail为最后一个元素,则(tail + 1)为 (11111111 + 1) = 100000000

结果:(tail + 1) & (elements.length – 1) = 000000000,tail下一个要添加的索引为0

其插入过程中,如果刚好是最后一个元素时,示例如下图

9855e1c4d672

ArrayDeque的扩容

private void doubleCapacity() {

assert head == tail; //扩容时头部索引和尾部索引肯定相等

int p = head;

int n = elements.length;

//头部索引到数组末端(length-1处)共有多少元素

int r = n – p; // number of elements to the right of p

//容量翻倍

int newCapacity = n << 1;

//容量过大,溢出了

if (newCapacity < 0)

throw new IllegalStateException(“Sorry, deque too big”);

//分配新空间

Object[] a = new Object[newCapacity];

//复制头部索引到数组末端的元素到新数组的头部

System.arraycopy(elements, p, a, 0, r);

//复制其余元素

System.arraycopy(elements, 0, a, r, p);

elements = a;

//重置头尾索引

head = 0;

tail = n;

}

其扩容的过程如下图

9855e1c4d672

ArrayDeque的删除

ArrayDeque支持从头尾两端移除元素,remove方法是通过poll来实现的。因为是基于数组的,在了解了环的原理后这段代码就比较容易理解了

public E pollFirst() {

int h = head;

@SuppressWarnings(“unchecked”)

E result = (E) elements[h];

// Element is null if deque empty

if (result == null)

return null;

elements[h] = null; // Must null out slot

head = (h + 1) & (elements.length – 1);

return result;

}

public E pollLast() {

int t = (tail – 1) & (elements.length – 1);

@SuppressWarnings(“unchecked”)

E result = (E) elements[t];

if (result == null)

return null;

elements[t] = null;

tail = t;

return result;

}

ArrayDeque的查询

@SuppressWarnings(“unchecked”)

public E peekFirst() {

// elements[head] is null if deque empty

return (E) elements[head];

}

@SuppressWarnings(“unchecked”)

public E peekLast() {

return (E) elements[(tail – 1) & (elements.length – 1)];

}

总结

ArrayDeque是Deque 接口的一种具体实现,是依赖于可变数组来实现的。ArrayDeque 没有容量限制,可根据需求自动进行扩容。ArrayDeque 可以作为栈来使用,效率要高于Stack;ArrayDeque 也可以作为队列来使用,效率相较于基于双向链表的LinkedList也要更好一些

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/191355.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • Matlab保存图像的5种方法「建议收藏」

    Matlab保存图像的5种方法「建议收藏」此博客转自:https://blog.csdn.net/holybin/article/details/39502077,另外我补充了一些实验结果。1、使用imwrite函数如图像是img,则可以使用imwrite(img,’result.jpg’);这种方法保存图像大小和显示的大小是一样的。下面的方法得到的图像和原图像的大小不一样;下面是用该方法保存的图片我们注意到,用imwrite保存的图…

  • pdf拆分保留书签_pdf补丁

    pdf拆分保留书签_pdf补丁PDF补丁丁0.2.7.2版软件已经更新,请在博客首页(http://pdfpatcher.cnblogs.com)下载最新版。2010年6月11日更新功能介绍PDF补丁丁是一个用于修改PDF文件信息的工具。它具有以下功能:生成PDF文件:通过导入一批图片或已有PDF文件,生成包含图片及已有PDF文件指定页面范围的PDF文件。在生成文件时还可挂上书签。用此功能…

  • 算法(一)时间复杂度「建议收藏」

    算法(一)时间复杂度「建议收藏」算法很重要,但是由于做移动开发并不经常用到,所以很多同学早就将算法打了个大礼包送还给了老师了,况且很多同学并没有学习过算法。这个系列就让对算法头疼的同学能快速的掌握基本的算法。过年放假阶段玩了会游戏NBA2K17的生涯模式,没有比赛的日子也都是训练,而且这些训练都是自发的,没有人逼你,从早上练到晚上,属性也不涨,但是如果日积月累,不训练和训练的人的属性值就会产生较大差距。这个突然让我意识到

  • 一维卷积神经网络案例_matlab 卷积神经网络

    一维卷积神经网络案例_matlab 卷积神经网络基于一维卷积神经网络对机械振动信号进行分类并加以预测*使用一维卷积神经网络训练振动信号进行二分类2020年7月16日,一学期没等到开学,然而又放假了。总览CSDN中大多数卷积神经网络都是对二维图片进行分类的,而图片也都是常见的猫狗分类,minst手写数字分类。一维卷积神经网络的使用非常少见,有也是IDMB情感分类,和鸢尾花分类的。作者研究生就读于河北一所双飞,全国排名270多,哈哈哈,不吹不黑。在网上翻来翻去找不到一篇可以利用的代码去研究我的机械故障诊断,后来在无奈下到某宝搜寻到一段代码,可以利用

  • AssertValid函数学习 .「建议收藏」

    AssertValid函数学习 .「建议收藏」转自http://tsitao.blog.163.com/blog/static/29795822006914105840496/ VC的调试中,AssertValid和Dump函数的应用CObject::AssertValid成员函数提供对对象内部状态的运行时检查。尽管从CObject派生类时不需要重写AssertValid,但可以通过重写使您的类更安全可靠。Asse

  • Android 打包出现jdk版本错误的问题

    Android 打包出现jdk版本错误的问题

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号