- 浏览: 1238680 次
- 性别:
- 来自: 杭州
文章分类
- 全部博客 (193)
- ant/maven (6)
- algorithm (5)
- tomcat/weblogic/jboss (6)
- javascript/jquery (13)
- java (33)
- flex/flash (0)
- JPA/Hibernate/myBatis (18)
- java concurrent (7)
- test (2)
- windows/linux (6)
- java collection (7)
- design pattern (2)
- life/health (3)
- database (12)
- IDE (4)
- spring/ejb (20)
- html/css/ckeditor (7)
- jsp/servlet (3)
- java io (13)
- java security (4)
- jni (0)
- svn/git (2)
- english (2)
- java jmx (1)
- xml (1)
- struts/springmvc (9)
- middleware (2)
- cache (1)
- cglib (3)
最新评论
-
jlotusYo:
博主,真感谢。
Java 密码扩展无限制权限策略文件 -
senninha:
这个。。是api说明吧。。
ScheduledExecutorService 源码分析 -
zoutao2008:
请问大文件如何处理?按你这种方式的话,文件超过200M时就会报 ...
hessian系列之二:上传文件 -
lwj1113:
lwj1113 写道谢谢博主这么细致的demo;在系列五中通过 ...
myBatis系列之五:与Spring3集成 -
lwj1113:
谢谢博主这么细致的demo;在系列五中通过testng测试类跑 ...
myBatis系列之五:与Spring3集成
ArrayDeque不是线程安全的。
ArrayDeque不可以存取null元素,因为系统根据某个位置是否为null来判断元素的存在。
当作为栈使用时,性能比Stack好;当作为队列使用时,性能比LinkedList好。
1. 两个重要的索引:head和tail
2. 构造方法
3. 分配合适大小的数组
4. 扩容
5. 添加元素
6. 删除元素
删除首尾元素:
删除指定元素:
示意图:
7. 获取元素
8. 队列操作
9. 栈操作
10. 集合方法
11. Object方法
ArrayDeque不可以存取null元素,因为系统根据某个位置是否为null来判断元素的存在。
当作为栈使用时,性能比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的数组。 copyElements(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(); } }
发表评论
-
TreeMap 源码分析
2013-06-25 10:20 01. 构造函数 public TreeMap() ... -
AbstractList 源码分析
2012-10-18 09:56 0public int hashCode() { ... -
AbstractMap 源码分析
2012-10-18 09:48 0public boolean equals(Obj ... -
LinkedHashMap 源码分析
2012-07-06 09:59 1600Map 接口的哈希表和链接列表实现,具有可预知的迭代顺序。此实 ... -
Arrays 的使用
2012-06-02 14:13 10611. 比较数组 在两个数组上调用equals,比较的是两个数 ... -
LinkedList源码分析
2012-09-02 22:20 1359LinkedList适用于添加、删除比较频繁,随机访问不多的场 ... -
HashMap源码分析
2012-11-08 15:17 1324size记录了所有键值对的数目,包括数组(内部实现)中的和 ... -
ArrayList 源码分析
2012-04-24 15:27 1407ArrayList的内部实现是Obje ... -
List 迭代过程中删除或添加元素
2012-04-04 21:54 48751. List 迭代过程中删除元素采用list.remove( ...
相关推荐
ArrayDeque是一种以数组方式实现的双端队列,它是非线程安全的。下面小编和大家一起学习一下
arraydeque
主要介绍了Java集合ArrayDeque类实例分析的相关资料,需要的朋友可以参考下
ArrayDeque 是Java中的双向队列(deque)实现,它基于数组实现并可以高效地在两端进行插入和删除操作。 以下是关于 ArrayDeque 的一些重要信息: 双向队列特性:ArrayDeque 支持在队列的两端进行元素的插入和删除...
主要介绍了Java容器类源码详解 Deque与ArrayDeque,Deque 接口继承自 Queue接口,但 Deque 支持同时从两端添加或移除元素,因此又被成为双端队列。,需要的朋友可以参考下
主要介绍了java.util.ArrayDeque类使用方法,java.util.ArrayDeque类提供了可调整大小的阵列,并实现了Deque接口,感兴趣的小伙伴们可以参考一下
主要为大家详细介绍了Java ArrayDeque的使用方法,感兴趣的小伙伴们可以参考一下
arraydeque固定容量的循环缓冲区。 需要Rust 1.20+。 这个箱子的灵感来自bluss / arrayvec文档的用法首先,添加fol arraydeque一个具有固定容量的循环缓冲区。 需要Rust 1.20+。 首先,将以下内容添加到Cargo.toml中...
主要介绍了Java ArrayDeque实现Stack功能的方法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
双端队列在没有和库的Java中实现ArrayDeque和LinkedListDeque。
目录 Java 数据类型 类加载过程 集合 异常 锁 线程池 IO JVM import sun.music.Unsafe 操作系统 ...ArrayList源码剖析 LinkedList源码剖析 ArrayDeque源码剖析 PriorityQueue源码剖析 TreeSet和TreeM
bitset源码Java源码分析 基础集合列表 ArrayList (done) Vector (done) LinkedList (done) Stack (done) ReferenceQueue (done) ArrayDeque (done) Set HashSet (done) TreeSet (done) LinkedHashSet (done) BitSet ...
1、用了Java两种方式,都挺好的,ArrayDeque的性能比LinkedList要强很多(都可以做队列),所以我就都写了一下,传入根结点即可(没有用数组存二叉树) /** * 层序遍历,使用了ArrayDeque,一个循环数组,性能很好...
前面以Java ArrayDeque为例讲解了Stack和Queue,其实还有一种特殊的队列叫做PriorityQueue,即优先队列。优先队列的作用是能保证每次取出的元素都是队列中权值小的(Java的优先队列每次取小元素,C++的优先队列...
总体介绍 LinkedList同时实现了List接口和Deque...关于栈或队列,现在的是ArrayDeque,它有着比LinkedList(当作栈或队列使用时)有着更好的性能。 LinkedList底层通过双向链表实现,本节将着重讲解插入和删
每天一道面试题,周五冲冲冲!...- 常见实现类有LinkedList、ArrayDeque和PriorityQueue等。 4. Map(映射): - 使用键值对(key-value)的方式存储元素。 - 键是唯一的,不允许重复,每个键关联一个值。
ArrayDeque实现了Deque接口,LinkedList实现了Deque,List接口 (1)对比: ArrayDeque 为数组结构,插入元素不能为null,无法确定数据量时,后期扩容会影响效率 LinkedList 链表结构,插入元素不能为null,无法确定...
典型相关分析matlab实现代码 * * * * * * * * * * * * * * * * * * * * * * * * * * 1. 判断括号是否有效 -> ValidParentheses HashMap 还有 Stack 栈 最佳实践,Deque = Stack public static boolean isValid...