精华内容
下载资源
问答
  • arraydeque

    2016-08-22 16:05:22
    arraydeque
  • 主要为大家详细介绍了Java ArrayDeque的使用方法,感兴趣的小伙伴们可以参考一下
  • ArrayDeque

    2021-03-16 02:02:10
    ArrayDeque Stack已经不被推荐了,现在使用栈和队列的时候推荐ArrayDeque。 Resizable-array implementation of the Deque interface. Array deques have no capacity restrictions; they grow as necessary to ...

    ArrayDeque

    Stack已经不被推荐了,现在使用栈和队列的时候推荐ArrayDeque。

    Resizable-array implementation of the Deque interface. Array deques have no capacity restrictions; they grow as necessary to support usage. They are not thread-safe; in the absence of external synchronization, they do not support concurrent access by multiple threads. Null elements are prohibited. This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.

    Deque接口的可调整数组实现。数组deque没有容量限制;它们会在必要时增长以支持使用。它们不是线程安全的;在没有外部同步的情况下,它们不支持多个线程的并发访问。禁止使用空元素。当使用该类作为堆栈时,它可能比Stack快,当使用该类作为队列时,它可能比LinkedList快。

    Most ArrayDeque operations run in amortized constant time. Exceptions include remove, removeFirstOccurrence, removeLastOccurrence, contains, iterator.remove(), and the bulk operations, all of which run in linear time.

    大多数ArrayDeque操作运行在平摊常量时间内。异常包括remove、removeFirstOccurrence、removeLastOccurrence、contains、iterator.remove()和bulk操作,所有这些操作都在线性时间内运行。

    The iterators returned by this class’s iterator method are fail-fast: If the deque is modified at any time after the iterator is created, in any way except through the iterator’s own remove method, the iterator will generally throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

    这个类的迭代器方法返回的迭代器是快速失败的:如果在创建迭代器后的任何时间修改了deque,除了通过迭代器自己的remove方法,其他任何方式迭代器通常都会抛出ConcurrentModificationException。因此,在面对并发修改时,迭代器快速而干净地失败,而不是在未来不确定的时间冒任意的、不确定的行为的风险。

    Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.
    This class and its iterator implement all of the optional methods of the Collection and Iterator interfaces.

    注意,不能保证迭代器快速失败的行为,因为一般来说,在存在非同步并发修改的情况下,不可能做出任何硬保证。快速失败迭代器会抛出ConcurrentModificationException异常。因此,编写依赖此异常来保证正确性的程序是错误的:迭代器的快速失败行为应该只用于检测bug。

    该类及其迭代器实现了集合和迭代器接口的所有可选方法。

    ArrayDeque是由会进行扩容的数组实现的,线程不安全,且不支持使用null。

    参数

        //存放元素的数组,长度永远为2的幂,如果数组满了就会立刻扩容
        transient Object[] elements; // non-private to simplify nested class access
    
        //头节点的索引
        transient int head;
    
        //元素被添加的位置的索引
        transient int tail;
    
        //最小容量,一定2的幂
        private static final int MIN_INITIAL_CAPACITY = 8;
    

    构造函数

    /**
     * Constructs an empty array deque with an initial capacity
     * sufficient to hold 16 elements.
     */
    public ArrayDeque() {
        elements = new Object[16];
    }
    

    不指定,默认为16的长度。

    /**
     * Constructs an empty array deque with an initial capacity
     * sufficient to hold the specified number of elements.
     *
     * @param numElements  lower bound on initial capacity of the deque
     */
    public ArrayDeque(int numElements) {
        allocateElements(numElements);
    }
    
    /**
     * Allocates empty array to hold the given number of elements.
     *
     * @param numElements  the number of elements to hold
     */
    private void allocateElements(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
        }
        elements = new Object[initialCapacity];
    }
    

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wP43zf5E-1615831302118)(C:\Users\10374\AppData\Roaming\Typora\typora-user-images\image-20210316011641147.png)]

        initialCapacity = numElements;
        initialCapacity |= (initialCapacity >>>  1);
        initialCapacity |= (initialCapacity >>>  2);
        initialCapacity |= (initialCapacity >>>  4);
        initialCapacity |= (initialCapacity >>>  8);
        initialCapacity |= (initialCapacity >>> 16);
        initialCapacity++;
    

    所以这段代码的意思就是将原来的值的最高位后面的位都置为1,再加1;

    扩容机制

    /**
     * Doubles the capacity of this deque.  Call only when full, i.e.,
     * when head and tail have wrapped around to become equal.
     */
    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;
    }
    

    在数组满了的时候立即扩容成原来的两倍。通过生成一个新的数组,然后进行数组复制。

    addFirst方法

    /**
     * Inserts the specified element at the front of this deque.
     *
     * @param e the element to add
     * @throws NullPointerException if the specified element is null
     */
    public void addFirst(E e) {
        if (e == null)
            throw new NullPointerException();
        elements[head = (head - 1) & (elements.length - 1)] = e;
        if (head == tail)
            doubleCapacity();
    }
    
    head == tail
    

    先看这段代码,判断头和尾是否相同?我们可以判断这个数组是首尾相连的数组,所以要在数组满的时候就扩容。

    (head - 1) & (elements.length - 1)
    

    假设由8个元素,那么进行一次扩容后长度为16,head原来在0处。

    那么0-1=-1就是0xffffffff即二进制表示11111111111111111111111111111111。

    最后和16-1=15。就是将元素放在数组下标为15的位置。

    现在head是15,那么14的二进制表示为1110,与15相与得14。

    其实elements.length - 1与(head - 1)相与得部分都为1,而(head - 1)仅仅是往head得前面一个位置。

    addLast

    /**
     * Inserts the specified element at the end of this deque.
     *
     * <p>This method is equivalent to {@link #add}.
     *
     * @param e the element to add
     * @throws NullPointerException if the specified element is null
     */
    public void addLast(E e) {
        if (e == null)
            throw new NullPointerException();
        elements[tail] = e;
        if ( (tail = (tail + 1) & (elements.length - 1)) == head)
            doubleCapacity();
    }
    

    tail永远指向将要存放元素得位置,若该位置与头节点指向相同就扩容。

    (tail = (tail + 1) & (elements.length - 1)) == head
    

    即这个时候。

    pollFirst

    public E pollFirst() {
        int h = head;
        @SuppressWarnings("unchecked")
        E result = (E) elements[h];
        // Element is null if deque empty
        if (result == null)
            return null;
        elements[h] = null;     // Must null out slot
        head = (h + 1) & (elements.length - 1);
        return result;
    }
    

    弹出第一个值,并将head指向后一个位置,并返回。

    pollLast

        public E pollLast() {
            int t = (tail - 1) & (elements.length - 1);
            @SuppressWarnings("unchecked")
            E result = (E) elements[t];
            if (result == null)
                return null;
            elements[t] = null;
            tail = t;
            return result;
        }
    
    

    先将尾指针向前移动一格,然后弹出元素。

    展开全文
  • 主要介绍了Java ArrayDeque实现Stack功能的方法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • ArrayDeque是一种以数组方式实现的双端队列,它是非线程安全的。下面小编和大家一起学习一下
  • 主要介绍了Java集合ArrayDeque类实例分析的相关资料,需要的朋友可以参考下
  • arraydeque固定容量的循环缓冲区。 需要Rust 1.20+。 这个箱子的灵感来自bluss / arrayvec文档的用法首先,添加fol arraydeque一个具有固定容量的循环缓冲区。 需要Rust 1.20+。 首先,将以下内容添加到Cargo.toml中...
  • 主要介绍了java.util.ArrayDeque类使用方法,java.util.ArrayDeque类提供了可调整大小的阵列,并实现了Deque接口,感兴趣的小伙伴们可以参考一下
  • ArrayDeque原理详解

    2021-06-15 14:40:09
    ArrayDeque是双向队列,线程不安全的双向队列,长度可以自己扩容的双向队列,并且长度需要是2的幂次方,双端主要是头部和尾部两端都可以进行插入删除和获取操作,该实现类实现了Deque接口,Deque接口提供了双向队列...

    介绍

    ArrayDeque是双向队列,线程不安全的双向队列,长度可以自己扩容的双向队列,并且长度需要是2的幂次方,双端主要是头部和尾部两端都可以进行插入删除和获取操作,该实现类实现了Deque接口,Deque接口提供了双向队列需要实现的方法,接口提供了从头部插入、尾部插入,从头部获取、尾部获取以及删除等操作。ArrayDeque从名称来看能看出ArrayDeque内部使用的是数组来进行存储元素。

    类图

    image-20210613153422308.png
    通过类图也可以清晰的看到ArrayDeque继承自Deque接口,并且继承自Queue接口。同时也继承自Collection接口说明可以使用迭代器进行遍历集合。

    源码分析

    在分析源码之前,我们可以试想一些问题,前文已经介绍过ArrayDeque内部使用的数组元素来进行存储,数组中是如何控制从头部进行插入的呢?当数组为空时,从头部插入元素是如何实现的?以及数组元素中有值时,比如数组a=[1,2,3],这时候数组元素0的位置是有元素的,那又是如何将元素插入到数组下标0的元素之前的呢?前文讲述过数组的长度是2的幂次方?为什么数组的长度要是2的幂次方呢?带着这个问题来看源码的分析。

    字段信息

    由于Deque接口是双向队列,所以再进行添加元素的时候会指定head指针和tail尾指针,head指针指向数据元素的头部,tail指针指向数据元素的尾部,通过head指针和tail指针控制是从头部进行操作还是尾部进行操作,以下是ArrayDeque中的字段信息:

    /**
     * 数组存储的元素。
     */
    transient Object[] elements; // non-private to simplify nested class access
    
    /**
     * 头指针。
     */
    transient int head;
    
    /**
     * 尾指针。
     */
    transient int tail;
    
    /**
     * 数组的默认最小大小。长度必须是2的幂次方。
     */
    private static final int MIN_INITIAL_CAPACITY = 8;
    

    calculateSize方法

    首先我们来解决第一个问题,就是数组的长度的问题,数组长度前面说必须是2的幂次方,但是看到构造函数中可以指定数组的长度,既然可以指定数组的长度,那这里指定数组长度为10,这个数字也不是2的幂次方啊,其实我们指定的虽然不是2的幂次方,但是ArrayDeque内部会帮我进行调整,调整数组长度为2的幂次方,先看一下ArrarDeque的构造函数:

    // 默认长度为16的数组。
    public ArrayDeque() {
        elements = new Object[16];
    }
    
    /**
     * 指定数组长度,发现指定数组长度时,调用了allocateElements方法。
     */
    public ArrayDeque(int numElements) {
        allocateElements(numElements);
    }
    
    /**
     * 指定集合并且初始化大小。
     */
    public ArrayDeque(Collection<? extends E> c) {
        allocateElements(c.size());
        addAll(c);
    }
    

    构造函数中除了第一个默认构造函数之外,其他两个构造函数都调用了allocateElements方法来进行初始化数组的动作以及容量调整的动作,接下来我们来分析下是如何做到容量是2的幂次方?

    /**
     * 初始化数组大小,调用calculateSize方法来调整容量大小。
     */
    private void allocateElements(int numElements) {
        elements = new Object[calculateSize(numElements)];
    }
    

    上面的方法对数组元素进行初始化,在初始化前需要进行容量的调整,实际调整容量大小的方法是calculateSize方法。

    private static int calculateSize(int numElements) {
      	// 获取最小的初始化容量大小。
        int initialCapacity = MIN_INITIAL_CAPACITY;
    		// 如果容量大于最小的容量,则寻找一个2的幂次方的值。
        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
        }
      	// 返回2的幂次方值。
        return initialCapacity;
    }
    

    以开始时的例子为主,比如我们在初始化ArrayDeque指定了数组长度为10,它在进行初始化数组大小时会调用calculateSize来计算一个2的幂次方的值。

    public static void main(String[] args) {
        ArrayDeque<Integer> arrayDeque = new ArrayDeque<>(10);
    }
    
    1. 程序运行到第五行时,numElements >= initialCapacity成立,10>=8,则会进入到if语句内部。
    2. 程序运行到第六行时, initialCapacity = numElements,initialCapacity 设置为10,10的二进制表示方式是1010。
    3. 程序运行到第七行时, initialCapacity无符号向右移动一位,1010无符号向右移动一位是0101,1010|0101=1111,十进制表示方式是15。
    4. 程序运行到第七行时, initialCapacity无符号向右移动一位,1111无符号向右移动一位是0011,1111|0011=1111,十进制表示方式是15,一直持续下去都是15,当程序运行到第12行时,15进行加1操作,则变成16。这个时候16就是2的幂次方返回。

    整体思路是每次移动将位数最高的值变成1,从而将二进制所有位数都变成1,变成1之后得到的十进制加上1之后得到值就是2的幂次方的值,这里的操作在JDK1.7版本中的HashMap扩容操作代码是类似的。

    AddFirst方法

    以上就是如何保证了数组的大小是2的幂次方的代码逻辑,代码设计很巧妙,2的幂次方数组大小有什么好处呢?其实这里我可以简单描述下好处在于可以控制指针的在数组中的位置,也就是可以解决第一个问题,接下来再往下继续进行分析数组进行头部插入时的内容,先上源码先上源码:

    public void addFirst(E e) {
        if (e == null)
            throw new NullPointerException();
        elements[head = (head - 1) & (elements.length - 1)] = e;
        if (head == tail)
            doubleCapacity();
    }
    

    在头部进行插入元素,比如我们看一下如下代码的运行结果,先进行头部进行插入,然后再尾部插入,看一下整体的插入过程,通过这个简单的实例能够了解为什么数组长度设置为2的幂次方。

    public static void main(String[] args) {
        ArrayDeque<Integer> arrayDeque = new ArrayDeque<>(10);
        arrayDeque.addFirst(5);
        arrayDeque.addLast(1);
        arrayDeque.forEach(System.out::println);
    }
    

    此时初始化时数组长度为16,头指针head和尾指针head默认是0,此时数组的内容如下所示:

    image-20210613173946845.png

    当执行addFirst方法插入数组元素5时,通过源码可以看到需要执行elements[head = (head - 1) & (elements.length - 1)] = e;这一行代码,至于后面那个headtail是为了扩容使用,也就是只有在队列满时才会对数组进行扩容操作,队列满的标识是headtail代表队列已经满了,这里先进行分析elements[head = (head - 1) & (elements.length - 1)] = e,我们将其拆分成如下内容

    • head=head-1,此时的head=0,那么head-1得到值15(二进制减法操作),15使用二进制表示为:1111
    • elements.length - 1,这里开始是初始化大小为10,通过calculateSize方法计算的到数组长度为16,16-1=15,二进制表示方式也是1111。
    • 1111&1111依然是1111,此时数组的下标为15。

    咦?通过这个算出来的下标竟然是15,而不是0?可能大家猜想的是在头部插入时会当数组为空时,它会插入到数组的元素下标0的位置,其实并不是,而是插入到下标为15的位置处,通过图示法来看一下:

    image-20210613175135449.png

    插入到下标为15的位置是因为,假如我们在0,1,2下标位置插入值后,在通过头插法插入值时,发现数组的头部已经没有位置了,它会利用数组的尾部进行插入,head会指向尾部的位置,这也是为什么数组要设置为2的幂次方的原因,是为了能够定位数组的中头指针的位置,大家看到头指针前一个指针是head = (head - 1) & (elements.length - 1),那大胆猜测一下头指针的下一个指针指向的head = (head + 1) & (elements.length - 1),这个我们后面来验证。

    AddLast方法

    还是回到上面的例子中,这里只是运行到了addFirst,继续运行addLast内容,首先先上源码,然后在针对源码进行分析:

    public void addLast(E e) {
        if (e == null)
            throw new NullPointerException();
        elements[tail] = e;
        if ( (tail = (tail + 1) & (elements.length - 1)) == head)
            doubleCapacity();
    }
    

    这里从尾指针进行插入看着还是比较简单的,直接使用elements[tail] = e;即可,此时数组中元素存储情况以及tail指针移动位置。

    image-20210613210956127.png

    此时tail指针是进行增加1,也就是会运行到tail = (tail + 1) & (elements.length - 1)这里,这里判断tail的下一个节点如果和head节点重合说明数组已经满了,需要进行扩容操作,相当于如下所示:

    image-20210613211152913.png

    当有线程再对ArrayDeque队列进行插入值时,这是tail值插入值后,tail会指向head节点,此时head和tail进行重合,重合后进行扩容操作,如下图所示:

    image-20210613211426159.png

    ArrayDeque双向队列巧妙的运用了数组的头部和尾部,简单点说头指针在获取数据时,需要将头指针进行增加1操作,当头指针达到数组尾部时,将头指针指向数组的头部,从数组的头部进行获取数据。如果从尾指针获取数据时,其实就是从尾指针数据进行减少1操作,向前进行获取数据,如果达到了数组头部,则将尾指针指向数组的数组的尾部,从尾部往前在进行寻找,如果找到值为空说明数组为空了。

    pollFirst方法

    当然ArrayDeque对获取数据还有peekFirst和peekLast,这两个方法比较简单,就是获取对应指针值,这里就不再赘述了,这里重点讲一下pollFirst和pollLast方法。

    public E pollFirst() {
      	// 获取头指针。
        int h = head;
        @SuppressWarnings("unchecked")
    		// 获取头指针对应的数组元素值。
        E result = (E) elements[h];
        // Element is null if deque empty
      	// 如果为空则说明说明数组为空,直接返回。
        if (result == null)
            return null;
      	// 将头指针值设置为空。
        elements[h] = null;     // Must null out slot
      	// 啊哈?这里是不是我们上面猜测的内容,头指针下一个位置。
        head = (h + 1) & (elements.length - 1);
        return result;
    }
    

    演示下刚才插入的两个元素情况进行pollFirst是一种什么样的操作,插入之后数组元素是这样的。

    image-20210613210956127.png

    当pollFirst时,此时head=15,h=15,result=elements[15]=5,并且将 elements[15]设置为null,此时数组为:

    image-20210613213246501.png
    设置为空后会执行如下语句,head = (h + 1) & (elements.length - 1),啊哈,这里和上文中猜测的内容是一样的,h+1=15+1=16,用二进制表示1 0000,数组长度为16,16-1=15,用二进制表示1111,相当于1111&0000=0,此时数组head节点被调整到数组的头部,head=0。此时数组为:

    image-20210613213540103.png

    pollLast方法

    这里还是回归到插入两个元素的情况,即如下状态:

    image-20210613210956127.png

    先看一下源码信息,如下所示:

    public E pollLast() {
      	// 找到尾指针的前一个指针位置。
        int t = (tail - 1) & (elements.length - 1);
        @SuppressWarnings("unchecked")
      	// 获取尾部元素。
        E result = (E) elements[t];
        if (result == null)
            return null;
      	// 将尾部元素设置为空。
        elements[t] = null;
      	// 调整尾指针位置。
        tail = t;
        return result;
    }
    

    当调用pollLast时,首先运行的是 int t = (tail - 1) & (elements.length - 1),此时tail=1,tail-1=0,二进制表示为0000,elements.length - 1=16-1=15,用二进制表示为1111,0000&1111=0,则代表尾指针的最后一个元素存储的内容在尾指针的前一个坐标,此时获取数组下标为0的值,result=1,将 elements[t]设置为null,此时数组为:

    image-20210613214415131.png
    接着将tail=t,t=0,将尾指针调整到0的位置,此时数组内容:

    image-20210613214513031.png

    其他用法

    在源码中还看到了removeFirst和removeLast其实内部调用的就是pollFist和pollLast方法,以及存在栈功能的pop方法和push方法,其实内部调用的就是addFist和pollFist的操作,这里就不在进行一一讲解了,主要方法都在上面讲述了。

    总结

    1. ArrayDeque是一个双向队列,线程非安全。

    2. ArrayDeque是基于数组来进行实现的。

    3. ArrayDeque的数组长度是2的幂次方。

    4. 指针下一个和上一个表示方式:

      • 头指针的前一个节点定位坐标:(head-1)&(elements.length - 1),下一个节点位置:(head+1)&(elements.length - 1)
      • 尾指针的前一个节点定位坐标:(tail-1)&(elements.length - 1),下一个节点位置:(tail+1)&(elements.length - 1)
      • 总结起来就是前一个节点位置:(i-1)&(elements.length - 1),下一个位置:(i+1)&(elements.length - 1)

    喜欢的朋友可以关注我的微信公众号BattleHeart,不定时推送文章

    展开全文
  • ArrayDeque详解

    2018-11-20 11:15:04
    ArrayDeque是java中对双端队列的线性实现 一.特性 无容量大小限制,容量按需增长; 非线程安全队列,无同步策略,不支持多线程安全访问; 当用作栈时,性能优于Stack,当用于队列时,性能优于LinkedList 两端都...

    美人如斯!

    ArrayDeque是java中对双端队列的线性实现

    一.特性

    1. 无容量大小限制,容量按需增长;
    2. 非线程安全队列,无同步策略,不支持多线程安全访问;
    3. 当用作栈时,性能优于Stack,当用于队列时,性能优于LinkedList
    4. 两端都可以操作
    5. 具有fail-fast特征
    6. 不能存储null
    7. 支持双向迭代器遍历

    注意: ArrayDeque的迭代器和大多数容器迭代器一样,都是快速失败(fail-fast),但是程序不能利用这个特性决定是或否进行了并发操作。

    二.数据结构

    为了更好的理解使用线性数组实现的双端队列,这里我们先来图解线性数组实现基本数据结构-队列:

    如上图所示,head指向队头,入队加元素时,tail队尾向后移动,出队时从head出取出元素并移除,这样就利用了线性数组实现先进先出的队列数据结构,当head等于tail时,则表示队列为空。
    但是这样存在问题:当不断出队时,head向后移动,前面空出来的空间就被浪费,导致不断入队时,需要数组扩容,出队时造成大量空间无法使用,空间利用率低下!
    假设,如果能将前面空出来的空间也利用起来进行存储末尾的元素,则空间使用率将提高,这里就需要有个循环的思维,把这种线性的弯曲成一个圆环,这样就可以反复使用空出来的空间,入队时使用出队空余出来的空间,就解决以上的问题,图解如下:

    同样,当head等于tail时,则表示循环队列为空。head和tail也是循环的,像钟表中的时针,具有周期性。这里head和tail需要对长度lenth取模,这样head和tail将一直在长度范围内,可以作为数组的下标。

    对于如何将数据分布到相应大小的连续空间中,常用的方式就是取模运算,即position=index%len,利用整数倍的周期性,将剩余的部分作为空间索引。

    三.源码分析

    1. ArrayDeque数据域

    /**
     * The array in which the elements of the deque are stored.
     * The capacity of the deque is the length of this array, which is
     * always a power of two. The array is never allowed to become
     * full, except transiently within an addX method where it is
     * resized (see doubleCapacity) immediately upon becoming full,
     * thus avoiding head and tail wrapping around to equal each
     * other.  We also guarantee that all array cells not holding
     * deque elements are always null.
     */
    transient Object[] elements; // non-private to simplify nested class access
    
    /**
     * The index of the element at the head of the deque (which is the
     * element that would be removed by remove() or pop()); or an
     * arbitrary number equal to tail if the deque is empty.
     */
    transient int head;
    
    /**
     * The index at which the next element would be added to the tail
     * of the deque (via addLast(E), add(E), or push(E)).
     */
    transient int tail;
    
    /**
     * The minimum capacity that we'll use for a newly created deque.
     * Must be a power of 2.
     */
    private static final int MIN_INITIAL_CAPACITY = 8;

    首先看下ArrayDeque持有的成员域,其中非常核心的是elements,head,tail三个。下面逐一介绍:

    • elements: 该数组用于存储队列元素,且是大小总是2的幂次方(后面会介绍为什么?)。这个数组不会满容量,会在add方法中扩容,使得头head和tail不会缠绕在一起(即head增长或不会超过tail,head减小时不会溢出到tail),这里队列长度是2的幂次方的原因后续会阐明;
    • head: 双端队列的头位置,出队时或者弹出栈时的元素位置,加入双端队列头端元素位置,表示当前头元素位置;
    • tail:双端队列的尾,入队和进栈时的元素位置,加入双端队列尾端的下个元素的索引,tail位总是空的;
    • MIN_INITIAL_CAPACITY:最小的初始化容量

    2. 构造函数

    /**
     * Constructs an empty array deque with an initial capacity
     * sufficient to hold 16 elements.
     */
    public ArrayDeque() {
        elements = new Object[16];
    }
    
    /**
     * Constructs an empty array deque with an initial capacity
     * sufficient to hold the specified number of elements.
     *
     * @param numElements  lower bound on initial capacity of the deque
     */
    public ArrayDeque(int numElements) {
        allocateElements(numElements);
    }
    
    /**
     * Constructs a deque containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.  (The first element returned by the collection's
     * iterator becomes the first element, or <i>front</i> of the
     * deque.)
     *
     * @param c the collection whose elements are to be placed into the deque
     * @throws NullPointerException if the specified collection is null
     */
    public ArrayDeque(Collection<? extends E> c) {
        allocateElements(c.size());
        addAll(c);
    }
    • 第一个默认的无参构造函数:创建初始化大小为16的队列
    • 第二个构造函数:根据参数numElements创建队列,如果numElements小于8,则队列初始化大小为8;如果numElements大于8,则初始化大小为大于numElements的最小2的幂次方。如:numElements=17,则初始化大小为32
    • 第三个构造函数:根据集合元素创建队列,初始化大小为大于集合大小的最小2的幂次方

    这里重点看下第二个构造器的过程。其中调用allocateElements(numElements)方法,该方法用来实现容量分配,下面看下内部具体实现:

    /**
     * Allocates empty array to hold the given number of elements.
     *
     * @param numElements  the number of elements to hold
     */
    private void allocateElements(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
        }
        elements = new Object[initialCapacity];
    }

    首先判断指定大小numElements与MIN_INITIAL_CAPACITY的大小关系。如果小于MIN_INITIAL_CAPACITY,则直接分配大小为MIN_INITIAL_CAPACITY的数组;如果大于MIN_INITIAL_CAPACITY,则进行无符号右移操作,然后在加1,这样就可以寻找到大于numElements的最小2的幂次方。
    原理:无符号右移再进行按位或操作,就是将其低位全部补成1,然后再自加加一次,就是再向前进一位。这样就能得到其最小的2次幂。之所以需要最多移16位,是为了能够处理大于2^16次方数。

    最后再判断值是否小于0,因为如果初始值在int最大值2^31-1和2^30之间,进行一系列移位操作后将得到int最大值,再加1,则溢出变成负数,所以需要检测临界值,然后再右移1位!!!

    接下来再来分析下ArrayDeque的几个重要双端操作。对于双端队列有哪些重要的双端操作,可以移步至我的之前写的另一篇文章Java中Deque特性及API

    在详细介绍ArrayDeque的重要API实现之前,以图解的方式看下ArrayDeque构造函数初始化出的队列的数据结构:

    初始化ArrayDeque后,head和tail都是0,指向数组的0下标位置。在了解初始化后的数据构成后,再首先来看下addFirst方法

    3. 重要行为

    addFirst方法

    /**
     * Inserts the specified element at the front of this deque.
     *
     * @param e the element to add
     * @throws NullPointerException if the specified element is null
     */
    public void addFirst(E e) {
        if (e == null)
            throw new NullPointerException();
        elements[head = (head - 1) & (elements.length - 1)] = e;
        if (head == tail)
            doubleCapacity();
    }

    先用图解的方式分析下这个方法,在第一次调用这个方法后,数据变化如下:

    根据图的变化来分析下代码实现。
    首先判断插入元素是否为空,再计算即将插入的位置,计算出后将元素赋值给相应的槽位,最后再判断队列容量进行扩容。

    1. 将数组的高位端作为双端队列的头部,将低位作为双端队列尾部。没从头部加入一个元素时,head头逆时针向tail尾方向移动一个位置,实现上即将head减1后对数组的最大下标按位与运算。这里就利用了2的幂次方的特性,队列容量设置为2的幂次方后,数组的最大下标位置等于2的幂次方减1,在二进制表示时,就是所有二进制位都是1。这样head位置减1后与其进行按位与运算就能得到头部插入的位置。

    2. 当head等于tail时,就表示队列已经满了。这时需要进行扩容。

    下面再来看下扩容策略:

    /**
     * Doubles the capacity of this deque.  Call only when full, i.e.,
     * when head and tail have wrapped around to become equal.
     */
    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;
    }
    1. 按照2倍方式扩容
    2. 扩容后,将原队列中从头部插入的元素即head右边元素从扩容后新数组的0位置开始排放,然后将左边的元素紧接着排放进新数组。
    3. 将head置0,tail置成扩容前数组长度。

     

     

    如果从头端插入,则head继续逆时针旋转方式插入新元素。从以上图中不难看出addFirst是操作双端队列头端,且是逆时针方式旋转插入。接下来再看看从尾端插入的过程

    addLast方法

    /**
     * Inserts the specified element at the end of this deque.
     *
     * <p>This method is equivalent to {@link #add}.
     *
     * @param e the element to add
     * @throws NullPointerException if the specified element is null
     */
    public void addLast(E e) {
        if (e == null)
            throw new NullPointerException();
        elements[tail] = e;
        if ( (tail = (tail + 1) & (elements.length - 1)) == head)
            doubleCapacity();
    }

    上述的addFirst是逆时针的插入方式,addLast刚好与其相反,即顺时针方向插入,且tail表示的是下一个插入的元素的位置。

    1. 判断元素是否为空,然后直接将元素插入tail槽位
    2. 然后tail向后移动一位,再按位与(控制循环)作为新的tail槽位
    3. 判断新的tail槽位是否与head相等,然后依此进行扩容(这里扩容与上述扩容过程一样,不再赘述)。

    pollFirst方法

    public E pollFirst() {
        int h = head;
        @SuppressWarnings("unchecked")
        E result = (E) elements[h];
        // Element is null if deque empty
        if (result == null)
            return null;
        elements[h] = null;     // Must null out slot
        head = (h + 1) & (elements.length - 1);
        return result;
    }
    1. 取出头元素,如果头元素为空,则返回null
    2. 否则,将头元素槽位置为空(因为pollFirst是移除操作)
    3. 再将head顺时针向后移动一位,即加1再和数组最大下标按位与计算出新的head

    注:读到这里,相信读者已经已经对双端队列的数据结构已经非常清晰,即双端操作的数组,tail向前(顺时针)移动即从尾端插入元素或者向后移动即从尾端移除元素,head向后(逆时针)移动即从头端插入元素或者向前移动即从头端移除元素。这几个过程正好具有FIFO和LIFO的特点,所以ArrayDeque既可以作为队列Queue又可以作为栈Stack。

    pollLast方法

    public E pollLast() {
        int t = (tail - 1) & (elements.length - 1);
        @SuppressWarnings("unchecked")
        E result = (E) elements[t];
        if (result == null)
            return null;
        elements[t] = null;
        tail = t;
        return result;
    }

    从以上描述的ArrayDeque的数据结构和tail的含义中,可以大致思考下,从尾端移除元素的过程。

    1. 先将tail向后(逆时针)移动一位,然后对数组最大下标按位与计算出将要移除元素的槽位
    2. 取出计算出的槽位中元素,判断是否为空,为空则返回null
    3. 如果不为空,则将该槽位置为空,将槽位下标作为新的tail

    以上的过程基就是ArrayDeque的工作原理的最基本实现,其他的行为大都是基于这些过程实现:

    offer方法:内部调用offerLast插入元素,返回插入结果true/false
    add方法:内部调用addLast实现
    poll方法:内部调用pollFirst实现
    remove方法:内部调用removeFirst实现
    peek方法:内部调用peekFirst实现
    element方法:内部调用getFirst实现
    pop方法:内部调用addFirst实现
    push方法:内部调用removeFirst实现

    这里不再详述每个操作的具体实现,因为这些操作都是基于addFirst、addLast、pollFirst和pollLast实现。具体调用这些基础行为实现的细节,读者可以阅读ArrayDeque源码。

    参考:

    位运算总结(按位与,或,异或)
    Java 中>>和>>>的区别
    java int short long float double精度最大值整理

    展开全文
  • Android ArrayDeque 分析

    2020-04-13 15:46:13
    ArrayDeque是JDK容器中的一个双端队列实现,不过它内部使用的是数组来对元素进行操作,不允许存储null值,同时可以当做队列,双端队列,栈来进行使用。上篇文章的时候我们分析过LinkedList也是双端队列,不过用的是...

    简介

    ArrayDeque是JDK容器中的一个双端队列实现,不过它内部使用的是数组来对元素进行操作,不允许存储null值,同时可以当做队列,双端队列,栈来进行使用。上篇文章的时候我们分析过LinkedList也是双端队列,不过用的是双向链表结构实现的。

    使用示例

    public static void main(String[] args) {
        ArrayDeque<String> deque = new ArrayDeque<>();
        //添加一个元素(内部也是添加一个元素到尾部)
        deque.add("adbc");
        deque.add("123");
        //在最后一个位置添加元素
        deque.addLast("last Element");
        deque.add("456");
        //对队列的最后一个位置添加元素
        deque.offer("yahoo");
        //往队列的最后一个位置添加元素
    	deque.offerLast("tencent");
        deque.add("789");
        //往队列中的第一个位置插入一个元素
        deque.push("Hello");
        //在第一个位置添加元素
        deque.addFirst("first Element");
        //删除第一个元素,并且返回该删除的元素
        deque.poll();
        String data = deque.poll();
    }
    

    类结构图

    image_1dtsshcl215ourmr1bdd36l1sad9.png-19.7kB

    image_1dtr7e11p1b8e1jmk18fk12jv9t89.png-29.4kB

    注意: 我们知道ArrayDeque内部是由数组实现的,但是我们 知道数组是从左边到右边的。由此我们可知 tail就是数组的第0个元素,head就是数组中的第 length-1个元素

    代码分析

    通过上面的学习以及类结构图,我们能很清楚的知道ArrayDeque基本使用以及复用关系,它的内部api方法其实很多之间也都是复用的。比如说 add() 和 offer()、offerLast()最后都是调用的 addLast()方法来进行实现的;push()和 offerFirst()最后都是调用的addFirst()方法进行实现的。所以我们只需要分析核心方法,其他找到他们的调用关系就行。

    • 初始化
    public class ArrayDeque {
        //队列内部存储元素的 数组
        transient Object[] elements;
        //用于记录 队列 头部 位置信息
        transient int head;
        //用于记录 队列 尾部 位置信息
        transient int tail;
        private static final int MIN_INITIAL_CAPACITY = 8;
        
        public ArrayDeque() {
            elements = new Object[16];
        }
        。。。。。。。
    }
    
    

    根据我们最简单的构造方法,发现首先会创建一个长度为16的数组,同时还有两个很重要的属性head和tail用来指向数组的头和尾巴,同时我们也可以自定义数组的长度

    //我们也可以传入我们自定义的容量大小,同时jdk帮我们内部创建一个数组。
    public ArrayDeque(int numElements) {
        allocateElements(numElements);
    }
    
    /**
     * 这段代码的核心是找到一个数字 大于等于 numElements同时也是 2的n次幂的数字,同时创建的数组的大小就以这个数字为大小,举个例子,如果我们传入29的话,这个时候会进行运算同时找到32这个数字,同时创建一个大小为32的数组。
     */
    private void allocateElements(int numElements) {
        int initialCapacity = MIN_INITIAL_CAPACITY;
          // Find the best power of two to hold elements.
        // Tests "<=" because arrays aren't kept full.
        //我们传进来的数字小于8的话,那么就创建一个大小为8的数组。否则就找到最接近于numElements(同时还需要大于或者等于numElements),同时还要是2的n次幂的数字。
        if (numElements >= initialCapacity) {
            initialCapacity = numElements;
            //这里的 >>> 是无符号向右移动多少位然后再跟原来的数字进行 或 运算的。
            initialCapacity |= (initialCapacity >>>  1);
            initialCapacity |= (initialCapacity >>>  2);
            initialCapacity |= (initialCapacity >>>  4);
            initialCapacity |= (initialCapacity >>>  8);
            initialCapacity |= (initialCapacity >>> 16);
            initialCapacity++;
    
            //最大只能创建 2的30次幂大小的数组。
            if (initialCapacity < 0)    // Too many elements, must back off
                initialCapacity >>>= 1; // Good luck allocating 2^30 elements
        }
        elements = new Object[initialCapacity];
    }
    

    上面主要分析的时候了构造方法里面创建数组时的一些注意问题,如果是调用者自己传入大小的话,内部代码还会做一个转换,就是会找到最接近于我们传入这个数字,同时还需要是 2^n = numElements,

    • 添加元素

    尾部添加元素

    public void addLast(E e) {
        //从这个代码中我们可以看出该队列不可以添加 null元素
        if (e == null)
            throw new NullPointerException();
        //在初始化的时候 tail为0,所以直接在[0] 添加元素就行
        elements[tail] = e;
        //我们知道 elements length = 2 ^ n,所以 length - 1转换为 二进制的话,所有的数字都是1的。
        比如说 32 - 1转换为2进制的话就是 11111的,所以 (tail + 1) & 31的话还是原来的数字。
        这里相当于是 tail + 1,也就是 尾部的位置想右边移动了一个位置。
        //这里有一个非常关键的地方就是 tail = tail + 1同时要判断跟head的位置是否重合,如果重合的话,就需要进行扩容了。
        if ( (tail = (tail + 1) & (elements.length - 1)) == head)
            doubleCapacity();
    }
    

    头部添加元素

    public void addFirst(E e) {
        if (e == null)
            throw new NullPointerException();
        //通过上面的结构图中我们知道head默认指向的是数组的最后一个数字。当 head = 0时 head - 1 为 -1,这个时候 -1 & 31的话还是31,也就是指向数组的最后一个元素。同时 head 指向31。如果再往数组的头部添加元素的话,数组的位置依次向左边移动,相当于 index--的实现。
        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;
    }
    
    • 删除元素

    删除头部元素

    public E pollFirst() {
        final Object[] elements = this.elements;
        //将head索引赋值给 h
        final int h = head;
        //然后获取数组 elements 数组的h位置的值
        E result = (E) elements[h];
        //如果 elements[h] 不为空的话,表示数组中存在该数据,需要将该位置数据置为null。
        if (result != null) {
            elements[h] = null; // Must null out slot
            //head的位置需要向右边移动一位(head = head + 1)。然后返回该元素
            head = (h + 1) & (elements.length - 1);
        }
        return result;
    }
    

    删除尾部元素

    public E pollLast() {
        final Object[] elements = this.elements;
        //首先我们需要将 tail 位置向 左边移动一位(也就说 tail = tail - 1)。
        final int t = (tail - 1) & (elements.length - 1);
        //然后获取数组中的元素
        E result = (E) elements[t];
        if (result != null) {
            //需要将 tail - 1位置的元素置为null
            elements[t] = null;
            //同时 tail - 1 赋值给tail
            tail = t;
        }
        return result;
    }
    

    其实上面的不管在首尾添加数据还是在首尾删除数据,其实跟我们现实中的逻辑都是一样的,就是通过控制 head和tail位置来操纵数组,对数组进行增删操作的。如果我们要判断某个元素是否在队列中,则需要去遍历数组,然后每个元素进行比对匹配。

    • 清除所有元素
    public void clear() {
        int h = head;
        int t = tail;
        //首先判断首尾不相等。
        if (h != t) {
            head = tail = 0;
            //然后 head赋值 i
            int i = h;
            int mask = elements.length - 1;
            do {
                elements[i] = null;
                //这里有个需要注意的是,如果 i+1 大于 elements.lenth以后,再 & mask的话,是循环从mask 到 tail的。其实我很好奇为啥不直接 遍历数组,从0开始遍历到 length -1 呢?
                i = (i + 1) & mask;
            } while (i != t);
        }
    }
    

    在文章的开头的时候我们讲过可以当做栈来进行使用

    //在栈顶添加元素
     public void push(E e) {
        addFirst(e);
    }
    
    //弹出栈顶的元素
    public E poll() {
        return pollFirst();
    }
    

    通过上面的代码我们可以分析的出来, head是作为栈底的,而tail是在栈的最上面。这个时候我们就需要把把 ArrayDeque竖立起来看待了。其原型图:

    image_1dtveghpltt310qp1pp7pqi46k9.png-63.2kB

    总结

    1. ArrayDeque 采用数组方式实现的双端队列,通过内部变量 head和tail来控制位置的偏移
    2. ArrayDeque容量不足时会进行扩容,每次扩容的容量在原有基础上扩大一倍
    3. Array还可以当做栈来直接使用
    展开全文
  • Java ArrayDeque

    2020-06-09 08:15:39
    Java中的ArrayDeque是实现Deque接口的类。 它是双端队列的基于数组的实现。 顾名思义,双端队列是允许我们在前端和后端添加或删除项目的队列。 在开始之前,让我们快速看一下ArrayDeque上的一些值得注意的点: ...
  • 一、 ArrayDeque集合特点 底层数据结构:数组 一个基于可变长度数组实现的无界双端队列。不允许null元素。 可以当作双端队列使用 也可以当作普通队列使用 还可以当作栈使用 *普通队列数组实现:从尾部添加元素从头部...
  • ArrayDeque是 Deque接口的一个实现,使用了可变数组,所以没有容量上的限制。同时, ArrayDeque是线程不安全的,在没有外部同步的情况下,不能再多线程环境下使用。 ArrayDeque是 Deque的实现类,可以作为栈来使用,...
  • ArrayDeque的foreach

    2021-06-18 12:27:37
    Stack的foreach: Stack 中栈顶元素是len...ArrayDeque的foreach: 但是ArrayDeuqe的push是public void push(E e) { addFirst(e); } 而addFrist: public void addFirst(E e) { if (e == null) throw new NullPoint
  • Java总结 - ArrayDeque

    千次阅读 2019-02-01 22:14:58
    这次来说一下ArrayDeque,我们先看一下他的类关系图,其中忽略掉了一些标记性接口 我们看一下类的定义 public class ArrayDeque<E> extends AbstractCollection<E> implements Deque<E>...
  • 文章目录一、ArrayDeque(一)简介(二)主要方法(三)方法实现二、PriorityQueue(一) 简介(二)PriorityQueue 原理(三)方法实现 一、ArrayDeque (一)简介 ArrayDeque类是双端队列的实现类,类的继承结构如...
  • 第一次写文章,这是我看java源代码自己模仿写的ArrayDeque,就当做对自己的一次复习吧,希望对你们有所帮助,代码有什么错的地方 还请见谅 代码如下 public class MyArrayDeque&lt;E&gt; { private Object...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 17,016
精华内容 6,806
关键字:

arraydeque