今天我们来说说ArrayDeque.很多人可能没用过甚至都没有听过这个类.当需要使用栈时,官
方已不推荐Stack,而是推荐使用效率更高的ArrayDeque(次选LinkedList).
概述
双端队列是一种两端皆可实现进出的特殊队列,而
ArrayDeque
便是Java中一个双端队列的实现.它内部基于数组存储数据,维护两个指针分别指向首尾,可以更高效的进行元素的插入和查找.其作为栈使用比
Stack
效率高,作为队列使用比
LinkedList
快,可以说
ArrayDeque
是用作队列,栈的不二选择.
源码分析
结构图
继承关系
public class ArrayDeque<E> extends AbstractCollection<E>
implements Deque<E>, Cloneable, Serializable{
AbstractCollection
是
Collection
接口唯一子类且是个抽象类,提供了对集合操作的基本实现.
ArrayDeque
实现了
Deque
接口,说明它是一个双端队列,支持首尾进出操作.
类中属性
/** 版本号 */
private static final long serialVersionUID = 2340985798034038923L;
/** 核心数组 (基于head&tail逻辑实现循环数组) **/
transient Object[] elements;
/** 头指针 **/
transient int head;
/** 尾指针(指向最后一个节点的下一个位置) **/
transient int tail;
/** 最小容量 (长度需保持2的幂,便于把求余操作转为移位操作) **/
private static final int MIN_INITIAL_CAPACITY = 8;
上述属性中
elements
就是存数据的核心数组,其大小始终为2的幂次方.这个数组每次都会在
add
方法中进行动态扩容,使
head
和
tail
不会交叉.
head
标识双端队列中头元素的位置.
tail
为双端队列的末端,始终是空的,每次尾部添加数据,
tail
都会往后移一位.
构造函数
/** 无参构造器, 默认初始容量16 **/
public ArrayDeque() {
elements = new Object[16];
}
/** 设置初始容量 **/
public ArrayDeque(int numElements) {
allocateElements(numElements);
}
/** 创建包含指定集合 **/
public ArrayDeque(Collection<? extends E> c) {
allocateElements(c.size());
addAll(c);
}
除了默认的无参构造器,其余两个都调用这么一个函数
allocateElements
,我们来看看它的实现:
/** 数组分配及大小调整 */
private void allocateElements(int numElements) {
// 最小容量
int initialCapacity = MIN_INITIAL_CAPACITY;
if (numElements >= initialCapacity) {
initialCapacity = numElements;
initialCapacity |= (initialCapacity >>> 1);
initialCapacity |= (initialCapacity >>> 2);
initialCapacity |= (initialCapacity >>> 4);
initialCapacity |= (initialCapacity >>> 8);
initialCapacity |= (initialCapacity >>> 16);
initialCapacity++;
if (initialCapacity < 0)
initialCapacity >>>= 1;
}
elements = new Object[initialCapacity];
}
allocateElements
函数主要用于给内部数组分配合适的大小使数组容量始终保持2^n .如果指定大小
numElements
小于
MIN_INITIAL_CAPACITY
,那么容量将设置成8,否则通过多次右移和位或运算分配容量为大于
numElements
且最小的2次幂.
>>>
为无符号右位移操作符,如上经过五次位移和位或操作可以保证得到
2^k-1
,再加1即可.
最后一小节:
if (initialCapacity < 0)
initialCapacity >>>= 1;
这是防止给定的
numElements
过大,导致位操作得到int最大值,再加1,则溢出变成负数,所以需要检测临界点回退一位.
即指定容量为
1111111111111111111111111111110
31位1(十进制为2147483646)经过各位操作后得
1111111111111111111111111111111
32位1(十进制为2147483647)为
int
最大值.
常用函数
| 操作 | 队首 | 失败抛异常 | 失败返回特殊值 | 队尾 | 失败抛异常 | 失败返回特殊值 |
|---|---|---|---|---|---|---|
| 插入 | addFirst(E) | offerFirst(E) | addLast(E) | offerLast(E) | ||
| 移除 | removeFirst() | pollFirst() | removeLast() | pollLast() | ||
| 获取 | getFirst() | peekFirst() | getLast() | peekLast() |
添加函数
void addFirst(E e)
/** 队首插入元素,为null抛异常 **/
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
// 核心代码
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
}
addFirst
函数核心代码
elements[head = (head - 1) & (elements.length - 1)] = e
,同样也是为什么数组容量为2的次幂原因:当length为2的次幂时,某整数
n & (length - 1)
等价于
n % length
,且对二进制而言**& 操作要比 % 效率更好**.
如下图:
当
head
为0的时候就会
head
指针移动到数组末尾.如若
head == tail
则触发
doubleCapacity
函数进行扩容.来看看扩容函数
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; // 左位移,等同于乘2,保持2的次幂
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;
}
doubleCapacity
通过数组拷贝和重新调整指针来完成扩容,每次扩容为原大小的2倍,保持2^n . 如下图:
void addLast(E e)
/** 队尾插入元素,为null抛异常 **/
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
addLast
和
addFirst
类似,只不过
addLast
是控制
tail
指针,从前往后移动.
删除函数
E pollFirst()
/** 取出并删除队首 为空返回null **/
public E pollFirst() {
int h = head;
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
.否则将头元素置为
null
,再把
head
向后移动一位,即加1再和
(length-1)
按位&计算出新的
head
.
E pollLast()
/** 取出并删除队尾元素 为空返回null **/
public E pollLast() {
int t = (tail - 1) & (elements.length - 1);
E result = (E) elements[t];
if (result == null)
return null;
elements[t] = null;
tail = t;
return result;
}
pollLast
和
pollFirst
差不多,先定位尾元素下标取出尾元素,为空返回
null
,不为空置为
null
,并把
tail
指针指向当前下标.
获取函数
/** 取出队首元素 为空抛异常 **/
public E getFirst() {
E result = (E) elements[head];
if (result == null)
throw new NoSuchElementException();
return result;
}
/** 取出队尾元素 为空返回抛异常 **/
public E getLast() {
E result = (E) elements[(tail - 1) & (elements.length - 1)];
if (result == null)
throw new NoSuchElementException();
return result;
}
getFirst
和
getLast
函数较为简单,一个直接获取
head
元素,一个通过&运算定位下标获取,代码分析到这里就结束了,其他部分也应该能看懂了。
总结
ArrayDeque是Deque的一种具体实现,是基于头尾指针循环利用数组实现的.
每当ArrayDeque容量不足时都会动态扩容,每次扩容容量增加一倍.
ArrayDeque提供了对栈的实现,也可直接作为栈来使用.