目录
一、概述
二、底层实现
三、具体使用
一、概述
ArrayDeque
是
Collection
接口下Deque接口的一个实现，使用了可变数组，所以没有容量上的限制。
同时，
ArrayDeque
是线程不安全的，在没有外部同步的情况下，不能再多线程环境下使用。
ArrayDeque
是
Deque
的实现类，可以作为栈来使用，效率高于
Stack
；
也可以作为队列来使用，效率高于
LinkedList
。需要注意的是，
ArrayDeque
不支持
null
值。
ArrayDeque
也可以使用Iterator来迭代，并且可以从前向后和从后向前遍历。
所以说它是万金油的原因是：
-
可以当做双端队列使用
-
可以当做普通队列使用
-
可以当做栈使用
二、底层实现
ArrayDeque
底层逻辑的实现主要借助于一个环形逻辑计算公式，其实底层结构就是一个数组，但是下标的巧妙控制让它在逻辑上成环，从而可以适应各种结构的实现。
下面就举个实例给大家解释一下：
public class MyArrayDeque<E> {
private E[] elements;//存储元素的数组
private int head;//头指针
private int tail;//尾指针
private final int INIT_CAPACITY = 16;//初始容量
//初始化方法
public MyArrayDeque() {
elements = (E[]) new Object[INIT_CAPACITY];
head = 0;
tail = 0;
}
//头部添加
public boolean offerFirst(E e) {
if (e == null) {
throw new NullPointerException();
}
//取余操作，避免数组空间浪费，同时防止下标越界，使数组在逻辑上成环
head = (head - 1) & (elements.length - 1);
elements[head] = e;
if (head == tail) {
//扩容操作
expand();
}
return true;
}
//扩容
private void expand() {
int oldLen = elements.length;
//二倍扩容
int newLen = oldLen << 1;
if (newLen < 0) {
throw new IllegalStateException("deque too big");
}
Object[] a = new Object[newLen];
//resize
int gap = oldLen - head;
//拷贝head到原数组末尾的所有元素到新数组
System.arraycopy(elements, head, a, 0, gap);
System.arraycopy(elements, 0, a, gap, tail);
//维护head和tail的下标
head = 0;
tail = oldLen;
//扩容后再返回给elements
elements = (E[]) a;
}
}
其实下面这段代码相当于是head=(head-1)%elements.length，但是我们都知道位运算的效率高，所以采用了位运算来取余（大家可以带入具体数值去验证这两个式子是否相等，是相等的。）
head = (head - 1) & (elements.length - 1);
至于为什么要(head-1)，因为咱这是头插方法，所以头插之后head往前移动一位，维护head节点的正确性，不然插着插着没头这个标志位了往哪儿插呢...
之后大家可能就不难理解为什么要取余了，比如head现在在0下标位置，我现在再头插，那head不维护成-1了？这时候就进行取余（按位&操作会去符号，因为(elements.length-1)是个正数，符号位是0，0&任何数都是0,符号位就是0，正数，这没什么问题），这也是逻辑成环的关键所在，所以我画个图解释一下：
至于扩容时机，那就是head==tail时了，注意是二倍扩容，并且扩容后一定要维护head和tail的值，不然一直head==tail会死循环无限扩容的，具体实现就是上面代码中的expand()方法。
三、具体使用
既然是具体使用，那直接上代码了，该说的写到注释里：
import java.util.ArrayDeque;
import java.util.Iterator;
public class ArrayDequeTest {
public static void main(String[] args) {
/**
* 当做双端队列使用
*/
System.out.println("当做双端队列使用：");
ArrayDeque<Integer> arrayDeque = new ArrayDeque<>();
//添加元素
arrayDeque.addFirst(1);
arrayDeque.addLast(2);
System.out.println("测试offer方法的返回值:");
System.out.println(arrayDeque.offerFirst(0));
System.out.println(arrayDeque.offerLast(3));
arrayDeque.addLast(4);
arrayDeque.addLast(5);
arrayDeque.addLast(6);
arrayDeque.addLast(7);
System.out.println("添加元素操作的测试：");
//正向遍历
Iterator iterator = arrayDeque.iterator();
while (iterator.hasNext()) {
Object next = iterator.next();
System.out.println(next);
}
//反向遍历
System.out.println("反向遍历:");
Iterator iteratorReversed = arrayDeque.descendingIterator();
while (iteratorReversed.hasNext()) {
Object next = iteratorReversed.next();
System.out.println(next);
}
//删除元素
arrayDeque.removeFirst();
arrayDeque.pollFirst();
arrayDeque.removeLast();
arrayDeque.pollLast();
arrayDeque.removeFirstOccurrence(4);
arrayDeque.removeLastOccurrence(5);
System.out.println("删除元素操作的测试：");
Iterator iterator1 = arrayDeque.iterator();
while (iterator1.hasNext()) {
Object next = iterator1.next();
System.out.println(next);
}
//获取元素
System.out.println("获取元素测试：");
System.out.println("获取第一个元素：" + arrayDeque.getFirst());
System.out.println("获取最后一个元素：" + arrayDeque.getLast());
System.out.println("元素个数：" + arrayDeque.size());
System.out.println("队列是否为空：" + arrayDeque.isEmpty());
System.out.println("队列中是否存在'2'元素:" + arrayDeque.contains(2));
System.out.println("------------------------------------");
/**
* 当做普通队列使用
*/
System.out.println("当做普通队列使用");
ArrayDeque<Integer> arrayDequeNormal = new ArrayDeque<>();
//增
arrayDequeNormal.add(1);
arrayDequeNormal.offer(2);
arrayDequeNormal.offer(3);
arrayDequeNormal.offer(4);
System.out.println("队列中的第一个元素为：" + arrayDequeNormal.element());
System.out.println("队列中的第一个元素为：" + arrayDequeNormal.peek());
//删
arrayDequeNormal.remove();
arrayDequeNormal.poll();
System.out.println("删除后剩余的元素:");
//遍历
Iterator iterator2 = arrayDequeNormal.iterator();
while (iterator2.hasNext()) {
Object next = iterator2.next();
System.out.println(next);
}
System.out.println("------------------------------------");
/**
* 当做栈来使用
*/
System.out.println("当做栈使用");
ArrayDeque<Integer> arrayDequeStack = new ArrayDeque<>();
//入栈
arrayDequeStack.push(1);
arrayDequeStack.push(2);
arrayDequeStack.push(3);
arrayDequeStack.push(4);
//出栈
arrayDequeStack.pop();
Iterator iterator3 = arrayDequeStack.iterator();
//遍历
while (iterator3.hasNext()) {
Object next = iterator3.next();
System.out.println(next);
}
System.out.println("------------------------------------");
}
}
大家可以在自己的环境下跑一下感受一下，万金油不是白叫的hh ^ ^