ArrayDeque详解(特点原理及使用示例)

ArrayDeque定义

ArrayDeque是Java集合框架中的一个双端队列实现，实现了Deque接口的类，它可以在两端添加或删除元素。

 

ArrayDeque特点

ArrayDeque具有以下特点：

1. 双端操作：ArrayDeque是一个双端队列，支持在队头和队尾添加或删除元素。
2. 线程不安全：ArrayDeque不是线程安全的，因此如果需要在多线程环境中使用，需要进行适当的同步。
3. 随机访问：与LinkedList不同，ArrayDeque支持随机访问操作，由于它是基于数组实现的，所以在索引访问时性能非常高效。
4. 没有容量限制：ArrayDeque的容量可以根据需要动态增加，因此它没有容量限制。

 

ArrayDeque原理

ArrayDeque的底层实现是一个基于循环数组的双端队列，它具有较高的性能表现和空间利用率。

如下图所示：

ArrayDeque的实现原理，会包含如下内容：

1.内部数组的实现

ArrayDeque使用一个Object[]数组来存储元素，当添加第一个元素时，数组被初始化为默认容量16。当元素数量超过容量时，ArrayDeque会自动扩容。

 

2.循环数组的实现

为了满足可以同时在数组两端插入或删除元素的需求，该数组还必须是循环的，即循环数组。

循环数组的实现方式是将数组的两端相连，这样当添加或删除元素时，可以直接在数组的头部或尾部进行操作。

 

3.双端队列的实现

ArrayDeque是一个双端队列，支持在队头和队尾添加或删除元素。

由于它同时支持栈和队列操作，因此它可以灵活地应对不同的场景。

 

4.空间利用率

ArrayDeque的内部数组实现具有较高的空间利用率，因为它可以动态扩容，并且使用了循环数组的实现方式。

这意味着在添加或删除元素时，不需要额外的空间来存储指针或节点，从而可以更有效地利用内存。

 

ArrayDeque使用实例

1.实现栈和队列

由于ArrayDeque同时支持栈和队列操作，因此可以用它来实现栈和队列。

如下所示：

Deque stack = new ArrayDeque<>();

// 入栈
stack.push(1);
stack.push(2);
stack.push(3);

// 出栈
while (!stack.isEmpty()) {
    System.out.println(stack.pop());
}

 

2.用作缓存

由于ArrayDeque可以动态扩容，因此可以将其用作缓存来存储最近访问的元素。

如下所示：

Deque cache = new ArrayDeque<>(10);
// 在访问一个新的URL时，将其加入缓存队列
public void visitUrl(String url) {
    if (!cache.contains(url)) {
        if (cache.size() >= 10) {
            cache.removeLast();
        }
        cache.addFirst(url);
    } else {
        cache.remove(url);
        cache.addFirst(url);
    }
}

通过上面的代码，ArrayDeque实现了一个最近访问的URL缓存。

以上就是ArrayDeque的详解，更多Java集合框架，请查看：Java集合框架详解(看这篇就够了)。

陈睿mikechen

10年+大厂架构经验，资深技术专家，就职于阿里巴巴、淘宝、百度等一线互联网大厂。

关注「mikechen」公众号，获取更多技术干货！

后台回复【面试】即可获取《史上最全阿里Java面试题总结》，后台回复【架构】，即可获取《阿里架构师进阶专题全部合集》