ArrayDeque使用&实现原理分析 (2)

allocateElements(numElements)方法：可以将一个任意的初始值转化为2^n的值。
如果本身传进来的值就是2^n 的值，那么经过转化会变成2^(n+1)；
如果传入的值大于等于2^30，那么经过转化会变成负值，即< 0，此时会把初始值设置为2^30， 即最大的容量只有2^30；

2.3、队列首部添加元素

offerFirst(E e)、addFirst(E e) 源码实现

// 源码来自：android-29/java/util/ArrayDeque // 在队列前边 添加元素，返回是否添加成功 public boolean offerFirst(E e) { addFirst(e); return true; } // 在队列前边 添加元素 public void addFirst(E e) { // 存入空数据时，抛出异常NullPointerException if (e == null) throw new NullPointerException(); // 这样写 当head=0时，添加到的位置为elements.length - 1 // 从数组的末尾 向前 依次添加数据 elements[head = (head - 1) & (elements.length - 1)] = e; // 空间不足 if (head == tail) doubleCapacity(); // 扩容 }

offerFirst(E e)、addFirst(E e) 在数组前面添加元素：源码实现中，从数组的末尾向前依次添加数据元素；

2.4、队列首部删除元素

pollFirst()、removeFirst()源码实现

// 源码来自：android-29/java/util/ArrayDeque // 删除第一个元素，返回删除元素的值；如果元素为null，将抛出异常； public E removeFirst() { E x = pollFirst(); // 若为空，则抛出异常； if (x == null) throw new NoSuchElementException(); return x; } // 删除第一个元素，返回删除元素的值；如果元素为null，将返回null； public E pollFirst() { // 数组 final Object[] elements = this.elements; // 头部index final int h = head; // 头部元素 E result = (E) elements[h]; // 如果头部元素为null，则返回null if (result != null) { // 数据元素出队列 elements[h] = null; // Must null out slot // 指向下一个元素 head = (h + 1) & (elements.length - 1); } return result; }

执行pollFirst()、removeFirst()方法，进行数据出队列时，其数据的删除示意图如下图所示：

2.5、队列尾部添加元素

offerLast(E e)、addLast(E e) 源码实现

// 源码来自：android-29/java/util/ArrayDeque // 在数组后添加元素，返回是否添加成功 public boolean offerLast(E e) { addLast(e); return true; } // 在数组后面添加元素 public void addLast(E e) { // 存入空数据时，抛出异常NullPointerException if (e == null) throw new NullPointerException(); // 存入数据 elements[tail] = e; // (tail + 1) == head 空间已满 if ( (tail = (tail + 1) & (elements.length - 1)) == head) // 扩容 doubleCapacity(); }

offerLast(E e)、addLast(E e) 在数组后添加元素: 源码实现中，从数组的前端向后依次添加数据元素；

2.6、队列尾部移除元素

pollLast()、removeLast()源码实现

// 源码来自：android-29/java/util/ArrayDeque // 删除最后一个元素，返回删除元素的值；如果为null，将抛出异常； public E removeLast() { E x = pollLast(); if (x == null) throw new NoSuchElementException(); return x; } // 删除最后一个元素，返回删除元素的值；如果为null，返回null； public E pollLast() { // 数组元素 final Object[] elements = this.elements; // tail-1 final int t = (tail - 1) & (elements.length - 1); // 获取当前元素 E result = (E) elements[t]; if (result != null) { // 当前元素置空 elements[t] = null; // 将tail-1 赋值给 tail tail = t; } return result; }