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

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

ArrayDeque定义

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

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

 

ArrayDeque特点

ArrayDeque具有以下特点:

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

 

ArrayDeque原理

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

如下图所示:

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

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年+大厂架构经验,BAT资深面试官,就职于阿里巴巴、淘宝、百度等一线互联网大厂。

👇阅读更多mikechen架构文章👇

阿里架构 |双11秒杀 |分布式架构 |负载均衡 |单点登录 |微服务 |云原生 |高并发 |架构师

以上

关注作者「mikechen」公众号,获取更多技术干货!

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

评论交流
    说说你的看法