另: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集合ArrayDeque类实例分析 Java集合ArrayDeque类实例分析主要介绍了ArrayDeque类的实现机理、基本特征和实现方法等相关知识点。 ArrayDeque类的继承结构 ArrayDeque类继承自AbstractCollection,实现了...
Java中的`java.util.ArrayDeque`类是一个高效且灵活的数据结构,它实现了`Deque`接口,同时也继承了`AbstractCollection`和`AbstractQueue`。`ArrayDeque`是一个基于可变数组的双端队列,它的主要特点是它使用一个...
3. **栈**:栈是一种后进先出(LIFO)的数据结构,Java中的栈可以使用ArrayDeque类或者Stack类实现。栈在函数调用、表达式求值等方面有广泛应用。 4. **队列**:队列是一种先进先出(FIFO)的数据结构,Java中的...
1. **ArrayDeque类**:Java集合框架提供了一个双端队列`ArrayDeque`,它可以被用作一个高效的栈。`ArrayDeque`继承自`AbstractCollection`,并实现了`Deque`接口,这个接口包含了栈的所有操作。创建一个栈并进行操作...
在Java中,除了LinkedList,还可以使用ArrayDeque类来实现栈和队列,ArrayDeque提供了更高效的操作,因为它基于数组而不是链表。 在实际应用中,LinkedList适合于频繁插入和删除的场景,因为这些操作的时间复杂度为...
栈是一种后进先出(LIFO)的数据结构,Java的ArrayDeque类可以作为栈来使用,提供了push和pop操作。 6. **队列**: 队列是一种先进先出(FIFO)的数据结构,Java的LinkedList或ArrayDeque类也可实现队列功能。 7...
Java中的栈可以使用ArrayDeque类或者Stack类来实现。栈的主要操作包括压入(push)、弹出(pop)和查看栈顶元素(peek)。 “队列”则是先进先出(FIFO)的数据结构,常见的应用包括任务调度和消息队列。Java提供了...
Java中,可以使用ArrayDeque类来实现栈。理解和实现基本的栈操作,如push、pop、peek等,是本章的重要内容。 4. **队列**:队列是先进先出(FIFO)的数据结构,常用于任务调度、消息传递等。Java的LinkedList类或...
- **ArrayDeque类**:ArrayDeque是Java集合框架的一部分,它是一个双端队列,但也可用作高效的栈。通过`push()`方法添加元素到栈顶,`pop()`方法移除并返回栈顶元素,`peek()`方法查看栈顶元素但不移除。 ```java...
队列是先进先出(FIFO)的数据结构,Java的LinkedList类可以方便地实现队列功能,或者使用ArrayDeque类的双端队列特性。 树是一种非线性的数据结构,二叉树是其中最简单的一种,每个节点最多有两个子节点。AVL树是...
Java的ArrayDeque类可以作为栈使用,提供push和pop等操作。此外,java.util.Stack类也是栈的实现,但效率较低。 4. **队列**:队列是一种先进先出(FIFO)的数据结构。Java提供了LinkedList类和ArrayDeque类来实现...
Java中,LinkedList或ArrayDeque类都可以实现队列,另外还有专门的Queue接口和其实现类如LinkedList、ArrayBlockingQueue等。 五、栈和队列的变种:堆 堆是一种特殊的树形数据结构,满足堆属性:父节点的键值总是...
Java中可以使用ArrayDeque类来实现栈的功能,也可以通过LinkedList类的push和pop方法操作。 队列是一种先进先出(FIFO)的数据结构,适用于处理一系列等待处理的任务,如任务调度。Java提供了LinkedList类和...
Java中可以使用LinkedList类或ArrayDeque类实现队列。 树是一种非线性数据结构,由节点和边构成,每个节点有零个或多个子节点。二叉树、二叉搜索树、平衡树(如AVL树和红黑树)是常见的树结构,它们在搜索、排序等...
在Java中,可以使用ArrayDeque类或LinkedList类来实现栈的功能。例如,使用push()方法添加元素,pop()方法移除并返回栈顶元素。 4. 算法: - 排序算法:常见的有冒泡排序、选择排序、插入排序、快速排序、归并排序...
Java中的ArrayDeque类可以被用作栈,提供高效的push和pop操作。 4. **队列**:队列是一种先进先出(FIFO)的数据结构,常用于任务调度和消息传递。Java中的LinkedList类和ArrayDeque类都可实现队列。 5. **堆**:...
Java中的ArrayDeque类可以作为栈使用。 4. 队列:先进先出(FIFO)的数据结构,常用操作是入队(enqueue)和出队(dequeue)。Java中的LinkedList或ArrayDeque类可实现队列。 5. 树:非线性数据结构,包含一个根...
Java的ArrayDeque类可以作为一个高效的栈实现。 4. **队列**:可能用于播放音频效果,如风声,因为它们遵循先进先出(FIFO)的原则。 5. **哈希表/映射**:可以用来关联每个荷花的位置与其颜色或状态,Java的...
在Java中,我们可以使用LinkedList类或者ArrayDeque类来实现队列。队列常用于任务调度、消息传递等场景。 3. **链表**: 链表不同于数组,它的元素在内存中不是连续存放的,每个元素(节点)包含数据和指向下一个...
在Java中,可以使用ArrayDeque类来实现栈,因为它提供了高效的栈操作: ```java import java.util.ArrayDeque; ArrayDeque<Integer> stack = new ArrayDeque(); stack.push(1); // 压栈 int topElement = stack....