ArrayDeque
当要使用栈时,Java已不推荐使用Stack,而推荐使用更高效的ArrayDeque;当需要使用队列时也就首选ArrayDeque(次选LinkedList)。ArrayDeque
实现了接口 Deque
。
ArrayDeque
没有容量限制;- 非线程安全,因此不支持多线程同时安全访问;
- 不允许存储Null元素;
- 作为栈使用时,比Stack快;作为队列使用时,比LinkedList更快。
Deque
double ended queue
, 支持元素在两端增加和删除的线性容器,这个接口定义了12种方法。分为两类:操作失败抛出异常;操作失败返回特定值 null 或者 false。
Deque接口extends Queue接口,当作为queue(FIFO)使用时,元素从队列的尾端加入,从队列的首端取出,对应的方法如下:
Queue | Equivalent Deque Method | Desc |
---|---|---|
add(e) |
addLast(e) |
向队尾插入元素,失败则抛出异常 |
offer(e) |
offerLast(e) |
向队尾插入元素,失败则返回false |
remove() |
removeFirst() |
获取并删除队首元素,失败则抛出异常 |
poll() |
pollFirst() |
获取并删除队首元素,失败则返回null |
element() |
getFirst() |
获取但不删除队首元素,失败则抛出异常 |
peek() |
peekFirst() |
获取但不删除队首元素,失败则返回null |
Deque也可以当作Stacks(LIFO)使用,元素从deque的首端push和pop,对应的方法如下:
Stack | Equivalent Deque Method | Desc |
---|---|---|
push(e) |
addFirst(e) |
向栈顶插入元素,失败则抛出异常 |
offerFirst(e) |
向栈顶插入元素,失败则返回false |
|
pop() |
removeFirst() |
获取并删除栈顶元素,失败则抛出异常 |
pollFirst() |
获取并删除栈顶元素,失败则返回null |
|
peek() |
peekFirst() |
获取但不删除栈顶元素,失败则抛出异常 |
peekFirst() |
获取但不删除栈顶元素,失败则返回null |
Important variables
1 | // 存储数组 |
数组的长度就是deque的容量,它总是2的幂。除了在addX方法中短暂的变满,不允许数组装满。在addX方法中,数组变满后立即对其进行大小调整,从而避免头和尾交叉。另外,不包含元素的位置始终为空。因为是循环数组,所以head
不一定总等于0,tail
也不一定总是比head
大。
Main Methods
doubleCapacity()
在head和tail相遇的时候,表示deque装满了,进行扩容。这样交叉的复制方式保证了性的elements中元素的顺序符合逻辑。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15private void doubleCapacity() {
assert head == tail;
int p = head;
int n = elements.length;
int r = n - p; // head右边的长度
int newCapacity = n << 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 = a;
head = 0;
tail = n;
}addFirst()
空间问题是在插入元素后考虑的;索引的范围控制交给
head = (head - 1) & (elements.length - 1)
当head=0时,在往左(head-1)加入元素,如下所示,head移动到了element的最后(构成了循环)。1
2
3// head=0,elements.length=16
head=[head-1]补&[elements.length - 1]补=[-1]补&[15]补=11111111&00001111
=00001111=[15]补=151
2
3
4
5
6
7
8public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
// 扩容
if (head == tail)
doubleCapacity();
}addLast()
tail 所以和head相反,向右移动,假设当前tail=element.length 放置元素之后.如下所示移动到elements最左(构成了循环)。
1
tail = (tail + 1) & (elements.length - 1)=[16]补&[15]补=00010000&00001111=00000000=0
1
2
3
4
5
6
7public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}poolFirst()
过程与addFirst相反,拿出元素,并向右移动head。1
2
3
4
5
6
7
8
9
10public 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;
}poolLast()
过程与addLast相反,拿出元素,并向左移动tail。1
2
3
4
5
6
7
8
9public 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;
}peakFirst()
1
2
3
4public E peekFirst() {
// 如果deque为空,elements[head] = null
return (E) elements[head];
}peakLast()
1
2
3public E peekLast() {
return (E) elements[(tail - 1) & (elements.length - 1)];
}Summary
- deque保证element数组的大小始终是2的幂,这就使得
elements.length - 1
的补码始终是类似于00001111
这样左边为0,右边为1的形式。 & (elements.length - 1)
是保证索引构成循环的巧妙实现- 扩容时的交叉复制,保证了元素扩容后顺序符合逻辑。
- deque保证element数组的大小始终是2的幂,这就使得
若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏
扫描二维码,分享此文章