# (48) 剖析ArrayDeque / 计算机程序的思维逻辑

ArrayDeque有如下构造方法：

```public ArrayDeque()
public ArrayDeque(int numElements)
public ArrayDeque(Collection<? extends E> c)```

numElements表示元素个数，初始分配的空间会至少容纳这么多元素，但空间不是正好numElements这么大，待会我们会看其实现细节。

ArrayDeque可以看做一个先进先出的队列，比如：

```Queue<String> queue = new ArrayDeque<>();

queue.offer("a");
queue.offer("b");
queue.offer("c");

while(queue.peek()!=null){
System.out.print(queue.poll() +" ");
}
```

```a b c
```

```Deque<String> stack = new ArrayDeque<>();

stack.push("a");
stack.push("b");
stack.push("c");

while(stack.peek()!=null){
System.out.print(stack.pop()+" ");
}
```

```c b a
```

```Deque<String> deque = new ArrayDeque<>();

deque.offerLast("b");

System.out.println(deque.getFirst()); //d
System.out.println(deque.peekLast()); //c
System.out.println(deque.removeFirst()); //d
System.out.println(deque.pollLast()); //c
```

ArrayDeque的用法是比较简单的，下面我们来看其实现原理。

ArrayDeque内部主要有如下实例变量：

```private transient E[] elements;
private transient int tail;```

```public ArrayDeque() {
elements = (E[]) new Object[16];
}
```

```public ArrayDeque(int numElements) {
allocateElements(numElements);
}
```

```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
}
elements = (E[]) new Object[initialCapacity];
}
```

• 如果numElements小于MIN_INITIAL_CAPACITY，则分配的数组长度就是MIN_INITIAL_CAPACITY，它是一个静态常量，值为8。
• 在numElements大于等于8的情况下，分配的实际长度是严格大于numElements并且为2的整数次幂的最小数。比如，如果numElements为10，则实际分配16，如果numElements为32，则为64。

```initialCapacity |= (initialCapacity >>>  1);
initialCapacity |= (initialCapacity >>>  2);
initialCapacity |= (initialCapacity >>>  4);
initialCapacity |= (initialCapacity >>>  8);
initialCapacity |= (initialCapacity >>> 16);
initialCapacity++;
```

```public static int highestOneBit(int i) {
// HD, Figure 3-1
i |= (i >>  1);
i |= (i >>  2);
i |= (i >>  4);
i |= (i >>  8);
i |= (i >> 16);
return i - (i >>> 1);
}```

```public ArrayDeque(Collection<? extends E> c) {
allocateElements(c.size());
}
```

```public boolean add(E e) {
return true;
}
```

```public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
```

doubleCapacity将数组扩大为两倍，代码为：

```private void doubleCapacity() {
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 = (E[])a;
tail = n;
}
```

```public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
doubleCapacity();
}
```

```Deque<String> queue = new ArrayDeque<>(7);
```

removeFirst方法的代码为：

```public E removeFirst() {
E x = pollFirst();
if (x == null)
throw new NoSuchElementException();
return x;
}
```

pollFirst的代码为：

```public E pollFirst() {
E result = 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;
}
```

removeLast方法的代码为：

```public E removeLast() {
E x = pollLast();
if (x == null)
throw new NoSuchElementException();
return x;
}
```

pollLast的代码为：

```public E pollLast() {
int t = (tail - 1) & (elements.length - 1);
E result = elements[t];
if (result == null)
return null;
elements[t] = null;
tail = t;
return result;
}```

t为最后一个位置，result为最后一个元素，将该位置置为null，然后修改tail指向前一个位置，最后返回原最后一个元素。

ArrayDeque没有单独的字段维护长度，其size方法的代码为：

```public int size() {
return (tail - head) & (elements.length - 1);
}
```

contains方法的代码为：

```public boolean contains(Object o) {
if (o == null)
return false;
int mask = elements.length - 1;
E x;
while ( (x = elements[i]) != null) {
if (o.equals(x))
return true;
i = (i + 1) & mask;
}
return false;
}
```

toArray方法

toArray方法的代码为：

```public Object[] toArray() {
return copyElements(new Object[size()]);
}
```

copyElements的代码为：

```private <T> T[] copyElements(T[] a) {
} else if (head > tail) {
}
return a;
}
```

ArrayDeque特点分析

ArrayDeque实现了双端队列，内部使用循环数组实现，这决定了它有如下特点：

• 在两端添加、删除元素的效率很高，动态扩展需要的内存分配以及数组拷贝开销可以被平摊，具体来说，添加N个元素的效率为O(N)。
• 根据元素内容查找和删除的效率比较低，为O(N)。

97 篇文章37 人订阅

0 条评论

## 相关文章

255100

38440

### 数据结构 第5讲 顺序栈

小张终于攒钱买了车，可是他家住在胡同的尽头，胡同很窄，只能通过一辆车，而且是死胡同，每天小张都为停车发愁，回家早了停在里面，早上上班就要让所有的人...

12530

### JAVA中Sql时间格式与util时间格式转换

pst.setDate(1, ;//这里的Date是sql中的::得到的是日期

30350

13130

182100

14930

8220

### 剑指Offer-不用加减乘除做加法

package Other; /** * 不用加减乘除做加法 * 写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。 * 思...

27150