死磕 java集合之ArrayDeque源码分析
问题
(1)什么是双端队列?
(2)ArrayDeque是怎么实现双端队列的?
(3)ArrayDeque是线程安全的吗?
(4)ArrayDeque是有界的吗?
简介
双端队列是一种特殊的队列,它的两端都可以进出元素,故而得名双端队列。
ArrayDeque是一种以数组方式实现的双端队列,它是非线程安全的。
继承体系
通过继承体系可以看,ArrayDeque实现了Deque接口,Deque接口继承自Queue接口,它是对Queue的一种增强。
public interface Deque<E> extends Queue<E> { // 添加元素到队列头 void addFirst(E e); // 添加元素到队列尾 void addLast(E e); // 添加元素到队列头 boolean offerFirst(E e); // 添加元素到队列尾 boolean offerLast(E e); // 从队列头移除元素 E removeFirst(); // 从队列尾移除元素 E removeLast(); // 从队列头移除元素 E pollFirst(); // 从队列尾移除元素 E pollLast(); // 查看队列头元素 E getFirst(); // 查看队列尾元素 E getLast(); // 查看队列头元素 E peekFirst(); // 查看队列尾元素 E peekLast(); // 从队列头向后遍历移除指定元素 boolean removeFirstOccurrence(Object o); // 从队列尾向前遍历移除指定元素 boolean removeLastOccurrence(Object o); // *** 队列中的方法 *** // 添加元素,等于addLast(e) boolean add(E e); // 添加元素,等于offerLast(e) boolean offer(E e); // 移除元素,等于removeFirst() E remove(); // 移除元素,等于pollFirst() E poll(); // 查看元素,等于getFirst() E element(); // 查看元素,等于peekFirst() E peek(); // *** 栈方法 *** // 入栈,等于addFirst(e) void push(E e); // 出栈,等于removeFirst() E pop(); // *** Collection中的方法 *** // 删除指定元素,等于removeFirstOccurrence(o) boolean remove(Object o); // 检查是否包含某个元素 boolean contains(Object o); // 元素个数 public int size(); // 迭代器 Iterator<E> iterator(); // 反向迭代器 Iterator<E> descendingIterator(); }
Deque中新增了以下几类方法:
(1)*First,表示从队列头操作元素;
(2)*Last,表示从队列尾操作元素;
(3)push(e),pop(),以栈的方式操作元素的方法;
源码分析
主要属性
// 存储元素的数组 transient Object[] elements; // non-private to simplify nested class access // 队列头位置 transient int head; // 队列尾位置 transient int tail; // 最小初始容量 private static final int MIN_INITIAL_CAPACITY = 8;
从属性我们可以看到,ArrayDeque使用数组存储元素,并使用头尾指针标识队列的头和尾,其最小容量是8。
主要构造方法
// 默认构造方法,初始容量为16 public ArrayDeque() { elements = new Object[16]; } // 指定元素个数初始化 public ArrayDeque(int numElements) { allocateElements(numElements); } // 将集合c中的元素初始化到数组中 public ArrayDeque(Collection<? extends E> c) { allocateElements(c.size()); addAll(c); } // 初始化数组 private void allocateElements(int numElements) { elements = new Object[calculateSize(numElements)]; } // 计算容量,这段代码的逻辑是算出大于numElements的最接近的2的n次方且不小于8 // 比如,3算出来是8,9算出来是16,33算出来是64 private static int calculateSize(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 } return initialCapacity; }
通过构造方法,我们知道默认初始容量是16,最小容量是8。
入队
入队有很多方法,我们这里主要分析两个,addFirst(e)和addLast(e)。
// 从队列头入队 public void addFirst(E e) { // 不允许null元素 if (e == null) throw new NullPointerException(); // 将head指针减1并与数组长度减1取模 // 这是为了防止数组到头了边界溢出 // 如果到头了就从尾再向前 // 相当于循环利用数组 elements[head = (head - 1) & (elements.length - 1)] = e; // 如果头尾挨在一起了,就扩容 // 扩容规则也很简单,直接两倍 if (head == tail) doubleCapacity(); } // 从队列尾入队 public void addLast(E e) { // 不允许null元素 if (e == null) throw new NullPointerException(); // 在尾指针的位置放入元素 // 可以看到tail指针指向的是队列最后一个元素的下一个位置 elements[tail] = e; // tail指针加1,如果到数组尾了就从头开始 if ( (tail = (tail + 1) & (elements.length - 1)) == head) doubleCapacity(); }
(1)入队有两种方式,从队列头或者从队列尾;
(2)如果容量不够了,直接扩大为两倍;
(3)通过取模的方式让头尾指针在数组范围内循环;
(4)x & (len - 1) = x % len,使用&的方式更快;
扩容
private void doubleCapacity() { assert head == tail; // 头指针的位置 int p = head; // 旧数组长度 int n = elements.length; // 头指针离数组尾的距离 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]; // 将旧数组head之后的元素拷贝到新数组中 System.arraycopy(elements, p, a, 0, r); // 将旧数组下标0到head之间的元素拷贝到新数组中 System.arraycopy(elements, 0, a, r, p); // 赋值为新数组 elements = a; // head指向0,tail指向旧数组长度表示的位置 head = 0; tail = n; }
扩容这里迁移元素可能有点绕,请看下面这张图来理解。
出队
出队同样有很多方法,我们主要看两个,pollFirst()和pollLast()。
// 从队列头出队 public E pollFirst() { int h = head; @SuppressWarnings("unchecked") // 取队列头元素 E result = (E) elements[h]; // 如果队列为空,就返回null 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]; // 如果队列为空返回null if (result == null) return null; // 将当前尾指针处置为空 elements[t] = null; // tail指向新的尾指针处 tail = t; // 返回取得的元素 return result; }
(1)出队有两种方式,从队列头或者从队列尾;
(2)通过取模的方式让头尾指针在数组范围内循环;
(3)出队之后没有缩容哈哈^^
栈
前面我们介绍Deque的时候说过,Deque可以直接作为栈来使用,那么ArrayDeque是怎么实现的呢?
public void push(E e) { addFirst(e); } public E pop() { return removeFirst(); }
是不是很简单,入栈出栈只要都操作队列头就可以了。
总结
(1)ArrayDeque是采用数组方式实现的双端队列;
(2)ArrayDeque的出队入队是通过头尾指针循环利用数组实现的;
(3)ArrayDeque容量不足时是会扩容的,每次扩容容量增加一倍;
(4)ArrayDeque可以直接作为栈使用;
彩蛋
双端队列与双重队列?
双端队列(Deque)是指队列的两端都可以进出元素的队列,里面存储的是实实在在的元素。
双重队列(Dual Queue)是指一种队列有两种用途,里面的节点分为数据节点和非数据节点,它是LinkedTransferQueue使用的数据结构。
还记得LinkedTransferQueue吗?点击链接直达【死磕 java集合之LinkedTransferQueue源码分析】。
欢迎关注我的公众号“彤哥读源码”,查看更多源码系列文章, 与彤哥一起畅游源码的海洋。

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
程序员笔记|循序渐进解读Oracle AWR性能分析报告
Oracle中的AWR,全称为Automatic Workload Repository,自动负载信息库。它收集关于特定数据库的操作统计信息和其他统计信息,Oracle以固定的时间间隔(默认为1个小时)为其所有重要的统计信息和负载信息执行一次快照,并将快照存放入AWR中。这些信息在AWR中保留指定的时间(默认为1周),然后执行删除。执行快照的频率和保持时间都是可以自定义的。 AWR的引入,为我们分析数据库提供了非常好的便利条件(这方面MySQL就相差了太多)。曾经有这样的一个比喻——“一个系统,就像是一个黑暗的大房间,系统收集的统计信息,就如同放置在房间不同位置的蜡烛,用于照亮这个黑暗大房间。Oracle,恰到好处地放置了足够的蜡烛(AWR),房间中只有极少的烛光未覆盖之处,性能瓶颈就容易定位。而对于蜡烛较少或是没有蜡烛的系统,性能优化就如同黑暗中的舞者。” 那如何解读AWR的数据呢?Oracle本身提供了一些报告,方便进行查看、分析。下面就针对最为常见的一种报告——《AWR数据库报告》进行说明。希望通过这篇文章,能方便大家更好地利用AWR,方便进行分析工作。 一、MAIN 1、Dat...
- 下一篇
TensorFlow 2.0+Keras 防坑指南
TensorFlow 2.0是对1.x版本做了一次大的瘦身,Eager Execution默认开启,并且使用Keras作为默认高级API, 这些改进大大降低的TensorFlow使用难度。 本文主要记录了一次曲折的使用Keras+TensorFlow2.0的BatchNormalization的踩坑经历,这个坑差点要把TF2.0的新特性都毁灭殆尽,如果你在学习TF2.0的官方教程,不妨一观。 问题的产生 从教程[1]https://www.tensorflow.org/alpha/tutorials/images/transfer_learning?hl=zh-cn(讲述如何Transfer Learning)说起: IMG_SHAPE = (IMG_SIZE, IMG_SIZE, 3) # Create the base model from the pre-trained model MobileNet V2 base_model = tf.keras.applications.MobileNetV2(input_shape=IMG_SHAPE, include_top=F...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- SpringBoot2整合MyBatis,连接MySql数据库做增删改查操作
- Windows10,CentOS7,CentOS8安装Nodejs环境
- CentOS8安装MyCat,轻松搞定数据库的读写分离、垂直分库、水平分库
- Red5直播服务器,属于Java语言的直播服务器
- Eclipse初始化配置,告别卡顿、闪退、编译时间过长
- SpringBoot2全家桶,快速入门学习开发网站教程
- CentOS7设置SWAP分区,小内存服务器的救世主
- CentOS7安装Docker,走上虚拟化容器引擎之路
- CentOS7编译安装Cmake3.16.3,解决mysql等软件编译问题
- Docker快速安装Oracle11G,搭建oracle11g学习环境