双端队列之ArrayDequeue

源代码 · 2024-9-23 22:59:20

双端队列是一个很故意思的话题。在讲并发双端队列之前，我们须要先容一个非并发的ArrayDequeue，让各人明确双端队列的一些原理。

ArrayDeque不是线程安全的。
ArrayDeque不可以存取null元素，由于体系根据某个位置是否为null来判定元素的存在。
看成为栈使用时，性能比Stack好；看成为队列使用时，性能比LinkedList好。

从 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 干系使用的图解，如下：

正如上图中末了的多次使用结果所示，如果此时我们再 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 的位置，如下图：

题目： (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; }

双端队列之ArrayDequeue

所属分类: 问答交流

新帖推荐: 30日

推荐作品