目录
一、概述
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 ^ ^
转载：https://blog.csdn.net/weixin_43729854/article/details/106529708
查看评论