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

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

2.7、扩容 doubleCapacity()

向数组中添加元素时，若数组容量不足，会调用doubleCapacity()方法，扩容为当前容量的两倍：

// 源码来自：android-29/java/util/ArrayDeque // 空间不足：扩容 private void doubleCapacity() { assert head == tail; // 头部 index int p = head; // 数组长度 int n = elements.length; // int r = n - p; // 容量扩展为当前的2倍 int newCapacity = n << 1; // 新的容量超过2^30，抛出异常 if (newCapacity < 0) throw new IllegalStateException("Sorry, deque too big"); // 创建一个新的数组 Object[] a = new Object[newCapacity]; // 拷贝原数组从 head位置到结束的数据 System.arraycopy(elements, p, a, 0, r); // 拷贝原数组从 开始到head的数据 System.arraycopy(elements, 0, a, r, p); // elements置空，保证其中元素可被垃圾回收 Arrays.fill(elements, null); // elements被重新赋值 elements = a; // header 和tail重新赋值 head = 0; tail = n; }

扩容后的数组为原始数组空间的两倍：

三、ArrayDeque 队列应用 3.1 入队列 // 向队列中添加一个元素。若添加成功则返回true；若因为容量限制添加失败则返回false是。 boolean offer(E e);

ArrayDeque入队列时：offer会调用offerLast实现入队列

3.2 出队列 // 删除队列头的元素，如果队列为空，则返回null； E poll();

ArrayDeque出队列时：poll会调用pollFirst实现出队列

四、ArrayDeque 堆栈应用 4.1 入堆栈 // 栈顶添加一个元素 void push( E e);

ArrayDeque入堆栈时：push会调用offerLast实现入堆栈

4.2 出堆栈 // 移除栈顶元素,如果栈顶没有元素将抛出异常 E pop();

ArrayDeque出堆栈时：poll会调用pollFirst实现出堆栈

参考

百度百科deque
https://baike.baidu.com/item/deque/849385?fr=aladdin