在Java中,deque和queue的区别与应用
队列(queue)简述
队列(queue)是一种常用的数据结构,可以将队列看做是一种特殊的线性表,该结构遵循的先进先出原则。Java中,LinkedList实现了Queue接口,因为LinkedList进行插入、删除操作效率较高。
在处理元素前用于保存元素的 collection。除了基本的 Collection 操作外,队列还提供其他的插入、提取和检查操作。每个方法都存在两种形式:一种抛出异常(操作失败时),另一种返回一个特殊值(null 或 false,具体取决于操作)。插入操作的后一种形式是用于专门为有容量限制的 Queue
|
抛出异常 |
返回特殊值 |
插入 |
add(e) |
offer(e) |
移除 |
remove() |
poll() |
检查 |
element() |
peek() |
队列通常(但并非一定)以 FIFO(先进先出)的方式排序各个元素。不过优先级队列和 LIFO 队列(或堆栈)例外,前者根据提供的比较器或元素的自然顺序对元素进行排序,后者按 LIFO(后进先出)的方式对元素进行排序。无论使用哪种排序方式,队列的头 都是调用 remove() 或 poll() 所移除的元素。在 FIFO 队列中,所有的新元素都插入队列的末尾。其他种类的队列可能使用不同的元素放置规则。每个 Queue
Queue 接口并未定义阻塞队列的方法,而这在并发编程中是很常见的。 BlockingQueue 接口定义了那些等待元素出现或等待队列中有可用空间的方法,这些方法扩展了此接口。
Queue 实现通常不允许插入 null 元素,尽管某些实现(如 LinkedList)并不禁止插入 null。即使在允许 null 的实现中,也不应该将 null 插入到 Queue 中,因为 null 也用作 poll
Queue 实现通常未定义 equals 和 hashCode 方法的基于元素的版本,而是从 Object
Queue常用方法:
- boolean add(E e);将指定的元素插入此队列(如果立即可行且不会违反容量限制),在成功时返回 true,如果当前没有可用的空间,则抛出 IllegalStateException。
- boolean offer(E e);将指定的元素插入此队列(如果立即可行且不会违反容量限制),当使用有容量限制的队列时,此方法通常要优于 add(E),后者可能无法插入元素,而只是抛出一个异常。
- E remove();获取并移除此队列的头。
- E poll();获取并移除此队列的头,如果此队列为空,则返回 null。
- E element();获取,但是不移除此队列的头。
- E peek();获取但不移除此队列的头;如果此队列为空,则返回 null。
双端队列(Deque)简述
双向队列(Deque),是Queue的一个子接口,双向队列是指该队列两端的元素既能入队(offer)也能出队(poll),如果将Deque限制为只能从一端入队和出队,则可实现栈的数据结构。对于栈而言,有入栈(push)和出栈(pop),遵循先进后出原则。
一个线性 collection,支持在两端插入和移除元素。名称 deque 是“double ended queue(双端队列)”的缩写,通常读为“deck”。大多数 Deque
此接口定义在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。每种方法都存在两种形式:一种形式在操作失败时抛出异常,另一种形式返回一个特殊值(null 或 false,具体取决于操作)。插入操作的后一种形式是专为使用有容量限制的 Deque
下表总结了上述 12 种方法:
|
第一个元素(头部) |
最后一个元素(尾部) |
||
|
抛出异常 |
特殊值 |
抛出异常 |
特殊值 |
插入 |
addFirst(e) |
offerFirst(e) |
addLast(e) |
offerLast(e) |
移除 |
removeFirst() |
pollFirst() |
removeLast() |
pollLast() |
检查 |
getFirst() |
peekFirst() |
getLast() |
peekLast() |
此接口扩展了 Queue 接口。在将双端队列用作队列时,将得到 FIFO(先进先出)行为。将元素添加到双端队列的末尾,从双端队列的开头移除元素。从 Queue 接口继承的方法完全等效于 Deque
此接口扩展了 Queue 接口。在将双端队列用作队列时,将得到 FIFO(先进先出)行为。将元素添加到双端队列的末尾,从双端队列的开头移除元素。从 Queue 接口继承的方法完全等效于 Deque
Queue |
等效 Deque |
add(e) |
addLast(e) |
offer(e) |
offerLast(e) |
remove() |
removeFirst() |
poll() |
pollFirst() |
element() |
getFirst() |
peek() |
peekFirst() |
双端队列也可用作 LIFO(后进先出)堆栈。应优先使用此接口而不是遗留 Stack 类。在将双端队列用作堆栈时,元素被推入双端队列的开头并从双端队列开头弹出。堆栈方法完全等效于 Deque
堆栈方法 |
等效 Deque |
push(e) |
addFirst(e) |
pop() |
removeFirst() |
peek() |
peekFirst() |
注意,在将双端队列用作队列或堆栈时, peek 方法同样正常工作;无论哪种情况下,都从双端队列的开头抽取元素。
此接口提供了两种移除内部元素的方法: removeFirstOccurrence 和 removeLastOccurrence。
与 List 接口不同,此接口不支持通过索引访问元素。
虽然 Deque 实现没有严格要求禁止插入 null 元素,但建议最好这样做。建议任何事实上允许 null 元素的 Deque 实现用户最好不 要利用插入 null 的功能。这是因为各种方法会将 null
Deque 实现通常不定义基于元素的 equals 和 hashCode 方法,而是从 Object 类继承基于身份的 equals 和 hashCode
从以下版本开始:
1.6
方法摘要 | |
|
将指定元素插入此双端队列所表示的队列(换句话说,此双端队列的尾部),如果可以直接这样做而不违反容量限制的话;如果成功,则返回 true,如果当前没有可用空间,则抛出 IllegalStateException。 |
|
将指定元素插入此双端队列的开头(如果可以直接这样做而不违反容量限制)。 |
|
将指定元素插入此双端队列的末尾(如果可以直接这样做而不违反容量限制)。 |
|
如果此双端队列包含指定元素,则返回 true。 |
|
返回以逆向顺序在此双端队列的元素上进行迭代的迭代器。 |
|
获取,但不移除此双端队列所表示的队列的头部(换句话说,此双端队列的第一个元素)。 |
|
获取,但不移除此双端队列的第一个元素。 |
|
获取,但不移除此双端队列的最后一个元素。 |
|
返回以恰当顺序在此双端队列的元素上进行迭代的迭代器。 |
|
将指定元素插入此双端队列所表示的队列(换句话说,此双端队列的尾部),如果可以直接这样做而不违反容量限制的话;如果成功,则返回 true,如果当前没有可用的空间,则返回 false。 |
|
在不违反容量限制的情况下,将指定的元素插入此双端队列的开头。 |
|
在不违反容量限制的情况下,将指定的元素插入此双端队列的末尾。 |
|
获取,但不移除此双端队列所表示的队列的头部(换句话说,此双端队列的第一个元素);如果此双端队列为空,则返回 null。 |
|
获取,但不移除此双端队列的第一个元素;如果此双端队列为空,则返回 null。 |
|
获取,但不移除此双端队列的最后一个元素;如果此双端队列为空,则返回 null。 |
|
获取并移除此双端队列所表示的队列的头部(换句话说,此双端队列的第一个元素);如果此双端队列为空,则返回 null。 |
|
获取并移除此双端队列的第一个元素;如果此双端队列为空,则返回 null。 |
|
获取并移除此双端队列的最后一个元素;如果此双端队列为空,则返回 null。 |
|
从此双端队列所表示的堆栈中弹出一个元素。 |
|
将一个元素推入此双端队列所表示的堆栈(换句话说,此双端队列的头部),如果可以直接这样做而不违反容量限制的话;如果成功,则返回 true,如果当前没有可用空间,则抛出 IllegalStateException。 |
|
获取并移除此双端队列所表示的队列的头部(换句话说,此双端队列的第一个元素)。 |
|
从此双端队列中移除第一次出现的指定元素。 |
|
获取并移除此双端队列第一个元素。 |
|
从此双端队列移除第一次出现的指定元素。 |
|
获取并移除此双端队列的最后一个元素。 |
|
从此双端队列移除最后一次出现的指定元素。 |
|
返回此双端队列的元素数。 |
下一篇: 排队概念与常见求职面试中的难题探讨
推荐阅读
-
Java 8新特性探究(十三)JavaFX 8新特性以及开发2048游戏-JavaFX历史## 跟java在服务器端和web端成绩相比,桌面一直是java的软肋,于是Sun公司在2008年推出JavaFX,弥补桌面软件的缺陷,请看下图JavaFX一路走过来的改进 从上图看出,一开始推出时候,开发者需使用一种名为JavaFX Script的静态的、声明式的编程语言来开发JavaFX应用程序。因为JavaFX Script将会被编译为Java bytecode,程序员可以使用Java代码代替。 JavaFX 2.0之后的版本摒弃了JavaFX Script语言,而作为一个Java API来使用。因此使用JavaFX平台实现的应用程序将直接通过标准Java代码来实现。 JavaFX 2.0 包含非常丰富的 UI 控件、图形和多媒体特性用于简化可视化应用的开发,WebView可直接在应用中嵌入网页;另外 2.0 版本允许使用 FXML 进行 UI 定义,这是一个脚本化基于 XML 的标识语言。 从JDK 7u6开始,JavaFx就与JDK捆绑在一起了,JavaFX团队称,下一个版本将是8.0,目前所有的工作都已经围绕8.0库进行。这是因为JavaFX将捆绑在Java 8中,因此该团队决定跳过几个版本号,迎头赶上Java 8。 ##JavaFx8的新特性 ## ###全新现代主题:Modena 新的Modena主题来替换原来的Caspian主题。不过在Application的start方法中,可以通过setUserAgentStylesheet(STYLESHEET_CASPIAN)来继续使用Caspian主题。 参考http://fxexperience.com/2013/03/modena-theme-update/ ###JavaFX 3D 在JavaFX8中提供了3D图像处理API,包括Shape3D (Box, Cylinder, MeshView, Sphere子类),SubScene, Material, PickResult, LightBase (AmbientLight 和PointLight子类),SceneAntialiasing等。Camera类也得到了更新。从JavaDoc中可以找到更多信息。 ###富文本 强化了富文本的支持 ###TreeTableView ###日期控件DatePicker 增加日期控件 ###用于 CSS 结构的公共 API
-
Django框架的特点和优势在基于Django的电商项目的设计与实现中的应用
-
Java中获取当前日期和时间的多种方法:详解New Date与java.util.Date的区别
-
Java开发者的日常生活:POI和JDBC的运用,以及Mockmvc在单元测试中的应用
-
实例化和抗锯齿在QT与OpenGL中的应用示例
-
实战详解:Java包扫描在Jar包中的应用与实现
-
【摩尔线程+Colossal-AI强强联手】MusaBert登上CLUE榜单TOP10:技术细节揭秘 - 技术实力:摩尔线程凭借"软硬兼备"的技术底蕴,让MusaBert得以从底层优化到顶层。其内置多功能GPU配备AI加速和并行计算模块,提供了全面的AI与科学计算支持,为AI推理和低资源条件下的大模型训练等场景带来了高效、经济且环保的算力。 - 算法层面亮点:依托Colossal-AI AI大模型开发系统,MusaBert在训练过程中展现出了卓越的并行性能与易用性,特别在预处理阶段对DataLoader进行了优化,适应低资源环境高效处理海量数据。同时,通过精细的建模优化、领域内数据增强以及Adan优化器等手段,挖掘和展示了预训练语言模型出色的语义理解潜力。基于MusaBert,摩尔线程自主研发的MusaSim通过对比学习方法微调,结合百万对标注数据,MusaSim在多个任务如语义相似度、意图识别和情绪分析中均表现出色。 - 数据资源丰富:MusaBert除了自家高质量语义相似数据外,还融合了悟道开源200GB数据、CLUE社区80GB数据,以及浪潮公司提供的1TB高质量数据,保证模型即便在较小规模下仍具备良好性能。 当前,MusaBert已成功应用于摩尔线程的智能客服与数字人项目,并广泛服务于语义相似度、情绪识别、阅读理解与声韵识别等领域。为了降低大模型开发和应用难度,MusaBert及其相关高质量模型代码已在Colossal-AI仓库开源,可快速训练优质中文BERT模型。同时,通过摩尔线程与潞晨科技的深度合作,仅需一张多功能GPU单卡便能高效训练MusaBert或更大规模的GPT2模型,显著降低预训练成本,进一步推动双方在低资源大模型训练领域的共享目标。 MusaBert荣登CLUE榜单TOP10,象征着摩尔线程与潞晨科技联合研发团队在中文预训练研究领域的领先地位。展望未来,双方将携手探索更大规模的自然语言模型研究,充分运用上游数据资源,产出更为强大的模型并开源。持续强化在摩尔线程多功能GPU上的大模型训练能力,特别是在消费级显卡等低资源环境下,致力于降低使用大模型训练的门槛与成本,推动人工智能更加普惠。而潞晨科技作为重要合作伙伴,将继续发挥关键作用。
-
在Spring MVC中,理解@Controller和@RequestMapper的作用与区别
-
深入理解Java中Lock和tryLock方法的工作原理与应用
-
在Node.js中轻松理解和应用JWT与Session的区别与用法