Android双端队列——ArrayDeque的实现&源码分析[通俗易懂]

全栈程序员站长

发布于 2022-11-08 11:19:47

1.2K0

文章被收录于专栏：全栈程序员必看全栈程序员必看

大家好，又见面了，我是你们的朋友全栈君。

ArrayDeque介绍

ArrayDeque是一个实现了Deque接口，并且可调整大小的一个双向队列。ArrayDeque队列没有容量限制，它可以根据需要扩容。

ArrayDeque底层采用数组实现的。

ArrayDeque特性：

ArrayDeque是一个可扩容的双端队列。
内部使用数组存储数据。
ArrayDeque不是线程安全的。
ArrayDeque禁止使用空元素。
ArrayDeque用作堆栈时，比Stack要快，当它用作队列时，比LinkedList要快。
ArrayDeque最大容量是2^30个元素。
ArrayDeque队列的容量必须满足size = 2的n次幂。
ArrayDeque有两个类属性，head和tail，两个指针，可以在数组任意一端进行数据插入或删除。

Android中的使用

我们在分析AsyncTask时，它的内部实现就用到了ArrayDeque作为一个先进先出的队列。

    private static class SerialExecutor implements Executor {
        final ArrayDeque<Runnable> mTasks = new ArrayDeque<Runnable>();
        Runnable mActive;

        public synchronized void execute(final Runnable r) {
            mTasks.offer(new Runnable() {
                ……
            });
            ……
        }

        protected synchronized void scheduleNext() {
            if ((mActive = mTasks.poll()) != null) {
                THREAD_POOL_EXECUTOR.execute(mActive);
            }
        }
    }

这里使用了offer方法添加元素，使用poll方法获取元素。我们知道LinkedList也可以实现队列操作，那么为什么会使用ArrayDeque呢？它有哪些优势呢？

我们接下来分析它的实现原理。

ArrayDeque解析

首先我们来看ArrayDeque的构建。

ArrayDeque队列的容量必须满足2的n次幂，它是如何保证的呢？如果我们给它的构造函数传递一个非2次幂的值，它又是如何来调整大小的呢？

ArrayDeque的队列容量初始化原理

我们来看它的构造函数：

    public ArrayDeque() {
        elements = new Object[16];
    }
    public ArrayDeque(int numElements) {
        allocateElements(numElements);
    }
    public ArrayDeque(Collection<? extends E> c) {
        allocateElements(c.size());
        addAll(c);
    }

ArrayDeque有3个重载构造方法：

无参数时，ArrayDeque的初始大小是16，该值满足2的次幂要求。
参数是名为numElements的int值，它允许使用者自定义容器的初始大小，该构造函数只是调用了allocateElements(numElements)，看来大小调整的秘密就在allocateElements方法中了。
参数为Collection的构造方法中，也同样调用了allocateElements方法，也侧面验证了allocateElements是实现ArrayDeque大小是2的次幂的关键。

那么我们就来分析allocateElements的实现吧。

allocateElements方法实现初始化容器原始大小

ArrayDeque的构造函数中会调用allocateElements方法，来实现队列的初始化。

allocateElements的源码：

    private static final int MIN_INITIAL_CAPACITY = 8;
    private void  allocateElements(int numElements) {
        int initialCapacity = MIN_INITIAL_CAPACITY;
        // 如果队列容量size的大小，大于最小值时，需要通过位运算来设置成一个符合2的n次幂的值。例如，如果参数值是9~15之间的任意值，size（initialCapacity变量的值）的最终大小就是16，如果参数值是17~31之间的任意值，则size的最终大小是32。
        if (numElements >= initialCapacity) {
            initialCapacity = numElements;
            initialCapacity |= (initialCapacity >>>  1);
            initialCapacity |= (initialCapacity >>>  2);
            initialCapacity |= (initialCapacity >>>  4);
            initialCapacity |= (initialCapacity >>>  8);
            initialCapacity |= (initialCapacity >>> 16);
            initialCapacity++;

            if (initialCapacity < 0)    // 如果值太大溢出（即小于0），需要缩小2倍
                initialCapacity >>>= 1; // 最大运行值是 2^30
        }
        elements = new Object[initialCapacity];
    }

逻辑解析：

这里首先判断队列容量值numElements是否小于最小初始值，如果小于，则直接以最小初始值为size，初始化队列容器，这里最小size是8。
如果大于最小初始值，则进行一系列”位“操作。
初始initialCapacity的二进制位中，高位往低位找，找到第一个”1“，经过这一系列位操作之后，会把”1“之后的所有位上的值，都变成”1“。例如，initialCapacity值等于9，则位操作之前是”1001“，位操作之后变为”1111“，也就是15。
位操作之后，initialCapacity自增，上例中就由15变为16了，也就符合了2的次幂规则了，其他数值也可以用此方法推算出结果。
最后，如果initialCapacity值溢出，则左移一位。

ArrayDeque的扩容原理

当两个双端指针相遇时，也就是head等于tail时，则表示数组需要扩容了。扩容是通过方法doubleCapacity来实现的。

doubleCapacity方法：

    private void doubleCapacity() {
        assert head == tail; //断言
        int p = head; //临时变量p，等于head
        int n = elements.length;//扩容前的size
        int r = n - p; // head右侧元素个数
        int newCapacity = n << 1;//size扩大1倍
        if (newCapacity < 0)//溢出了，抛出错误
            throw new IllegalStateException("Sorry, deque too big");
        Object[] a = new Object[newCapacity];//创建新的数组，容量为原来的2倍
        System.arraycopy(elements, p, a, 0, r);//将head右侧数据从原来数组copy到新数组
        System.arraycopy(elements, 0, a, r, p);//将head左侧的数据从原数组copy到新数组
        // Android-added: Clear old array instance that's about to become eligible for GC.
        // This ensures that array elements can be eligible for garbage collection even
        // before the array itself is recognized as being eligible; the latter might
        // take a while in some GC implementations, if the array instance is longer lived
        // (its liveness rarely checked) than some of its contents.
        Arrays.fill(elements, null);//将原数组清空
        elements = a;//将扩容后的数组赋给elements
        head = 0;//设置head为0
        tail = n;//设置tail为扩容前的数组大小，作为指针起点
    }

逻辑解析：

计算出head指针右侧元素个数，之后需要使用它来进行数据复制。
数组容量扩大1倍，如果溢出（大于2^30），则报错。
创建新的数组作为容器，然后原数组的内容copy到新数组。
将原数组元素都置位null。
将新数组赋给elements。
设置head的值为0，tail的值为原数组的大小n。这时，新数组的[0~n)指针位均已存储元素。

下面我们再来分析ArrayDeque的几个关键方法。

队列头部添加元素addFirst

head代表了队列头当前插入点的指针，它的初始值是0。

在队列头部添加一个元素，使用addFirst方法：

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

逻辑解析：

这里的关键点就在head的计算上，head – 1 的使head得指针向左移动一位。例如，当head初始值为0时，队列容量是8时，head – 1的值就是-1，用二进制表示是1111，(elements.length – 1)的二进制表示是0111，两者按位&操作，结果就是7。这种操作结果类似于取余操作，但使用起来非常方便。

也就是说addFirst的第一个元素，在数组中的位置是elements[elements.length – 1]，之后每次插入操作，head指针都会向左移动。

当head指针和tail指针相等时，表示数组容器已经满了，需要进一步扩容了，扩容调用doubleCapacity方法即可。

队列尾添加元素addLast

head代表了队列尾当前插入点的指针，它的初始值是0。

在队列尾添加一个元素，使用addLast方法：

    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的值是0，也就是第一个在尾部添加的元素数组索引是0。
接下来tail指针右移，指向新的位置。这里同样使用了位运算来实现，以队列容量大小8为例，当tail的位置在第八位时（tail值是7）,tail的二进制是0111，加1后变为1000，按位&二进制0111（elements.length – 1的二进制），结果为0。
同样，当tail等于head时，扩容。

队列头弹出元素pollFirst

    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;
    }

逻辑解析：

获取head指针位置的元素：elements[h]，并赋值给result变量。
当元素不为null时，将elements[h]置位null，并且head指针右移（同样使用了位操作）。
最后返回result变量。

队列尾弹出元素pollLast

    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;
    }

逻辑解析：

设置临时变量t，并将tail左移一位之后赋值给t。
获取队尾元素，并赋值给result。
如果result不为null，将elements[t]置位null，并且将t赋值给tail指针。
最后返回result变量。

offer方法和poll方法

前文原理解析中，介绍了ArrayDeque的主要方法，但并没有AsyncTask中使用的offer方法和poll方法。其实这两个方法都是基于之前方法实现的封装接口，我们来看。

offer方法

    public boolean offer(E e) {
        return offerLast(e);
    }
    public boolean offerLast(E e) {
        addLast(e);
        return true;
    }

offer方法调用了offerLast方法，offerLast方法最终调用的是offerLast方法，offerLast方法之前已经做过分析了，它实现了在队尾添加元素。

poll方法

    public E poll() {
        return pollFirst();
    }

poll方法直接return了pollFirst方法，pollFirst方法实现了队列头部弹出。

小结

我们在本文中分析了ArrayDeque的实现、使用、及原理，下面来简单总结一下：

ArrayDeque是一个实现了Deque接口的双向队列。
ArrayDeque的容量大小是可以动态调整的，并且容量大小必须满足是2的n次幂。
ArrayDeque内部是使用数组来实现数据存储的。
ArrayDeque不是线程安全的。
ArrayDeque禁止使用空元素。
ArrayDeque用作堆栈时，比Stack要快，当它用作队列时，比LinkedList要快。
ArrayDeque最大容量是2^30个元素。
ArrayDeque有两个类属性，head和tail，两个指针，可以在数组任意一端进行数据插入或删除。
ArrayDeque在Android中有大量的应用。
在队列头部添加元素，可使用addFirst方法，在队列尾添加元素可使用addLast方法，队列头弹出元素可使用pollFirst方法，队列尾弹出元素可使用pollLast方法。
ArrayDeque的offer方法可以实现在队尾添加元素，它内部是调用offerLast方法实现的。
ArrayDeque的poll方法可以在队列头弹出元素，它的内部是调用pollFirst方法实现的。
ArrayDeque中，大量使用了位操作，非常巧妙的省去了边界处理等问题，简化了操作。

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/191250.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022年9月20日，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度