ArrayDeque
简介
Java注释
Resizable-array implementation of the {@link Deque} interface. Array deques have no capacity restrictions; they grow as necessary to support usage. They are not thread-safe; in the absence of external synchronization, they do not support concurrent access by multiple threads.Null elements are prohibited. This class is likely to be faster than {@link Stack} when used as a stack, and faster than {@link LinkedList} when used as a queue.
翻译
Deque接口的可调整大小的数组实现。数组双端队列没有容量限制；它们会根据需要增长以支持使用。它们不是线程安全的。在没有外部同步的情况下，它们不支持多个线程的并发访问。 禁止使用null元素。用作堆栈时，此类可能比Stack快，而用作队列时，则比LinkedList快。
双端队列是一种特殊的队列，它的两端都可以进出元素，故而得名双端队列。ArrayDeque是一种以数组方式实现的双端队列，它是非线程安全的。
类图
ArrayDeque实现了Deque接口，Deque接口继承自Queue接口，它是对Queue的一种增强。
源码
Queue
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public interface Queue<E> extends Collection<E> {
//插入指定的元素插入如果立即可行且不会违反容量限制，成功时返回true;
//如果当前没有空间可用,抛出IllegalStateException
boolean add(E e);
//如果可能的话，立即将指定的元素插入此队列，而不会违反容量限制。
//当使用容量受限的队列时，此方法通常比add更可取，后者可能会因抛出异常而无法仅插入元素。
boolean offer(E e);
//检索并删除此队列的头。该方法与poll的不同之处仅在于，如果此队列为空，它将引发异常。
E remove();
//检索并删除此队列的开头，如果此队列为空，则返回null
E poll();
//检索但不删除此队列的头。该方法与peek的不同之处仅在于，如果此队列为空，它将引发异常
E element();
//检索但不删除此队列的头，如果此队列为空，则返回null
E peek();
}
|
| 操作 |
抛出异常 |
返回特殊值 |
| 插入 |
add(e) |
offer(e) |
| 删除 |
remove() |
poll() |
| 检查 |
element() |
peek() |
Deque
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| public interface Deque<E> extends Queue<E> {
// 添加元素到队列头
void addFirst(E e);
// 添加元素到队列尾
void addLast(E e);
// 添加元素到队列头
boolean offerFirst(E e);
// 添加元素到队列尾
boolean offerLast(E e);
// 从队列头移除元素
E removeFirst();
// 从队列尾移除元素
E removeLast();
// 从队列头移除元素
E pollFirst();
// 从队列尾移除元素
E pollLast();
// 查看队列头元素
E getFirst();
// 查看队列尾元素
E getLast();
// 查看队列头元素
E peekFirst();
// 查看队列尾元素
E peekLast();
// 从队列头向后遍历移除指定元素
boolean removeFirstOccurrence(Object o);
// 从队列尾向前遍历移除指定元素
boolean removeLastOccurrence(Object o);
// *** 队列中的方法 ***
// 添加元素，等于addLast(e)
boolean add(E e);
// 添加元素，等于offerLast(e)
boolean offer(E e);
// 移除元素，等于removeFirst()
E remove();
// 移除元素，等于pollFirst()
E poll();
// 查看元素，等于getFirst()
E element();
// 查看元素，等于peekFirst()
E peek();
// *** 栈方法 ***
// 入栈，等于addFirst(e)
void push(E e);
// 出栈，等于removeFirst()
E pop();
// *** Collection中的方法 ***
// 删除指定元素，等于removeFirstOccurrence(o)
boolean remove(Object o);
// 检查是否包含某个元素
boolean contains(Object o);
// 元素个数
public int size();
// 迭代器
Iterator<E> iterator();
// 反向迭代器
Iterator<E> descendingIterator();
}
|
Deque方法总结
|
队列头 |
队列尾 |
|
抛异常 |
特殊值 |
抛异常 |
特殊值 |
| 插入 |
addFirst(e) |
offerFirst(e) |
addLast(e) |
offerLast(e) |
| 移除 |
removeFirst() |
pollFirst() |
removeLast() |
pollLast() |
| 检查 |
getFirst() |
peekFirst() |
getLast() |
peekLast() |
属性
1
2
3
4
5
6
7
8
| //存储元素数组
transient Object[] elements; // non-private to simplify nested class access
//队列头位置
transient int head;
//队列尾位置
transient int tail;
//最小初始容量
private static final int MIN_INITIAL_CAPACITY = 8;
|
构造方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| //无参构造方法
public ArrayDeque() {
elements = new Object[16];
}
//指定容量构造方法
public ArrayDeque(int numElements) {
allocateElements(numElements);
}
//通过集合构造
public ArrayDeque(Collection<? extends E> c) {
allocateElements(c.size());
addAll(c);
}
//初始化数组
private void allocateElements(int numElements) {
elements = new Object[calculateSize(numElements)];
}
//计算容量，算出大于numElements的最接近的2的n次方且不小于8
// 比如，3算出来是8，9算出来是16，33算出来是64
private static int calculateSize(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
}
return initialCapacity;
}
|
入队
add(E e)
1
2
3
4
5
| //调用addLast(e)
public boolean add(E e) {
addLast(e);
return true;
}
|
addFirst(E e)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| //队列头入队
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
// 将head指针减1并与数组长度减1取模，为了防止数组到头了边界溢出
// 如果到头了就从尾再向前，相当于循环利用数组
elements[head = (head - 1) & (elements.length - 1)] = e;
if (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;
if (newCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
//创建新数组
Object[] a = new Object[newCapacity];
//将旧数组head之后的元素拷贝到新数组中
System.arraycopy(elements, p, a, 0, r);
//将旧数组下标0到head之间的元素拷贝到新数组中
System.arraycopy(elements, 0, a, r, p);
elements = a;
//head指向0，旧数组长度指向尾索引
head = 0;
tail = n;
}
|
addLast(E e)
1
2
3
4
5
6
7
8
9
10
11
| //队列尾入队
public void addLast(E e) {
//非空校验
if (e == null)
throw new NullPointerException();
//在尾指针的位置放入元素，tail指针指向的是队列最后一个元素的下一个位置
elements[tail] = e;
//tail指针加1，如果到数组尾了就从头开始
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
|
出队
remove()
1
2
3
4
5
6
7
8
9
| public E remove() {
return removeFirst();
}
public E removeFirst() {
E x = pollFirst();
if (x == null)
throw new NoSuchElementException();
return x;
}
|
pollFirst()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| //从队列头出队
public E pollFirst() {
//头索引
int h = head;
@SuppressWarnings("unchecked")
//头节点元素
E result = (E) elements[h];
// Element is null if deque empty
//如果元素是null，返回null
if (result == null)
return null;
//头索引位置为null
elements[h] = null; // Must null out slot
//队列头指针右移一位
head = (h + 1) & (elements.length - 1);
return result;
}
|
pollLast()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| //从队列尾出队
public E pollLast() {
//队列尾索引左移一位
int t = (tail - 1) & (elements.length - 1);
@SuppressWarnings("unchecked")
//队列尾元素
E result = (E) elements[t];
if (result == null)
return null;
//队列尾位置设为null
elements[t] = null;
tail = t;
return result;
}
|
栈
ArrayDeque可以作为栈使用。
1
2
3
4
5
6
7
8
| //压入栈
public void push(E e) {
addFirst(e);
}
//弹出栈
public E pop() {
return removeFirst();
}
|
双端队列和双重队列
