栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

JDK源码阅读--ArrayDeque

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

JDK源码阅读--ArrayDeque

文章目录
  • 继承机构
  • 队列Queue
  • 双端队列deque
    • 操作第一个元素
    • 操作最后一个元素
    • 用作FIFO队列
    • 用作LIFO堆栈
  • ArrayDeque源码分析
    • addFirst
    • 扩容机制
    • 查询
    • 队列还是栈

继承机构

队列Queue

队列还提供额外的插入、提取和检查操作。 这些方法中的每一个都以两种形式存在:一种在操作失败时抛出异常,另一种返回>一个特殊值( null或false ,取决于操作)

抛出异常返回特殊值
添加add(e)offer(e)
移除队列头remove()poll()
返回队列头element()peek()
双端队列deque

双端队列是指允许两端都可以进行入队和出队操作的队列

操作第一个元素

操作最后一个元素

用作FIFO队列

用作LIFO堆栈

ArrayDeque源码分析

● 不支持多线程并发访问,
● 禁止空元素.
● 底层是对象数组,默认16,两倍扩容
分析一下ArrayDeque是如何实现双端队列的

transient Object[] elements;// 双端队列的容量,总是2的幂
transient int head; //表示队列头
transient int tail; // 表示队列尾
private static final int MIN_INITIAL_CAPACITY = 8;


// 无参构造一个长度16的对象数组,数组末端作为头部,每次add,就在左侧填充.

addFirst

arrayDeque底层数据结构是一个数组,无参构造创建的是一个容量为16的对象数组.
添加元素从数组末端开始,依次向数组头方向(head=head-1)添加,如上图

public void addFirst(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[head = (head - 1) & (elements.length - 1)] = e;
    // 每次add后检查是否需要扩容,当add元素的索引为0时,扩容为原来的两倍
    if (head == tail)
        doubleCapacity();
}

元素添加顺序:

数组中的存储顺序:

扩容机制

通过左移运算new = old<<1,新容量为原来的2倍
扩容时机: head==tail,数组空间已被使用完.

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];
    System.arraycopy(elements, p, a, 0, r);
    System.arraycopy(elements, 0, a, r, p);
    elements = a;
    head = 0;
    tail = n;
}

以上述add案例继续说明,当数组最后一个空间被占用后,检查head==tail,进行扩容.扩容之后元素在数组中的摆放如下:

查询

因为arrayDeque类中定义了两个属性,head和tail用来表示队列头尾对应的数组索引.所以获取首尾元素很简单,就是指定element
的索引即可

getFirst()
E result = (E) elements[head];

getLast()
E result = (E) elements[(tail - 1) & (elements.length - 1)];

如果没有扩容,按照从队列前面插入元素的规则,第一个插入的放入数组的最后一个索引,即elements.length-1.
当发生扩容后,数组中元素的摆放位置不再是连续有序的,此时则取tail-1索引位. 以容量16为例,扩容后为32,last元素放在未扩容时>的15索引位.即15&31 = 15;

队列还是栈

双端队列deque既可以实现队列结构FIFO(比linkedList实现队列要快),也可以实现栈结构LIFO(比stack类快).
取决于取数时是从头部取还是尾部取.
头部存,头部取,则是先进后出,栈
头部存,尾部取,则是先进先出,队列

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/981314.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号