Java 集合深入理解(10):Deque 双端队列

什么是 Deque

DequeDouble ended queue (双端队列) 的缩写,读音和 deck 一样,蛋壳。

Deque 继承自 Queue,直接实现了它的有 LinkedList, ArayDeque, ConcurrentLinkedDeque 等。

Deque 支持容量受限的双端队列,也支持大小不固定的。一般双端队列大小不确定。

Deque 接口定义了一些从头部和尾部访问元素的方法。比如分别在头部、尾部进行插入、删除、获取元素。和 Queue

类似,每个操作都有两种方法,一种在异常情况下直接抛出异常奔溃,另一种则不会抛异常,而是返回特殊的值,比如 false, null …

插入(Insert)方法的第二种是针对固定大小的双端队列设计的。大多数情况下 插入都不会失败。

Deque 继承了 Queue 接口的方法。当 Deque 当做 队列使用时(FIFO),添加元素是添加到队尾,删除时删除的是头部元素。从 Queue 接口继承的方法对应容器的方法如图所示:

Deque 也能当栈用(后进先出)。这时入栈、出栈元素都是在 双端队列的头部 进行。Deque 中和栈对应的方法如图所示:

Deque 包含的方法如下图所示:

根据名字就能看到功能,具体实现我们下篇看 LinkedList 源码时介绍。

Deque 的实现类

Deque 的实现类主要分为两种场景:

  • 一般场景
    • LinkedList 大小可变的链表双端队列,允许元素为 null
    • ArrayDeque 大下可变的数组双端队列,不允许 null
  • 并发场景
    • LinkedBlockingDeque 如果队列为空时,获取操作将会阻塞,知道有元素添加

Deque 与 工作密取

在并发编程 中,双端队列 Deque 还用于 “工作密取” 模式。

什么是工作密取呢?

在 生产者-消费者 模式中,所有消费者都从一个工作队列中取元素,一般使用阻塞队列实现;

而在 工作密取 模式中,每个消费者有其单独的工作队列,如果它完成了自己双端队列中的全部工作,那么它就可以从其他消费者的双端队列末尾秘密地获取工作。

工作密取 模式 对比传统的 生产者-消费者 模式,更为灵活,因为多个线程不会因为在同一个工作队列中抢占内容发生竞争。在大多数时候,它们只是访问自己的双端队列。即使需要访问另一个队列时,也是从 队列的尾部获取工作,降低了队列上的竞争程度。

Thanks

https://docs.oracle.com/javase/tutorial/collections/interfaces/deque.html https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html http://www.nowamagic.net/librarys/veda/detail/2296 《Java 并发编程实战》

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏乐百川的学习频道

设计模式(二十四) 访问者模式

访问者模式提供了一种方法,将算法和数据结构分离。假设我们需要对一个数据结构进行不同的操作,就可以考虑使用访问者模式。访问者模式的要点在于,需要一个访问者接口,提...

2116
来自专栏乐享123

C:dynamic Array in Stack

1285
来自专栏Python爬虫与算法进阶

学点算法之队列的学习及应用

约瑟夫问题 约瑟夫问题 有 n 个囚犯站成一个圆圈,准备处决。首先从一个人开始,越过k-2个人(因为第一个人已经被越过),并杀掉第k个人。接着,再越过 k-1个...

3607
来自专栏精讲JAVA

用 Maven 实现一个 protobuf 的 Java 例子

Protocal Buffers(简称protobuf)是谷歌的一项技术,用于结构化的数据序列化、反序列化,常用于RPC 系统(Remote Procedure...

1142
来自专栏贾老师の博客

Lock-Free 学习总结

在通常使用 Mutex 互斥锁的场景, 有的线程抢占了锁, 其他线程则会被阻塞, 当获得锁的进程挂掉之后, 整个程序就 block 住了. 但在 Lock-Fr...

4153
来自专栏calmound

缺省参数是编译期间绑定的,而不是动态绑定

看一个程序 #include <iostream> using namespace std; class A { public: virtual void ...

3216
来自专栏大内老A

WCF技术剖析之十四:泛型数据契约和集合数据契约(上篇)

在.NET Framework 2.0中,泛型第一次被引入。我们可以定义泛型接口、泛型类型、泛型委托和泛型方法。序列化依赖于真实具体的类型,而泛型则刻意模糊了具...

2218
来自专栏铭毅天下

干货 | Elasticsearch Nested类型深入详解

本文通过一个例子将Nested类型适合解决的问题、应用场景、使用方法串起来, 文中所有的DSL都在Elasticsearch6.X+验证通过。

1663
来自专栏猿人谷

设计模式分类

     在《设计模式》这本书中列举并描述了23种设计模式,分为创建型模式、结构型模式和行为型模式。另外,近来这一清单又增加了一些类别,例如,并发型模式、线程池...

1935
来自专栏java工会

Java异常处理的误区和经验总结

1395

扫码关注云+社区