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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
|
public class ArrayDeque<E> extends AbstractCollection<E>
implements Deque<E>, Cloneable, Serializable
{
/**
* 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.
* 存储了双端队列元素的数组。该deque的容量是这个数组的长度，这总是2的幂。该数组永远不会被允许变满，
* 除非暂时在addX方法中被调整大小（请参阅双倍容量），因此避免头部和尾部相互缠绕。我们还保证所有不包含deque元素的
* 数组单元始终为空。
*
* 数组作为存储结构
*/
private transient E[] elements;
/**
* 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.
*
* deque头部元素的索引（这是remove（）或pop（）将被移除的元素）;或者如果双端队列是空的，则任意数字等于尾部。
*/
private 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)).
*
* 下一个元素将添加到deque尾部的索引（通过添加Last（E），add（E）或push（E））。
*/
private transient int tail;
/**
* The minimum capacity that we'll use for a newly created deque.
* Must be a power of 2.
* 我们将为新创建的deque使用的最小容量。必须是2的幂。
*/
private static final int MIN_INITIAL_CAPACITY = 8;
// ****** Array allocation and resizing utilities ******
/**
* Allocate 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 祝你好运分配2 ^ 30元素
}
elements = (E[]) new Object[initialCapacity];
}
/**
* Double 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; // 往右移1位，扩容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 = (E[])a;
head = 0;
tail = n;
}
/**
* Copies the elements from our element array into the specified array,
* in order (from first to last element in the deque). It is assumed
* that the array is large enough to hold all elements in the deque.
* 复制元素 调用toArray
* @return its argument
*/
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;
}
/**
* Constructs an empty array deque with an initial capacity
* sufficient to hold 16 elements.
*/
public ArrayDeque() {
elements = (E[]) 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);
}
}
|
