双边队列Deque详解

原文发布于自己的博客平台【http://www.jetchen.cn/deque/】简介这是数据结构系列的第二篇文章,上篇文章见: 【详解 HashMap 数据

大家好,今天给各位分享双边队列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;}

构造函数

双边队列Deque详解

构造函数共有三个,分别是:

无参数构造(初始化一个容量为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指令的执行成本。

小结

Deque双边队列的数据结构为两端数据的操作提供了便利,也是官方推荐的替代Stack数据结构的方案。另外,它不仅有最常用的ArrayDeque,还有线程安全的ConcurrentLinkedDeque。数据结构也比较丰富。

用户评论

双边队列Deque详解
龙吟凤

终于找到了详细讲解双向队列!(deque) 的文章!之前一直没明白它的特点和应用场景,这篇文章把一些关键点都阐述清楚了,比如它的进出栈效率,以及在某些算法中的优势。感觉这下能更好地理解它了!

    有12位网友表示赞同!

双边队列Deque详解
暮光薄凉

Deque 确实是个很实用的数据结构,这篇文写的很棒,解释得很详细,各种示例也很生动形象地展示了 deque 的用法。以前没觉得它有什么特别的地方,看了这篇文章才知道它在哪些地方特别有用。

    有17位网友表示赞同!

双边队列Deque详解
旧爱剩女

作为一名程序员,了解不同的数据结构对代码设计非常重要,这篇博客讲解双向队列 (Deque) 还是很不错的啊!之前虽然知道它的名字,但对于具体用法一直不太清楚,现在终于看明白了!

    有9位网友表示赞同!

双边队列Deque详解
醉红颜

我觉得标题太直白了,"详解"有点过于严谨,应该用更吸引人的词语来概括文章内容的重点。例如:"双向队列(Deque): 让你轻松解决进出栈难题!" 这样会更有吸引力。

    有17位网友表示赞同!

双边队列Deque详解
断秋风

这篇文章讲得非常详细,完全满足了我的学习需求!特别是对于 deque 在实际应用中的场景分析,很有参考意义。希望以后还能看到更多这样高质量的文章!

    有8位网友表示赞同!

双边队列Deque详解
今非昔比'

文章写得很清晰易懂,把Deque的一些关键特性解释得很好理解,包括其与优先队列、栈和队列的区别等。 不过我觉得文章内容可以再丰富一点,比如加入一些实际项目中的应用案例,那样更能帮助读者理解 deque 的价值。

    有11位网友表示赞同!

双边队列Deque详解
封心锁爱

原来双向队列 (deque) 可以这么灵活使用啊!之前一直把它和一般的队列或栈混淆了。这篇博客把它们的差异点解释得非常清楚,现在我终于明白了,deque 真让人眼前一亮!

    有19位网友表示赞同!

双边队列Deque详解
浮光浅夏ζ

对入门者来说,文章的语言还是比较专业,可能不太容易理解。建议加入一些通俗易懂的例子来解释 deque 的含义和原理,这样更容易帮助新手入门。

    有10位网友表示赞同!

双边队列Deque详解
拥抱

双向队列的实现方法多种多样,这篇文章重点介绍了其中的几种常见实现方式,讲解也很清晰详细。我很想进一步了解一下这些实现方法的优缺点比较,以及在不同场景下应该选择哪种方案。

    有17位网友表示赞同!

双边队列Deque详解
£烟消云散

感觉这篇博客讲得很有深度,对 deque 的理解范围相当广泛,涵盖了原理、特性、应用等各个方面。不愧是详解!

    有5位网友表示赞同!

双边队列Deque详解
安陌醉生

文章介绍得很详细,但是我觉得代码示例部分可以再丰富一些,加入更多不同场景下的应用代码,比如使用 deque 实现LRU缓存算法或者滑动窗口等,这样能更好地帮助读者理解 deque 的实际运用。

    有8位网友表示赞同!

双边队列Deque详解
逾期不候

看了这篇文章后,我对双向队列 (deque) 的认识有了很大提升。原来它不仅限于进出栈操作,还可以用于其他场景,例如数据处理、游戏开发等等。真是太棒了!

    有9位网友表示赞同!

双边队列Deque详解
毒舌妖后

这篇文章写得的确不错,但个人觉得一些术语定义的解释可以更详细一点,比如 "插入/删除头和尾" 的具体细节,以及 deque 的时间复杂度分析。这样对读者理解会更加清晰。

    有13位网友表示赞同!

双边队列Deque详解
西瓜贩子

双向队列 (deque) 确实是个非常实用的数据结构啊!之前我还在考虑用数组来模拟栈的操作,看了这篇文章后才知道 deque 就直接满足了我的需求!

    有19位网友表示赞同!

双边队列Deque详解
。婞褔vīp

我觉得文章内容有些繁琐,对于没有编程基础的人来说可能不太容易理解。建议加入一些通俗易懂的比喻或者漫画图解,这样能让读者更轻松地掌握双向队列的概念。

    有19位网友表示赞同!

双边队列Deque详解
墨染年华

这篇文章让我对 deque 这种数据结构有了更深入的了解,它在一些算法中的应用确实很有优势。我现在更想去尝试一下把 deque 应用到我的程序中看看效果!

    有14位网友表示赞同!

双边队列Deque详解
从此我爱的人都像你

总而言之,这篇博客对双向队列 (Deque) 的讲解很全面,内容丰富且易懂。对于想要学习数据结构的朋友来说,绝对是一个不错的参考材料!

    有8位网友表示赞同!

原创文章,作者:小su,如若转载,请注明出处:https://www.sudun.com/ask/123974.html

(0)
小su的头像小su
上一篇 2024年9月1日 下午6:08
下一篇 2024年9月1日 下午6:13

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注