双端队列之ArrayDequeue

2022-05-04 本文已影响0人程序员札记

双端队列是一个很有意思的话题。在讲并发双端队列之前，我们需要介绍一个非并发的ArrayDequeue，让大家理解双端队列的一些原理。

ArrayDeque不是线程安全的。
ArrayDeque不可以存取null元素，因为系统根据某个位置是否为null来判断元素的存在。
当作为栈使用时，性能比Stack好；当作为队列使用时，性能比LinkedList好。

image.png

从 ArrayDeque 命名就能看出他的实现基于数组（LinkedList 是基于链表实现的双端队列），但是 ArrayDeque 的数组是一个可扩容动态数组，每次队列满了就会进行扩容，除非扩容至 int 边界才会抛出异常，ArrayDeque 不允许元素为 null。ArrayDeque 的主要成员是一个 elements 数组和 int 的 head 与 tail 索引，head 是队列的头部元素索引，而 tail 是队列下一个要添加的元素的索引，elements 的默认容量是 16 且默认容量必须是 2 的幂次，不足 2 的幂次会自动向上调整为 2 的幂次。

ArrayDeque 获取队列头部元素的 element()\getFirst()\peek()\peekFirst() 操作，其都是调用 getFirst() 实现的，访问队列头部元素但不删除，即如下

    public E getFirst() {
        @SuppressWarnings("unchecked")
        E result = (E) elements[head];
        if (result == null)
            throw new NoSuchElementException();
        return result;
    }

ArrayDeque 删除队列头部元素的 remove()\removeFirst()\poll()\pollFirst() 操作，其都是调用 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;
    }

ArrayDeque 添加元素到队列尾部的操作可以发现 add(E e)\offer(E e)\offerLast(E e)\addLast(E e) 操作都是调用 addLast(E e) 实现的，即如下：

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

addLast 的实现原理，也就是那句 if 操作与双倍扩容到底是做了什么我们先看下不扩容情况下 ArrayDeque 相关操作的图解，如下：

image.png

正如上图中最后的多次操作结果所示，如果此时我们再 add 操作一个元素到 tail 索引处则 tail+1 会变成 8 导致数组越界，理论上来说这时候应该进行扩容操作了，但是由于下标为 0、1、2、3 处没有存储元素，直接扩容有些浪费（ArrayList 为了避免浪费是通过拷贝将删除之后的元素整体前挪一位），所以为了高效利用数组中现有的剩余空间就有了 addLast(E e) 中的代码 (tail = (tail + 1) & (elements.length - 1)); 实质类似上面 pollFirst() 里面 head 操作，即假设 elements 默认初始化长度是 8，则当前 tail + 1（8=1000）按位与上数组长度减一（7=0111）的结果为十进制的 0，所以下一个被 addLast(E e) 的元素实际会放在索引为 0 的位置，再下一个会放在索引为 1 的位置，如下图：

image.png

问题： (tail = (tail + 1) & (elements.length - 1)) 这个哪里见过，是不是在LongAdder里线程probe找cell 那个逻辑？这句话实际上就是对element.length 取余

可以看到，随着出队入队不断操作，如果 tail 移动到 length-1 之后数组的第一个位置 0 处没有元素则需要将 tail 指向 0，依次循环，当 tail 如果等于 head 时说明数组要满了，接下来需要进行数组扩容，所以就有了上面 addLast(E e) 里面那个 if 判断的逻辑去触发 doubleCapacity()。因此这也就解释了为什么 ArrayDeque 的初始容量必须是 2 的幂次（扩容每次都是成倍的，所以自然也满足 2 的幂次），因为只有容量为 2 的幂次时 ((tail + 1) & (elements.length - 1)) 操作中的 (elements.length - 1) 二进制最高位永远为 0，当 (tail + 1) 与其按位与操作时才能保证循环归零置位。ArrayDeque 的 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;
    }

image.png

双端队列之ArrayDequeue

猜你喜欢

热点阅读