大家好,又见面了,我是你们的朋友全栈君。
美人如斯!
ArrayDeque是java中对双端队列的线性实现
Stack
,当用于队列时,性能优于LinkedList
null
注意: ArrayDeque的迭代器和大多数容器迭代器一样,都是快速失败(fail-fast),但是程序不能利用这个特性决定是或否进行了并发操作。
为了更好的理解使用线性数组实现的双端队列,这里我们先来图解线性数组实现基本数据结构-队列:
如上图所示,head指向队头,入队加元素时,tail队尾向后移动,出队时从head出取出元素并移除,这样就利用了线性数组实现先进先出的队列数据结构,当head等于tail时,则表示队列为空。 但是这样存在问题:当不断出队时,head向后移动,前面空出来的空间就被浪费,导致不断入队时,需要数组扩容,出队时造成大量空间无法使用,空间利用率低下! 假设,如果能将前面空出来的空间也利用起来进行存储末尾的元素,则空间使用率将提高,这里就需要有个循环的思维,把这种线性的弯曲成一个圆环,这样就可以反复使用空出来的空间,入队时使用出队空余出来的空间,就解决以上的问题,图解如下:
同样,当head等于tail时,则表示循环队列为空。head和tail也是循环的,像钟表中的时针,具有周期性。这里head和tail需要对长度lenth取模,这样head和tail将一直在长度范围内,可以作为数组的下标。
对于如何将数据分布到相应大小的连续空间中,常用的方式就是取模运算,即position=index%len,利用整数倍的周期性,将剩余的部分作为空间索引。
1. ArrayDeque数据域
/**
* The array in which the elements of the deque are stored.
* The capacity of the deque is the length of this array, which is
* always a power of two. The array is never allowed to become
* full, except transiently within an addX method where it is
* resized (see doubleCapacity) immediately upon becoming full,
* thus avoiding head and tail wrapping around to equal each
* other. We also guarantee that all array cells not holding
* deque elements are always null.
*/
transient Object[] elements; // non-private to simplify nested class access
/**
* The index of the element at the head of the deque (which is the
* element that would be removed by remove() or pop()); or an
* arbitrary number equal to tail if the deque is empty.
*/
transient int head;
/**
* The index at which the next element would be added to the tail
* of the deque (via addLast(E), add(E), or push(E)).
*/
transient int tail;
/**
* The minimum capacity that we'll use for a newly created deque.
* Must be a power of 2.
*/
private static final int MIN_INITIAL_CAPACITY = 8;
首先看下ArrayDeque持有的成员域,其中非常核心的是elements,head,tail三个。下面逐一介绍:
add
方法中扩容,使得头head和tail不会缠绕在一起(即head增长或不会超过tail,head减小时不会溢出到tail),这里队列长度是2的幂次方的原因后续会阐明;2. 构造函数
/**
* Constructs an empty array deque with an initial capacity
* sufficient to hold 16 elements.
*/
public ArrayDeque() {
elements = new Object[16];
}
/**
* Constructs an empty array deque with an initial capacity
* sufficient to hold the specified number of elements.
*
* @param numElements lower bound on initial capacity of the deque
*/
public ArrayDeque(int numElements) {
allocateElements(numElements);
}
/**
* Constructs a deque containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator. (The first element returned by the collection's
* iterator becomes the first element, or <i>front</i> of the
* deque.)
*
* @param c the collection whose elements are to be placed into the deque
* @throws NullPointerException if the specified collection is null
*/
public ArrayDeque(Collection<? extends E> c) {
allocateElements(c.size());
addAll(c);
}
numElements
创建队列,如果numElements
小于8,则队列初始化大小为8;如果numElements
大于8,则初始化大小为大于numElements
的最小2的幂次方。如:numElements=17,则初始化大小为32这里重点看下第二个构造器的过程。其中调用allocateElements(numElements)
方法,该方法用来实现容量分配,下面看下内部具体实现:
/**
* Allocates empty array to hold the given number of elements.
*
* @param numElements the number of elements to hold
*/
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];
}
首先判断指定大小numElements与MIN_INITIAL_CAPACITY
的大小关系。如果小于MIN_INITIAL_CAPACITY
,则直接分配大小为MIN_INITIAL_CAPACITY
的数组;如果大于MIN_INITIAL_CAPACITY
,则进行无符号右移操作,然后在加1,这样就可以寻找到大于numElements的最小2的幂次方。
原理:无符号右移再进行按位或操作,就是将其低位全部补成1,然后再自加加一次,就是再向前进一位。这样就能得到其最小的2次幂。之所以需要最多移16位,是为了能够处理大于2^16次方数。
最后再判断值是否小于0,因为如果初始值在int最大值2^31-1和2^30之间,进行一系列移位操作后将得到int最大值,再加1,则溢出变成负数,所以需要检测临界值,然后再右移1位!!!
接下来再来分析下ArrayDeque的几个重要双端操作。对于双端队列有哪些重要的双端操作,可以移步至我的之前写的另一篇文章Java中Deque特性及API
在详细介绍ArrayDeque的重要API实现之前,以图解的方式看下ArrayDeque构造函数初始化出的队列的数据结构:
初始化ArrayDeque后,head和tail都是0,指向数组的0下标位置。在了解初始化后的数据构成后,再首先来看下addFirst方法
3. 重要行为
addFirst方法
/**
* Inserts the specified element at the front of this deque.
*
* @param e the element to add
* @throws NullPointerException if the specified element is null
*/
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
}
先用图解的方式分析下这个方法,在第一次调用这个方法后,数据变化如下:
根据图的变化来分析下代码实现。 首先判断插入元素是否为空,再计算即将插入的位置,计算出后将元素赋值给相应的槽位,最后再判断队列容量进行扩容。
下面再来看下扩容策略:
/**
* Doubles the capacity of this deque. Call only when full, i.e.,
* when head and tail have wrapped around to become equal.
*/
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];
System.arraycopy(elements, p, a, 0, r);
System.arraycopy(elements, 0, a, r, p);
elements = a;
head = 0;
tail = n;
}
如果从头端插入,则head继续逆时针旋转方式插入新元素。从以上图中不难看出addFirst是操作双端队列头端,且是逆时针方式旋转插入。接下来再看看从尾端插入的过程
addLast方法
/**
* Inserts the specified element at the end of this deque.
*
* <p>This method is equivalent to {@link #add}.
*
* @param e the element to add
* @throws NullPointerException if the specified element is null
*/
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
上述的addFirst是逆时针的插入方式,addLast刚好与其相反,即顺时针方向插入,且tail表示的是下一个插入的元素的位置。
pollFirst方法
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;
}
null
注:读到这里,相信读者已经已经对双端队列的数据结构已经非常清晰,即双端操作的数组,tail向前(顺时针)移动即从尾端插入元素或者向后移动即从尾端移除元素,head向后(逆时针)移动即从头端插入元素或者向前移动即从头端移除元素。这几个过程正好具有FIFO和LIFO的特点,所以ArrayDeque既可以作为队列Queue又可以作为栈Stack。
pollLast方法
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的数据结构和tail的含义中,可以大致思考下,从尾端移除元素的过程。
null
以上的过程基就是ArrayDeque的工作原理的最基本实现,其他的行为大都是基于这些过程实现:
offer方法:内部调用offerLast插入元素,返回插入结果true/false add方法:内部调用addLast实现 poll方法:内部调用pollFirst实现 remove方法:内部调用removeFirst实现 peek方法:内部调用peekFirst实现 element方法:内部调用getFirst实现 pop方法:内部调用removeFirst实现 push方法:内部调用addFirst实现
这里不再详述每个操作的具体实现,因为这些操作都是基于addFirst、addLast、pollFirst和pollLast实现。具体调用这些基础行为实现的细节,读者可以阅读ArrayDeque源码。
参考:
位运算总结(按位与,或,异或) java int short long float double精度最大值整理
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/191212.html原文链接:https://javaforall.cn