文档章节

死磕 java集合之ArrayDeque源码分析

o
 osc_gu9d45li
发布于 2019/04/29 23:17
字数 1812
阅读 0
收藏 0

精选30+云产品,助力企业轻松上云!>>>

问题

(1)什么是双端队列?

(2)ArrayDeque是怎么实现双端队列的?

(3)ArrayDeque是线程安全的吗?

(4)ArrayDeque是有界的吗?

简介

双端队列是一种特殊的队列,它的两端都可以进出元素,故而得名双端队列。

ArrayDeque是一种以数组方式实现的双端队列,它是非线程安全的。

继承体系

qrcode

通过继承体系可以看,ArrayDeque实现了Deque接口,Deque接口继承自Queue接口,它是对Queue的一种增强。


public interface Deque<E> extends Queue<E> {
    // 添加元素到队列头
    void addFirst(E e);
    // 添加元素到队列尾
    void addLast(E e);
    // 添加元素到队列头
    boolean offerFirst(E e);
    // 添加元素到队列尾
    boolean offerLast(E e);
    // 从队列头移除元素
    E removeFirst();
    // 从队列尾移除元素
    E removeLast();
    // 从队列头移除元素
    E pollFirst();
    // 从队列尾移除元素
    E pollLast();
    // 查看队列头元素
    E getFirst();
    // 查看队列尾元素
    E getLast();
    // 查看队列头元素
    E peekFirst();
    // 查看队列尾元素
    E peekLast();
    // 从队列头向后遍历移除指定元素
    boolean removeFirstOccurrence(Object o);
    // 从队列尾向前遍历移除指定元素
    boolean removeLastOccurrence(Object o);

    // *** 队列中的方法 ***
    
    // 添加元素,等于addLast(e)
    boolean add(E e);
     // 添加元素,等于offerLast(e)
    boolean offer(E e);
    // 移除元素,等于removeFirst()
    E remove();
    // 移除元素,等于pollFirst()
    E poll();
    // 查看元素,等于getFirst()
    E element();
    // 查看元素,等于peekFirst()
    E peek();

    // *** 栈方法 ***

    // 入栈,等于addFirst(e)
    void push(E e);
    // 出栈,等于removeFirst()
    E pop();

    // *** Collection中的方法 ***
    
    // 删除指定元素,等于removeFirstOccurrence(o)
    boolean remove(Object o);
    // 检查是否包含某个元素
    boolean contains(Object o);
    // 元素个数
    public int size();
    // 迭代器
    Iterator<E> iterator();
    // 反向迭代器
    Iterator<E> descendingIterator();
}

Deque中新增了以下几类方法:

(1)*First,表示从队列头操作元素;

(2)*Last,表示从队列尾操作元素;

(3)push(e),pop(),以栈的方式操作元素的方法;

源码分析

主要属性

// 存储元素的数组
transient Object[] elements; // non-private to simplify nested class access
// 队列头位置
transient int head;
// 队列尾位置
transient int tail;
// 最小初始容量
private static final int MIN_INITIAL_CAPACITY = 8;

从属性我们可以看到,ArrayDeque使用数组存储元素,并使用头尾指针标识队列的头和尾,其最小容量是8。

主要构造方法

// 默认构造方法,初始容量为16
public ArrayDeque() {
    elements = new Object[16];
}
// 指定元素个数初始化
public ArrayDeque(int numElements) {
    allocateElements(numElements);
}
// 将集合c中的元素初始化到数组中
public ArrayDeque(Collection<? extends E> c) {
    allocateElements(c.size());
    addAll(c);
}
// 初始化数组
private void allocateElements(int numElements) {
    elements = new Object[calculateSize(numElements)];
}
// 计算容量,这段代码的逻辑是算出大于numElements的最接近的2的n次方且不小于8
// 比如,3算出来是8,9算出来是16,33算出来是64
private static int calculateSize(int numElements) {
    int initialCapacity = MIN_INITIAL_CAPACITY;
    // Find the best power of two to hold elements.
    // Tests "<=" because arrays aren't kept full.
    if (numElements >= initialCapacity) {
        initialCapacity = numElements;
        initialCapacity |= (initialCapacity >>>  1);
        initialCapacity |= (initialCapacity >>>  2);
        initialCapacity |= (initialCapacity >>>  4);
        initialCapacity |= (initialCapacity >>>  8);
        initialCapacity |= (initialCapacity >>> 16);
        initialCapacity++;

        if (initialCapacity < 0)   // Too many elements, must back off
            initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
    }
    return initialCapacity;
}

通过构造方法,我们知道默认初始容量是16,最小容量是8。

入队

入队有很多方法,我们这里主要分析两个,addFirst(e)和addLast(e)。

// 从队列头入队
public void addFirst(E e) {
    // 不允许null元素
    if (e == null)
        throw new NullPointerException();
    // 将head指针减1并与数组长度减1取模
    // 这是为了防止数组到头了边界溢出
    // 如果到头了就从尾再向前
    // 相当于循环利用数组
    elements[head = (head - 1) & (elements.length - 1)] = e;
    // 如果头尾挨在一起了,就扩容
    // 扩容规则也很简单,直接两倍
    if (head == tail)
        doubleCapacity();
}
// 从队列尾入队
public void addLast(E e) {
    // 不允许null元素
    if (e == null)
        throw new NullPointerException();
    // 在尾指针的位置放入元素
    // 可以看到tail指针指向的是队列最后一个元素的下一个位置
    elements[tail] = e;
    // tail指针加1,如果到数组尾了就从头开始
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)
        doubleCapacity();
}

(1)入队有两种方式,从队列头或者从队列尾;

(2)如果容量不够了,直接扩大为两倍;

(3)通过取模的方式让头尾指针在数组范围内循环;

(4)x & (len - 1) = x % len,使用&的方式更快;

扩容

private void doubleCapacity() {
    assert head == tail;
    // 头指针的位置
    int p = head;
    // 旧数组长度
    int n = elements.length;
    // 头指针离数组尾的距离
    int r = n - p; // number of elements to the right of p
    // 新长度为旧长度的两倍
    int newCapacity = n << 1;
    // 判断是否溢出
    if (newCapacity < 0)
        throw new IllegalStateException("Sorry, deque too big");
    // 新建新数组
    Object[] a = new Object[newCapacity];
    // 将旧数组head之后的元素拷贝到新数组中
    System.arraycopy(elements, p, a, 0, r);
    // 将旧数组下标0到head之间的元素拷贝到新数组中
    System.arraycopy(elements, 0, a, r, p);
    // 赋值为新数组
    elements = a;
    // head指向0,tail指向旧数组长度表示的位置
    head = 0;
    tail = n;
}

扩容这里迁移元素可能有点绕,请看下面这张图来理解。

qrcode

出队

出队同样有很多方法,我们主要看两个,pollFirst()和pollLast()。

// 从队列头出队
public E pollFirst() {
    int h = head;
    @SuppressWarnings("unchecked")
    // 取队列头元素
    E result = (E) elements[h];
    // 如果队列为空,就返回null
    if (result == null)
        return null;
    // 将队列头置为空
    elements[h] = null;     // Must null out slot
    // 队列头指针右移一位
    head = (h + 1) & (elements.length - 1);
    // 返回取得的元素
    return result;
}
// 从队列尾出队
public E pollLast() {
    // 尾指针左移一位
    int t = (tail - 1) & (elements.length - 1);
    @SuppressWarnings("unchecked")
    // 取当前尾指针处元素
    E result = (E) elements[t];
    // 如果队列为空返回null
    if (result == null)
        return null;
    // 将当前尾指针处置为空
    elements[t] = null;
    // tail指向新的尾指针处
    tail = t;
    // 返回取得的元素
    return result;
}

(1)出队有两种方式,从队列头或者从队列尾;

(2)通过取模的方式让头尾指针在数组范围内循环;

(3)出队之后没有缩容哈哈^^

前面我们介绍Deque的时候说过,Deque可以直接作为栈来使用,那么ArrayDeque是怎么实现的呢?

public void push(E e) {
    addFirst(e);
}

public E pop() {
    return removeFirst();
}

是不是很简单,入栈出栈只要都操作队列头就可以了。

总结

(1)ArrayDeque是采用数组方式实现的双端队列;

(2)ArrayDeque的出队入队是通过头尾指针循环利用数组实现的;

(3)ArrayDeque容量不足时是会扩容的,每次扩容容量增加一倍;

(4)ArrayDeque可以直接作为栈使用;

彩蛋

双端队列与双重队列?

双端队列(Deque)是指队列的两端都可以进出元素的队列,里面存储的是实实在在的元素。

双重队列(Dual Queue)是指一种队列有两种用途,里面的节点分为数据节点和非数据节点,它是LinkedTransferQueue使用的数据结构。

还记得LinkedTransferQueue吗?点击链接直达【死磕 java集合之LinkedTransferQueue源码分析】。


欢迎关注我的公众号“彤哥读源码”,查看更多源码系列文章, 与彤哥一起畅游源码的海洋。

qrcode

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
死磕 Java简单集合之终结篇

简介 大家好,我是彤哥,Java简单集合彤哥建议的阅读顺序是先从最简单的ArrayList看起,再看Map->Set->Queue->Deque,最后再看LinkedList,LinkedList不仅仅是一个List,它还是一个Deque双端...

彤哥读源码
2019/11/29
0
0
死磕 java所有集合之终结篇

简介 我们先来看一看java中所有集合的类关系图。 这里面的类太多了,请放大看,如果放大还看不清,请再放大看,如果还是看不清,请放弃。 我们下面主要分成五个部分来逐个击破。 List List中...

彤哥读源码
2019/11/29
0
0
死磕 java集合之终结篇

概览 我们先来看一看java中所有集合的类关系图。 这里面的类太多了,请放大看,如果放大还看不清,请再放大看,如果还是看不清,请放弃。 我们下面主要分成五个部分来逐个击破。 List List中...

osc_gd4rlfym
2019/05/04
1
0
死磕 java集合之终结篇

🖕欢迎关注我的公众号“彤哥读源码”,查看更多源码系列文章, 与彤哥一起畅游源码的海洋。 概览 我们先来看一看java中所有集合的类关系图。 这里面的类太多了,请放大看,如果放大还看不清...

彤哥读源码
2019/05/05
0
0
死磕 java集合之终结篇

概览 我们先来看一看java中所有集合的类关系图。 这里面的类太多了,请放大看,如果放大还看不清,请再放大看,如果还是看不清,请放弃。 我们下面主要分成五个部分来逐个击破。 List List中...

彤哥读源码
2019/05/04
328
0

没有更多内容

加载失败,请刷新页面

加载更多

eclipse汉化教程(附安装包)

eclipse汉化包安装步骤 一、去官网或者在本站下载Eclipse(不管是什么版,中文设置的方法都是差不多的,所以说我们汉化的教程不管未来更新多少个版本都是一样的) 官方下载地址:www.eclipse.o...

树懒宝宝
36分钟前
22
0
CocosCreator之分层管理的ListView

前言 进入公众号回复listview即可获得demo的git地址。 之前写的一篇文章《Creator之ScrollView那些事》中提到了官方Demo中提供的ListViewCtl,只是实现了纵向滑动,没有实现横向滑动。并且建议...

陈广文
39分钟前
24
0
在CSS Flexbox中,为什么没有“ justify-items”和“ justify-self”属性?

问题: Consider the main axis and cross axis of a flex container: 考虑伸缩容器的主轴和横轴: Source: W3C 资料来源: W3C To align flex items along the main axis there is one pro......

法国红酒甜
41分钟前
17
0
搜索解决方案 - ElasticSearch/Solr/Lucene

搜索解决方案 - ElasticSearch/Solr/Lucene 1. 什么是 ElasticSearch ElasticSearch 是一个基于 Lucene 的搜素服务器 是一个分布式、高扩展、实时的搜素与数据分析引擎 基于 RESTful web 接口...

夙梦o
44分钟前
26
0
设计模式学习笔记(五):工厂方法模式

1 前言 尽管简单工厂模式实现了对象的创建和使用分离,但是仍然存在以下两个问题: 工厂类过于庞大,包含了大量的判断代码,导致维护和测试难度增大 系统扩展不灵活,如果增加了新的产品类型...

氷泠
48分钟前
21
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部