image frame

无论走到哪里,
都应该记住,
过去都是假的,
回忆是一条没有尽头的路。
一切以往的春天都不复存在,
就连那最坚韧而又狂乱的爱情,
归根结底也不过是转瞬即逝的现实,
唯有孤独永恒。

——加西亚·马尔克斯

ArrayDeque 源码

问题

  1. ArrayDeque 如何实现双端队列的?
  2. ArrayDeque 操作队列的头部和尾部指针有什么特别技巧,如何防止移位越界?
  3. ArrayDeque 有界吗?

概述

  • 双端队列,非线程安全

    ArrayDeque 是一种以数组方式实现的双端队列(两端可以进出),非线程安全。

继承结构

ArrayDeque 继承结构

  • ArrayDeque 继承 AbstractCollection<E>

可求两个集合的并集、差集、交集等方法

  • ArrayDeque 实现了 Deque<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
/**
* 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 底层使用数组存储,容量大小总是 2^n

  • ArrayDeque 使用头部和尾部指针标识

  • ArrayDeque 的最小总量是 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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/**
* 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);
}

/**
* Allocates empty array to hold the given number of elements.
*
* @param numElements the number of elements to hold
*/
private void allocateElements(int numElements) {
elements = new Object[calculateSize(numElements)];
}

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;
}
  • 不指定初始化容量,默认是 16
  • 指定初始化容量,计算最合适的容量(2^n)
  • 最大分配容量的 2^30

知识点

如何找到大于一个正整数N的最小2的次幂数,参考 calculateSize(int numElements) 方法。
详细解读

入队

入队有很多方法,主要是调用以下两个方法。

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
/**
* 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();
}

/**
* 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();
}
  • 两种入队方式,从队列头或者从队列尾
  • 如果容量不够,直接扩大为两倍
  • 头部指针和尾部指针在数组范围内循环

知识点

一个容量为 2^n 的数组,增减元素时移动前后指针,如何使用最优的方式解决指针越界的问题?

  • 前提:elements.length 是 2^n
  • head = (head - 1) & (elements.length - 1) 头部指针前移一位
  • tail = (tail + 1) & (elements.length - 1) 尾部指针后移一位

扩容

ArrayDeque 扩容为原来的两倍。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* 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;
}
  • 创建新的数组为原来的两倍
  • 从旧的数组拷贝到新数组
  • 重新设置头部和尾部的指针

出队

出队有多种方法,主要调用以下两个方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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;
}

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 可以作为栈来使用。

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
/**
* Pushes an element onto the stack represented by this deque. In other
* words, inserts the element at the front of this deque.
*
* <p>This method is equivalent to {@link #addFirst}.
*
* @param e the element to push
* @throws NullPointerException if the specified element is null
*/
public void push(E e) {
addFirst(e);
}

/**
* Retrieves and removes the head of the queue represented by this deque
* (in other words, the first element of this deque), or returns
* {@code null} if this deque is empty.
*
* <p>This method is equivalent to {@link #pollFirst}.
*
* @return the head of the queue represented by this deque, or
* {@code null} if this deque is empty
*/
public E poll() {
return pollFirst();
}
  • 栈的特性是先进后出,故只需要操作队列头就可以实现了

总结

  • ArrayDeque 通过数组实现的双端队列;
  • ArrayDeque 出队入队列是通过操作头部和尾部的指针实现;
  • ArrayDeque 容量不足是,进行扩容,新容量为原来的 2 倍;
  • ArrayDeque 的容量都是 2^n ,这样方便操作头部和尾部的指针;

head = (head - 1) & (elements.length - 1) 头部指针前移一位
tail = (tail + 1) & (elements.length - 1) 尾部指针后移一位

  • ArrayDeque 可作为栈来使用;
  • © 2015-2020 Andrew
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信