另:Java多线程(6)之Deque与LinkedBlockingDeque深入分析(转)
ArrayDeque类实现Queue,Deque接口。
对于数组实现的Deque来说,数据结构上比较简单,只需要一个存储数据的数组以及头尾两个索引即可。由于数组是固定长度的,所以很容易就得到数组的头和尾,那么对于数组的操作只需要移动头和尾的索引即可。
特别说明的是ArrayDeque并不是一个固定大小的队列,每次队列满了以后就将队列容量扩大一倍(doubleCapacity()),因此加入一个元素总是能成功,而且也不会抛出一个异常。也就是说ArrayDeque是一个没有容量限制的队列。
同样继续性能的考虑,使用System.arraycopy复制一个数组比循环设置要高效得多。
ArrayDeque不是线程安全的。
ArrayDeque不可以存取null元素,因为系统根据某个位置是否为null来判断元素的存在。
当作为栈使用时,性能比Stack好;
当作为队列使用时,性能比LinkedList好。
因为栈Stack继承了Vector,是线程安全的
总结:
1、队列满了后自动扩容,因此新增总会成功
2、head 为第一个元素的索引
tail 为下个要添加元素的位置,为末尾元素的索引 + 1
因此,首元素为element[head],未元素为element[tail-1]
3、
头部添加元素e时:
head = (head - 1)
elements[head】 = e
尾部添加元素e时:
是将e 赋值给elements[tail] 即elements[tail] = e;
tail = (tail + 1) ,指向下个要添加元素的位置
添加完之后都需要判断是否需要扩容。
头部删除元素时:
elements[head] = null;
head = (head + 1)
尾部删除元素时:
int t = (tail - 1) // 处理临界情况(当tail为0时),与后的结果为elements.length - 1。
elements[t] = null;
tail = t
看了ArrayDeque类的源码。有以下几点总结:
1)ArrayDeque有两个类属性,head和tail,两个指针。
2)ArrayDeque通过一个数组作为载体,其中的数组元素在add等方法执行时不移动,发生变化的只是head和tail指针,而且指针是循环变化,数组容量不限制。
3)offer方法和add方法都是通过其中的addLast方法实现,每添加一个元素,就把元素加到数组的尾部,此时,head指针没有变化,而tail指针加一,因为指针是循环加的,所以当tail追上head((this.tail = this.tail + 1 & this.elements.length - 1) == this.head)时,数组容量翻一倍,继续执行。
4)remove方法和poll方法都是通过其中的pollFirst方法实现,每移除一个元素,该元素所在位置变成null,此时,tail指针没有变化,而head指针加一,当数组中没有数据时,返回null。
5)因为ArrayDeque不是线程安全的,所以,用作堆栈时快于 Stack,在用作队列时快于 LinkedList。
1. 两个重要的索引:head和tail
- // 第一个元素的索引
- private transient int head;
- // 下个要添加元素的位置,为末尾元素的索引 + 1
- private transient int tail;
2. 构造方法
- public ArrayDeque() {
- elements = (E[]) new Object[16]; // 默认的数组长度大小
- }
- public ArrayDeque(int numElements) {
- allocateElements(numElements); // 需要的数组长度大小
- }
- public ArrayDeque(Collection<? extends E> c) {
- allocateElements(c.size()); // 根据集合来分配数组大小
- addAll(c); // 把集合中元素放到数组中
- }
3. 分配合适大小的数组
- private void allocateElements(int numElements) {
- int initialCapacity = MIN_INITIAL_CAPACITY;
- // 找到大于需要长度的最小的2的幂整数。
- // 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 = (E[]) new Object[initialCapacity];
- }
4. 扩容
- // 扩容为原来的2倍。
- 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和tail已经重合了,说明tail是在head的左边。
- System.arraycopy(elements, p, a, 0, r); // 拷贝原数组从head位置到结束的数据
- System.arraycopy(elements, 0, a, r, p); // 拷贝原数组从开始到head的数据
- elements = (E[])a;
- head = 0; // 重置head和tail为数据的开始和结束索引
- tail = n;
- }
- // 拷贝该数组的所有元素到目标数组
- private <T> T[] copyElements(T[] a) {
- if (head < tail) { // 开始索引大于结束索引,一次拷贝
- System.arraycopy(elements, head, a, 0, size());
- } else if (head > tail) { // 开始索引在结束索引的右边,分两段拷贝
- int headPortionLen = elements.length - head;
- System.arraycopy(elements, head, a, 0, headPortionLen);
- System.arraycopy(elements, 0, a, headPortionLen, tail);
- }
- return a;
- }
5. 添加元素
- public void addFirst(E e) {
- if (e == null)
- throw new NullPointerException();
- // 本来可以简单地写成head-1,但如果head为0,减1就变为-1了,和elements.length - 1进行与操作就是为了处理这种情况,这时结果为elements.length - 1。
- elements[head = (head - 1) & (elements.length - 1)] = e;
- if (head == tail) // head和tail不可以重叠
- doubleCapacity();
- }
- public void addLast(E e) {
- if (e == null)
- throw new NullPointerException();
- // tail位置是空的,把元素放到这。
- elements[tail] = e;
- // 和head的操作类似,为了处理临界情况 (tail为length - 1时),和length - 1进行与操作,结果为0。
- if ( (tail = (tail + 1) & (elements.length - 1)) == head)
- doubleCapacity();
- }
- public boolean offerFirst(E e) {
- addFirst(e);
- return true;
- }
- public boolean offerLast(E e) {
- addLast(e);
- return true;
- }
6. 删除元素
删除首尾元素:
- public E removeFirst() {
- E x = pollFirst();
- if (x == null)
- throw new NoSuchElementException();
- return x;
- }
- public E removeLast() {
- E x = pollLast();
- if (x == null)
- throw new NoSuchElementException();
- return x;
- }
- public E pollFirst() {
- int h = head;
- E result = elements[h]; // Element is null if deque empty
- if (result == null)
- return null;
- // 表明head位置已为空
- elements[h] = null; // Must null out slot
- head = (h + 1) & (elements.length - 1); // 处理临界情况(当h为elements.length - 1时),与后的结果为0。
- return result;
- }
- public E pollLast() {
- int t = (tail - 1) & (elements.length - 1); // 处理临界情况(当tail为0时),与后的结果为elements.length - 1。
- E result = elements[t];
- if (result == null)
- return null;
- elements[t] = null;
- tail = t; // tail指向的是下个要添加元素的索引。
- return result;
- }
删除指定元素:
- public boolean removeFirstOccurrence(Object o) {
- if (o == null)
- return false;
- int mask = elements.length - 1;
- int i = head;
- E x;
- while ( (x = elements[i]) != null) {
- if (o.equals(x)) {
- delete(i);
- return true;
- }
- i = (i + 1) & mask; // 从头到尾遍历
- }
- return false;
- }
- public boolean removeLastOccurrence(Object o) {
- if (o == null)
- return false;
- int mask = elements.length - 1;
- int i = (tail - 1) & mask; // 末尾元素的索引
- E x;
- while ( (x = elements[i]) != null) {
- if (o.equals(x)) {
- delete(i);
- return true;
- }
- i = (i - 1) & mask; // 从尾到头遍历
- }
- return false;
- }
- private void checkInvariants() { // 有效性检查
- assert elements[tail] == null; // tail位置没有元素
- assert head == tail ? elements[head] == null :
- (elements[head] != null &&
- elements[(tail - 1) & (elements.length - 1)] != null); // 如果head和tail重叠,队列为空;否则head位置有元素,tail-1位置有元素。
- assert elements[(head - 1) & (elements.length - 1)] == null; // head-1的位置没有元素。
- }
- private boolean delete(int i) {
- checkInvariants();
- final E[] elements = this.elements;
- final int mask = elements.length - 1;
- final int h = head;
- final int t = tail;
- final int front = (i - h) & mask; // i前面的元素个数
- final int back = (t - i) & mask; // i后面的元素个数
- // Invariant: head <= i < tail mod circularity
- if (front >= ((t - h) & mask)) // i不在head和tail之间
- throw new ConcurrentModificationException();
- // Optimize for least element motion
- if (front < back) { // i的位置靠近head,移动开始的元素,返回false。
- if (h <= i) {
- System.arraycopy(elements, h, elements, h + 1, front);
- } else { // Wrap around
- System.arraycopy(elements, 0, elements, 1, i);
- elements[0] = elements[mask]; // 处理边缘元素
- System.arraycopy(elements, h, elements, h + 1, mask - h);
- }
- elements[h] = null;
- head = (h + 1) & mask; // head位置后移
- return false;
- } else { // i的位置靠近tail,移动末尾的元素,返回true。
- if (i < t) { // Copy the null tail as well
- System.arraycopy(elements, i + 1, elements, i, back);
- tail = t - 1;
- } else { // Wrap around
- System.arraycopy(elements, i + 1, elements, i, mask - i);
- elements[mask] = elements[0];
- System.arraycopy(elements, 1, elements, 0, t);
- tail = (t - 1) & mask;
- }
- return true;
- }
- }
示意图:
7. 获取元素
- public E getFirst() {
- E x = elements[head];
- if (x == null)
- throw new NoSuchElementException();
- return x;
- }
- public E getLast() {
- E x = elements[(tail - 1) & (elements.length - 1)]; // 处理临界情况(当tail为0时),与后的结果为elements.length - 1。
- if (x == null)
- throw new NoSuchElementException();
- return x;
- }
- public E peekFirst() {
- return elements[head]; // elements[head] is null if deque empty
- }
- public E peekLast() {
- return elements[(tail - 1) & (elements.length - 1)];
- }
8. 队列操作
- public boolean add(E e) {
- addLast(e);
- return true;
- }
- public boolean offer(E e) {
- return offerLast(e);
- }
- public E remove() {
- return removeFirst();
- }
- public E poll() {
- return pollFirst();
- }
- public E element() {
- return getFirst();
- }
- public E peek() {
- return peekFirst();
- }
9. 栈操作
- public void push(E e) {
- addFirst(e);
- }
- public E pop() {
- return removeFirst();
- }
10. 集合方法
- public int size() {
- return (tail - head) & (elements.length - 1); // 和elements.length - 1进行与操作是为了处理当tail < head时的情况。
- }
- public boolean isEmpty() {
- return head == tail; // tail位置的元素一定为空,head和tail相等,也为空。
- }
- // 向前迭代器
- public Iterator<E> iterator() {
- return new DeqIterator();
- }
- // 向后迭代器
- public Iterator<E> descendingIterator() {
- return new DescendingIterator();
- }
- private class DeqIterator implements Iterator<E> {
- private int cursor = head;
- private int fence = tail; // 迭代终止索引,同时也为了检测并发修改。
- private int lastRet = -1; // 最近的next()调用返回的索引。据此可以定位到需要删除元素的位置。
- public boolean hasNext() {
- return cursor != fence;
- }
- public E next() {
- if (cursor == fence)
- throw new NoSuchElementException();
- E result = elements[cursor];
- // This check doesn't catch all possible comodifications,
- // but does catch the ones that corrupt traversal
- if (tail != fence || result == null)
- throw new ConcurrentModificationException();
- lastRet = cursor;
- cursor = (cursor + 1) & (elements.length - 1); // 游标位置加1
- return result;
- }
- public void remove() {
- if (lastRet < 0)
- throw new IllegalStateException();
- if (delete(lastRet)) { // 如果将元素从右往左移,需要将游标减1。
- cursor = (cursor - 1) & (elements.length - 1); // 游标位置回退1。
- fence = tail; // 重置阀值。
- }
- lastRet = -1;
- }
- }
- private class DescendingIterator implements Iterator<E> {
- private int cursor = tail; // 游标开始索引为tail
- private int fence = head; // 游标的阀值为head
- private int lastRet = -1;
- public boolean hasNext() {
- return cursor != fence;
- }
- public E next() {
- if (cursor == fence)
- throw new NoSuchElementException();
- cursor = (cursor - 1) & (elements.length - 1); // tail是下个添加元素的位置,所以要减1才是尾节点的索引。
- E result = elements[cursor];
- if (head != fence || result == null)
- throw new ConcurrentModificationException();
- lastRet = cursor;
- return result;
- }
- public void remove() {
- if (lastRet < 0)
- throw new IllegalStateException();
- if (!delete(lastRet)) { // 如果从左往右移,需要将游标加1。
- cursor = (cursor + 1) & (elements.length - 1);
- fence = head;
- }
- lastRet = -1;
- }
- }
- public boolean contains(Object o) {
- if (o == null)
- return false; // ArrayDeque不可以存储null元素
- int mask = elements.length - 1;
- int i = head;
- E x;
- while ( (x = elements[i]) != null) {
- if (o.equals(x))
- return true;
- i = (i + 1) & mask; // 处理临界情况
- }
- return false;
- }
- public boolean remove(Object o) {
- return removeFirstOccurrence(o);
- }
- public void clear() {
- int h = head;
- int t = tail;
- if (h != t) { // clear all cells
- head = tail = 0; // 重置首尾索引
- int i = h;
- int mask = elements.length - 1;
- do {
- elements[i] = null; // 清除元素
- i = (i + 1) & mask;
- } while (i != t);
- }
- }
- public Object[] toArray() {
- return copyElements(new Object[size()]); // 把所有元素拷贝到新创建的Object数组上,所以对返回数组的修改不会影响该双端队列。
- }
- public <T> T[] toArray(T[] a) {
- int size = size();
- if (a.length < size) // 目标数组大小不够
- a = (T[])java.lang.reflect.Array.newInstance(
- a.getClass().getComponentType(), size); // 利用反射创建类型为T,大小为size的数组。
- yElements(a); // 拷贝所有元素到目标数组。
- if (a.length > size)
- a[size] = null; // 结束标识
- return a;
- }
11. Object方法
- public ArrayDeque<E> clone() {
- try {
- ArrayDeque<E> result = (ArrayDeque<E>) super.clone();
- result.elements = Arrays.copyOf(elements, elements.length); // 深度复制。
- return result;
- } catch (CloneNotSupportedException e) {
- throw new AssertionError();
- }
- }
来源:http://czj4451.iteye.com/blog/1688693
相关推荐
主要介绍了java.util.ArrayDeque类使用方法,java.util.ArrayDeque类提供了可调整大小的阵列,并实现了Deque接口,感兴趣的小伙伴们可以参考一下
主要介绍了Java集合ArrayDeque类实例分析的相关资料,需要的朋友可以参考下
主要介绍了Java容器类源码详解 Deque与ArrayDeque,Deque 接口继承自 Queue接口,但 Deque 支持同时从两端添加或移除元素,因此又被成为双端队列。,需要的朋友可以参考下
AbstractQueue 抽象类LinkedList ArrayDeque PriorityQueue 反射的思想及作用 反射的基本使用 获取类的 Class 对象构造类的实例化对象获取-个类的所有信息 获取类中的变量(Field) 获取类中的方法(Method) 获取类的...
GetTestieCollections 编写一些练习Collections类的测试 创建一个项目,为每个Collections类编写1或2个测试。 找出最常见,最有用的方法,然后在为该... 对于Deque接口, ArrayDeque是最常用的实现。 还包括针对Vecto
每天一道面试题,周五冲冲冲!...- 常见实现类有LinkedList、ArrayDeque和PriorityQueue等。 4. Map(映射): - 使用键值对(key-value)的方式存储元素。 - 键是唯一的,不允许重复,每个键关联一个值。
ArrayList、LinkedList、ArrayDeque、PriorityQueue、HashMap、LinkedHashMap、TreeMap 及并发容器类等。 3. 并发 并发:线程基础、JMM、AQS、CAS、锁与线程安全(Synchronized、ReentrantLock)、JUC、线程池、定时...
当你需要使用栈或者队列时,可以考虑使用LinkedList,一方面是因为Java官方已经声明不建议使用Stack类,更遗憾的是,Java里根本没有一个叫做Queue的类(它是个接口名字)。关于栈或队列,现在的是ArrayDeque,它有着...
kotlin类的SAM转换 显式API模式 尾随逗号 表达式中断并继续 混合名称和位置参数 命名约定:*或Null max和min函数在1.4中已弃用。 应该使用maxOrNull / minOrNull代替 maxBy与maxOf minBy与minOf 命名约定:*...
给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。... // Stack 这个类 Java 的文档里推荐写成 Deque stack = new ArrayDeque(); // 注意:只使用 stack 相关的接口 Deque stack = new Ar
类加载过程 集合 异常 锁 线程池 IO JVM import sun.music.Unsafe 操作系统 CPU的组成与功能 内存管理 进程管理 常问问题 计算机网络 OSI TCP/IP UDP 五层协议 浏览器输入网址到返回页面内容的全部过程 设计模式 ...
ArrayDeque是基于循环拆分的双向数组,可扩容,拆分栈和样式。 平均情况下,作为栈比Stack效率更高,作为层次比LinkedList效率更高。 对于整型元素而言,最小堆。 放 | 设置中位数出现重复元素。 HashSet完全依赖...
ArrayDeque 而不是 Stack 类。 找到第一个未排序元素的索引:(参见 Stack 解决方案) 要扁平化嵌套数据结构,可以使用迭代器堆栈: 数组 从 1..n 中查找重复/缺失的数字,其中 n 是数组的长度,使用元素本身作为...
内部类,TreeNode 图节点表示 Java 8 特性 队列、堆栈、双端队列 树结构,树集 堆,优先队列 Guava(谷歌核心 Java 库 链表,ArrayDeque 哈希,哈希表 LRUCache 缓存,LinkedHashMap 其他开源 Java 库 课程大纲 - ...
**类DWGraph_DS我定义了单向加权图,然后在其上定义了不同的方法。 我添加了一个节点,连接了这些节点(添加了边),删除了边,删除了节点,返回了边的长度,以及返回了图中节点数和图中边数的方法。 另外,我定义...