双边队列Deque详解

大家好，关于双边队列Deque详解很多朋友都还不太明白，不过没关系，因为今天小编就来为大家分享关于的知识点，相信应该可以解决大家的一些困惑和问题，如果碰巧可以解决您的问题，还望关注下本站哦，希望对各位有所帮助！

其实源码中的很多注释还是蛮有趣的。比如上面的发音是写在源码里的。

LIFO：Deque VS Stack

一切事物的存在都是有原因的，那么Deque存在的意义是什么？我个人的理解是剑指向Stack。

因为我们都知道，在处理LIFO（Last-In-First-Out）数组，即后进先出时，首先想到的数据模型就是Stack（栈数据结构），因为它有最关键的两个方法：push(e)（压栈）和pop()（弹出栈），Java util包下也有相关的类：

/** * @since JDK1.0 */public class StackE extends VectorE {}但是看源码中的注释，明确告诉我们不建议使用Stack类，而使用DequeInteger stack=new ArrayDequeInteger ();反而：

为什么？首先参考上面关于SO：堆栈溢出的答案

我们简单说一下：

1.首先，正如上面SO中回答的那样，Stack类继承自Vector，这确实很奇怪，而且有点令人困惑。毕竟杂家也是一个非常真实的数据结构。它必须像Map一样作为接口存在，否则每个扩展类都必须继承Stack类，这很奇怪。

2、其次，Stack最大的缺点是同步，即线程安全，因为它的方法中使用了重量级的锁命令synchronized。这样带来的最大的问题就是性能会大大降低，也就是效率低下，例如：publicsynchronizedEpop()。

如上所述，Deque是双边队列。双边是指既可以操作头数据，也可以操作尾数据。所以很自然地，Deque可以实现Stack中的push(e)和pop()方法。该方法对应的图如下：

DequeStack解释说addFirst(e)push(e)将数据插入到栈顶，失败则抛出异常。 OfferFirst(e) 不会向栈顶插入任何数据，如果失败则返回false。 removeFirst() pop() 获取并删除栈顶的数据。如果失败，则抛出异常。 pollFirst() 不会检索和删除堆栈顶部的数据。如果失败，则返回null。 getFirst() peek() 查询栈顶的数据。如果失败，则会抛出异常。 peekFirst() 不会查询栈顶的数据。如果失败，则返回null。

FIFO：Deque VS Queue

上面说了，Deque继承自Queue接口，所以两者肯定是相关的。我们来看看这两个接口的情况。

首先，Queue是队列，数据结构是FIFO（先进先出），也就是说元素的添加发生在末尾，元素的删除发生在开头。

与上图中的add(e)和element()方法类似，Deque中也有相应的方法。

两个接口中的方法对应图如下：

DequeQueue解释说addLast(e)add(e)在尾部插入数据，失败则抛出异常。 OfferLast(e) Offer(e) 在尾部插入数据，如果失败则返回false。 removeFirst()remove() 获取并删除第一个数据，如果失败则抛出异常。异常pollFirst() poll() 获取并删除第一个数据。如果失败，则返回null。 getFirst()element() 查询第一个数据。如果失败，则会抛出异常。 peekFirst()peek()查询第一条数据。如果失败，则返回null。

使用场景

无论是Stack还是Queue，它们都只能操作头部或尾部。那么如何同时支持头部和尾部的操作呢？这体现了Deque（双边队列）的优点，即Deque既可以用于LIFO，也可以用于LIFO。也可用于FIFO。

Deque和List最大的区别是不支持对元素进行索引访问，但是Deque也提供了相应的方法来操作指定元素：removeFirstOccurrence(Object o) 和removeLastOccurrence(Object o)

Deque是数据结构的标准接口，仅定义标准方法。有几个类实现了这个接口，比如常用的ArrayDeque、LinkedList、ConcurrentLinkedDeque。

上面列出的三个类是我们常用的实现。看名字就知道ArrayDeque是基于数组的，LinkedList和ConcurrentLinkedDeque显然是基于链表的，而且后者是线程安全的。

这三类的主要特点和应用场景如下表所示：

类特性使用场景ArrayDeque 数组大小可变，涉及自动扩展无序不可插入Null 线程不安全LinkedList 链表大小可变，无需扩展无序可插入Null 线程不安全ConcurrentLinkedDeque 链表大小可变，无需扩展无序不能插入Null 线程安全

继承关系如下图所示：

ArrayDeque

我们从源码层面介绍一下它最重要的方法：添加和删除。另外，ArrayDeque底层是一个数组，所以很自然的想到了数组的固有方法：扩容。

数据结构

数据结构很简单，没什么好说的，我们应该能猜到，就是一个数组，而且因为需要操作头尾，所以必须有头索引和尾索引。

public class ArrayDequeE extends AbstractCollectionE Implements DequeE, Cloneable, Serialized { //底层数据结构是一个数组瞬态Object[] 元素； //头索引瞬态int head; //尾部索引瞬态int tail; //最小容量为8 private static final int MIN_INITIAL_CAPACITY=8;}

构造函数

构造函数共有三个，分别是：

无参数构造（初始化一个容量为16的数组）。参数构造，参数为指定容量。参数构造，参数为Collection集合。接下来介绍第二个参数构造，即初始化一个指定容量的数组。为什么我们需要将它分开？我们来说说吧，因为初始化容量是有一定规则的。

//初始化一个指定容量的Dequeprivate void allocateElements(int numElements) { //初始化的数组容量始终是2的幂次方=new Object[calculateSize(numElements)];} 记住上面的【HashMap详细解释】结构]，我们讲了它扩展时比较麻烦的操作。这里，ArrayDeque也和之前一样，即扩展时，容量始终是2的幂。

与HashMap不同的是，HashMap中有一个-1动作，即计算出的容量始终大于等于参数。例如，如果参数为8，则返回值也是8。但是，这里计算的容量始终大于参数。例如，如果参数为8，则返回值为16。

//计算容量，容量始终为2的幂//最小容量为8 //返回值为>传入参数的private static intcalculateSize(int numElements) { //最小容量intinitialCapacity=最小初始容量； if (numElements=初始容量) { 初始容量=numElements;初始容量|=(初始容量1);初始容量|=(初始容量2);初始容量|=(初始容量4);初始容量|=(初始容量8);初始容量|=（初始容量16）；初始容量++； if (初始容量0) 初始容量=1; } return initialCapacity;} 上面的位操作非常精妙，就不赘述了。具体可以阅读之前的文章【HashMap数据结构详解】，然后精妙的计算逻辑是贴一张上一篇的图：

总的原则是保证低位以上每一位都为1，最后一位+1。这样，除了高位之外的所有位都是0，也就是2的幂。

扩容

当容量不够时，肯定需要扩容。具体扩容时机暂不赘述。稍后讨论添加元素的方法时我会详细介绍。下面结合源码讲解一下扩展的方法：

//将容量扩展至大小的2 倍private void doubleCapacity() { //断言，如果为true，则继续，如果为false，则抛出AssertionError 异常assert head==tail; int p=头； //当前容量int n=elements.length; //p 右侧的元素个数int r=n – p; //新容量加倍int newCapacity=n 1; if (newCapacity 0) throw new IllegalStateException(‘抱歉，双端队列太大’); //新数组Object[] a=new Object[newCapacity]; //将head右侧的数据复制到目标数组的索引0处//接下来的五个参数分别是：元数据和元数据中需要复制的元素的起始位置、目标数据、起始位置目标数据中要粘贴的元素，数据长度System.arraycopy(elements, p, a, 0, r); //将head左侧的数据复制到目标数组r索引中System.arraycopy(elements, 0, a, r, p);元素=a； //头索引head=0; //尾部索引tail=n;} 注意，上面的扩容操作涉及到将元数据复制到新数组的操作，这里是通过两次副本来进行的。为什么要这样做？其实这涉及到元素的添加，下面会讲到。

添加元素

为了添加元素，我们介绍两种典型的方法。其他类似，即头加法和尾加法，即addFirst(E e)和addLast(E e)。

//向第一个添加元素public void addFirst(E e) { //插入的元素不能为null，否则会抛出空指针异常if (e==null) throw new NullPointerException(); //将第一个索引减一，并将该索引处的元素设置为e elements[head=(head – 1) (elements.length – 1)]=e; //判断是否需要扩容if (head==tail) doubleCapacity(); //向尾部添加元素public void addLast(E e) { //插入的元素不能为null，否则会抛出空指针异常if (e==null) throw new NullPointerException(); //将尾部索引处的元素设置为e elements[tail]=e; //将尾部索引后移一位，判断是否需要扩容if ( (tail=(tail + 1) (elements.length – 1))==head) doubleCapacity();} 从上面的源码我们可以可以看到几个有趣的点：

当向头部添加元素时，先将头部索引向前移动，然后再添加元素。请注意，头部索引处有一个元素。当向尾部添加元素时，直接将该元素添加到尾部索引，然后将尾部索引向后移动。注意，tail索引处没有元素。可见数组中一定有一个空索引，即尾部索引。因此，可以先插入元素，然后再进行扩展。扩展的判断条件是判断首尾索引是否一致，即head==向尾部头部添加元素时，如果head 为0，则执行elements[head=(head – 1) (elements .length – 1)]=e;操作，head – 1=-1，元素。 length – 1=15，两者进行“与”运算时，因为“-1”的二进制数实际上是“1111 1111.1111”，即所有位都是1，所以结果AND运算自然也是15。

下面画一张图来介绍以下元素的插入过程：

移除元素

Deque 无法根据索引删除元素。只能删除第一个和最后一个元素（pollFirst()、pollLast()），或者删除指定内容的元素（removeFirstOccurrence(Object o)、removeLastOccurrence(Object o)）

//删除头元素public E pollFirst() { //头索引int h=head; @SuppressWarnings(‘unchecked’) E 结果=(E) elements[h]; //如果双端队列为空，则元素为null if (result==null) return null; //将标头索引处的元素设置为null elements[h]=null; //必须将slot 清空//调整header 索引head=(h + 1) (elements.length – 1); return result ;}//删除尾部元素public E pollLast() { //尾部索引之前的索引，因为尾部索引指向的索引没有元素int t=(tail – 1) (elements.length – 1）； @ SuppressWarnings(‘unchecked’) E 结果=(E) elements[t]; if (结果==null) 返回null; //设置为空elements[t]=null;尾=t； return result;}删除元素代码其实很简单。有趣的是，删除元素后，数组可能在数组的前面和后面都有数据，也可能在数组的中间有数据。也就是说head不一定总是等于0，tail也不一定总是等于0。并不总是比head大。所以我们称之为循环数组。

LinkedList

LinkedList 与ArrayDeque 相比，底层数据结构从数组变成了链表，所以LinkedList 自然不需要扩展。

LinkedList是由NodeV一一组成的。每个节点都会记录当前数据、前一个节点和后一个节点，这样就形成了一个链表。数据模型如下：

具体方法我就不详细说了，比较简单。

public class LinkedListE extends AbstractSequentialListE Implements ListE, DequeE, Cloneable, java.io.Serialized { //链表长度瞬态int size=0; //第一个元素瞬态NodeE优先； //最后一个元素transient NodeE last; //各个节点的数据结构private static class NodeE { E item;接下来是NodeE； NodeE 上一个； Node(NodeE prev, E element, NodeE next) { this.item=element;这.下一个=下一个；这. 上一个=上一个； } } }

ConcurrentLinkedDeque

上面提到的ArrayDeque和LinkedList都是List包下的工具类，其中ConcurrentLinkedDeque比较有趣。它是concurrent包下的一个类。其实我们看名字就应该能明白其中的一两个。它是一个线程安全的无限双端队列。

它的内部变量都是用volatile 修饰的，所以是线程安全的。因为易失性的作用是防止变量访问前后指令的重新排列，从而保证指令的顺序执行。

另外，内部采用了spin+CAS的非阻塞算法，保证线程并发访问时数据的一致性。例如，向header addFirst(E e) 方法添加元素：

public void addFirst(E e) { linkFirst(e);}/** * 将e 链接为第一个元素。 */private void linkFirst(E e) { //检查要插入的元素是否为空checkNotNull(e);最终NodeE newNode=新NodeE(e); //锚点设计是为了方便多层for循环的内部for循环。可以直接继续锚点restartFromHead: for (;) //从头节点第一个节点开始向前搜索for (NodeE h=head, p=h, q;) { if ((q=p.prev) !=null (q=(p=q).prev) !=null) //每隔一跳检查头部更新。 //如果p==q，我们肯定会跟随head 。 //如果head 被修改，则返回head 再次查找p=(h !=(h=head)) ? h : q； else if (p.next==p) //PREV_TERMINATOR 继续restartFromHead; else { //p 是第一个节点newNode.lazySetNext(p); //CAS 搭载if (p.casPrev(null, newNode)) { //成功的CAS 是线性化点//e 成为此双端队列的元素， //并且newNode 变为“活动”。 if (p !=h) //一次跳两个节点casHead(h, newNode); //失败也没关系。返回； } //与另一个线程的CAS 竞争失败；重读prev } }}执行流程大致如下：

从头节点开始向前循环找到第一个节点（p.prev==nullp.next!=p），然后通过lazySetNext将新节点的下一个节点设置为firstCAS，并将first的prev修改为新节点。注意，CAS指令成功后，会判断第一个节点是否跳转了两个节点。只有跳转两个节点后，CAS才会更新头部。这也是为了节省CAS指令的执行成本。