ArrayDeque源码解析

2022-12-19 13:33:48 浏览数 (1)

转载请以链接形式标明出处： 本文出自:103style的博客

base on jdk_1.8.0_77

目录

  • ArrayDeque简介
  • ArrayDeque的常量和成员变量介绍
  • ArrayDeque的构造函数
  • ArrayDeque相关的函数
  • 小结
  • 参考文章

ArrayDeque简介

ArrayDeque类是双端队列Deque的实现类，类的继承结构如下:

代码语言：javascript复制
public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable

就其实现而言，ArrayDeque采用了循环数组的方式来完成双端队列的功能。

ArrayDeque有以下基本特征：

  • 无限的扩展，自动扩展队列大小的。（当然在不会内存溢出的情况下。）
  • 非线程安全的，不支持并发访问和修改。
  • 支持fast-fail.
  • 作为栈使用的话比Stack要快.
  • 当队列使用比LinkedList要快。
  • null元素被禁止使用。

ArrayDeque的常量和成员变量介绍

代码语言：javascript复制
private static final int MIN_INITIAL_CAPACITY = 8; //初始化 elements 的 最小长度
transient Object[] elements; // ArrayDeque保存数据的数组
transient int head;// 第一个元素的位置
transient int tail;// 最后一个元素的位置

ArrayDeque的构造函数

  • 数组默认的长度时 16，当指定长度时，会通过allocateElements计算 大于numElements 的最小 2n (n >=3)为数组的长度。 为什么是 2n ，和 HashMap 类似，通过index & (elements.length - 1)计算索引。
代码语言：javascript复制
public ArrayDeque() {
    elements = new Object[16];
}
public ArrayDeque(int numElements) {
    allocateElements(numElements);
}
public ArrayDeque(Collection<? extends E> c) {
    allocateElements(c.size());
    addAll(c);
}
private void allocateElements(int numElements) {
    int initialCapacity = MIN_INITIAL_CAPACITY;
    if (numElements >= initialCapacity) {
        initialCapacity = numElements;
        initialCapacity |= (initialCapacity >>>  1);
        initialCapacity |= (initialCapacity >>>  2);
        initialCapacity |= (initialCapacity >>>  4);
        initialCapacity |= (initialCapacity >>>  8);
        initialCapacity |= (initialCapacity >>> 16);
        initialCapacity  ;

        if (initialCapacity < 0)    
            initialCapacity >>>= 1;
    }
    elements = new Object[initialCapacity];
}

ArrayDeque相关的函数

代码语言：javascript复制
//添加到head前面
public void push(E e)
public boolean offerFirst(E e)
public void addFirst(E e)

//添加到tail后面
public boolean add(E e)
public boolean offerLast(E e)
public void addLast(E e)

//删除head所在位置的元素
public E pop()
public E remove()
public E poll()
public E removeFirst()
public E pollFirst()

//删除 tail所在位置的元素
public E removeLast()
public E pollLast()

//获取head所在位置的元素
public E element()
public E peek()
public E peekFirst()

//获取tail所在位置的元素
public E peekLast()

//获取队列元素的个数
public int size()
addFirst(E e)
  • 因为 head 和 tail 默认为 0，所以默认第一个元素存入的位置为 element 数组的最后的索引位置。当head==tail 时，说明elements数组满了，需要进行数组扩容，新数组长度是原来的2倍，然后重新赋值head = 0 。
代码语言：javascript复制
public void addFirst(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[head = (head - 1) & (elements.length - 1)] = e;
    if (head == tail)
        doubleCapacity();
}
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;
}
addLast(E e)
  • addLast即赋值 tail索引位置的值为e，然后tail ，当head==tail 时，同addFirst(E e)进行数组扩容。
代码语言：javascript复制
public void addLast(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[tail] = e;
    if ( (tail = (tail   1) & (elements.length - 1)) == head)
        doubleCapacity();
}
pollFirst()、pollLast()、peekFirst()、peekLast()
  • 返回对应索引的元素。
代码语言：javascript复制
public E pollFirst() {
    final Object[] elements = this.elements;
    final int h = head;
    @SuppressWarnings("unchecked")
    E result = (E) elements[h];
    // Element is null if deque empty
    if (result != null) {
        elements[h] = null; // Must null out slot
        head = (h   1) & (elements.length - 1);
    }
    return result;
}
public E pollLast() {
    final Object[] elements = this.elements;
    final int t = (tail - 1) & (elements.length - 1);
    @SuppressWarnings("unchecked")
    E result = (E) elements[t];
    if (result != null) {
        elements[t] = null;
        tail = t;
    }
    return result;
}
public E peekFirst() {
    // elements[head] is null if deque empty
    return (E) elements[head];
}
public E peekLast() {
    return (E) elements[(tail - 1) & (elements.length - 1)];
}
size()
代码语言：javascript复制
public int size() {
    return (tail - head) & (elements.length - 1);
}

小结

  • ArrayDeque是带首尾标记的数组实现的双端队列。

参考文章

  • Java集合ArrayDeque类解读
  • ArrayDeque

以上

编程算法 腾讯云开发者社区

0 人点赞