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 条评论
登录 后参与评论

相关文章

来自专栏chenssy

【死磕Java并发】—–深入分析volatile的实现原理

通过前面一章我们了解了synchronized是一个重量级的锁,虽然JVM对它做了很多优化,而下面介绍的volatile则是轻量级的synchronized。如...

3237
来自专栏大闲人柴毛毛

Java并发容器大合集

概述         java.util包中的大部分容器都是非线程安全的,若要在多线程中使用容器,你可以使用Collections提供的包装函数:synchro...

3646
来自专栏IT技术精选文摘

Java内存模型

在多核时代,如何提高CPU的性能成为了一个永恒的话题,而这个话题的讨论主要就是如何定义一个高性能的内存模型,内存模型用于定义处理器的各层缓存与共享内存的同步机制...

18510
来自专栏人人都是极客

如何设计嵌入式系统?带你理解一个小型嵌入式操作系统的精髓

1 多任务机制 其实在单一CPU 的情况下,是不存在真正的多任务机制的,存在的只有不同的任务轮流使用CPU,所以本质上还是单任务的。但由于CPU执行速度非常快,...

2617
来自专栏函数式编程语言及工具

Scalaz(32)- Free :lift - Monad生产线

    在前面的讨论里我们提到自由数据结构就是产生某种类型的最简化结构,比如:free monoid, free monad, free category等等。...

1765
来自专栏desperate633

浅谈数据库查询优化的几种思路

应尽量避免全表扫描,首先应考虑在 where 及 order by ,group by 涉及的列上建立索引

751
来自专栏orientlu

FreeRTOS 信号量

FreeRTOS 信号量和互斥锁是基于队列实现的, 队列介绍见 << FreeRTOS 消息队列 >>。 使用信号量需要在源文件中包含头文件 semphr....

742
来自专栏java一日一条

死磕Java并发:深入分析volatile的实现原理

通过前面一章我们了解了synchronized是一个重量级的锁,虽然JVM对它做了很多优化,而下面介绍的volatile则是轻量级的synchronized。如...

362
来自专栏Java编程

40个Java多线程问题总结

个人认为,学习,内容越多、越杂的知识,越需要进行深刻的总结,这样才能记忆深刻,将知识变成自己的。这篇文章主要是对多线程的问题进行总结的,因此罗列了40个多线程的...

4951
来自专栏Java架构师进阶

java多线程高级教程,这些你都懂了吗?

一、countdownLatch和cyclicbarrier(这两个做多线程控制很好用,工作中会经常用到)

684

扫码关注云+社区