java deque_java 集合框架(十五)Deque

迈不过友情╰ 2022-11-01 15:50 251阅读 0赞

一.概述

Deque是Queue的子接口,我们知道Queue是一种队列形式,而Deque则是双向队列,它支持从两个端点方向检索和插入元素,因此Deque既可以支持LIFO形式也可以支持LIFO形式.Deque接口是一种比Stack和Vector更为丰富的抽象数据形式,因为它同时实现了以上两者.

二.主要方法

修饰符和返回值

方法名

描述

添加功能

void

push(E)

向队列头部插入一个元素,失败时抛出异常

void

addFirst(E)

向队列头部插入一个元素,失败时抛出异常

void

addLast(E)

向队列尾部插入一个元素,失败时抛出异常

boolean

offerFirst(E)

向队列头部加入一个元素,失败时返回false

boolean

offerLast(E)

向队列尾部加入一个元素,失败时返回false

获取功能

E

getFirst()

获取队列头部元素,队列为空时抛出异常

E

getLast()

获取队列尾部元素,队列为空时抛出异常

E

peekFirst()

获取队列头部元素,队列为空时返回null

E

peekLast()

获取队列尾部元素,队列为空时返回null

删除功能

boolean

removeFirstOccurrence(Object)

删除第一次出现的指定元素,不存在时返回false

boolean

removeLastOccurrence(Object)

删除最后一次出现的指定元素,不存在时返回false

弹出功能

E

pop()

弹出队列头部元素,队列为空时抛出异常

E

removeFirst()

弹出队列头部元素,队列为空时抛出异常

E

removeLast()

弹出队列尾部元素,队列为空时抛出异常

E

pollFirst()

弹出队列头部元素,队列为空时返回null

E

pollLast()

弹出队列尾部元素,队列为空时返回null

迭代器

Iterator

descendingIterator()

返回队列反向迭代器

可以看出Deque在Queue的方法上新添了对队列头尾元素的操作,add,remove,get形式的方法会在有界队列满员和空队列时抛出异常,offer,poll,peek形式的方法则会返回false或null.

此外方法表中需要注意push = addFirst,pop = removeFirst,只是使用了不同的方法名体现队列表示栈结构时的特点.

三.实现

同Queue一样Deque的实现也可以划分成通用实现和并发实现.

通用实现主要有两个实现类ArrayDeque和LinkedList.

ArrayDeque是个可变数组,它是在Java 6之后新添加的,而LinkedList是一种链表结构的list.LinkedList要比ArrayDeque更加灵活,因为它也实现了List接口的所有操作,并且可以插入null元素,这在ArrayDeque中是不允许的.

从效率来看,ArrayDeque要比LinkedList在两端增删元素上更为高效,因为没有在节点创建删除上的开销.最适合使用LinkedList的情况是迭代队列时删除当前迭代的元素.此外LinkedList可能是在遍历元素时最差的数据结构,并且也LinkedList占用更多的内存,因为LinkedList是通过链表连接其整个队列,它的元素在内存中是随机分布的,需要通过每个节点包含的前后节点的内存地址去访问前后元素.

总体ArrayDeque要比LinkedList更优越,在大队列的测试上有3倍与LinkedList的性能,最好的是给ArrayDeque一个较大的初始化大小,以避免底层数组扩容时数据拷贝的开销.

LinkedBlockingDeque是Deque的并发实现,在队列为空的时候,它的takeFirst,takeLast会阻塞等待队列处于可用状态

发表评论取消回复

表情：

评论列表（有 0 条评论，251人围观）

还没有评论，来说两句吧...

相关阅读

相关理解Java集合框架（Collections Framework）中的双端队列（Deque）。

在Java的集合框架中，双端队列（Deque，Double-Ended Queue）是一种可以同时从两端添加元素和删除元素的数据结构。它是List接口的一个实现。以下是一些

我不是女神ヾ/ 2024年12月03日 15:27/ 0 赞/ 14 阅读

相关 Java 集合框架系列十五：JDK 1.8 Hashtable 详解

Hashtable 继承关系 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM

港控/mmm°/ 2022年12月04日 07:56/ 0 赞/ 243 阅读

相关 java deque_java 集合框架(十五)Deque

一.概述 Deque是Queue的子接口,我们知道Queue是一种队列形式,而Deque则是双向队列,它支持从两个端点方向检索和插入元素,因此Deque既可以支持LIFO形式

迈不过友情╰/ 2022年11月01日 15:50/ 0 赞/ 252 阅读

相关双向队列集合 Deque

Queue除了前面介绍的实现外，还有一种双向的Queue实现Deque。这种队列允许在队列头和尾部进行入队出队操作，因此在功能上比Queue显然要更复杂。下图描述的是Deque

蔚落/ 2022年07月16日 23:12/ 0 赞/ 555 阅读

相关 Java集合框架（十五）：TreeSet 源码分析

文章目录 1、TreeSet 简述 2、TreeSet源码分析 3、TreeSet排序方式 3.1、一是自然排

- 日理万妓/ 2022年05月28日 12:37/ 0 赞/ 368 阅读

相关 Java学习笔记(十五)--集合

强烈推荐一个大神的人工智能的教程：[http://www.captainbed.net/zhanghan][http_www.captainbed.net_zhanghan]

浅浅的花香味﹌/ 2022年05月27日 13:05/ 0 赞/ 260 阅读

相关 Java从入门到放弃（十五）集合框架之LinkedHashMap源码

LinkedHashMap是一个有序的HashMap，各个节点以双向链表的形式链接着，结构如图所示：![LinkedHashMap结构图][LinkedHashMap] L

阳光穿透心脏的1/2处/ 2022年05月24日 04:42/ 0 赞/ 218 阅读

相关 Java集合框架（十）：Deque 源码分析

文章目录 1、Deque 简述 2、Deque 类图 3、Deque 方法概述 1、Deque 简述线性集合，支持两端插

心已赠人/ 2022年02月23日 10:18/ 0 赞/ 424 阅读

相关 Java集合List，Set，Map，Queue，Deque

集合是Java基础中非常重要的一部分，Java提供了非常丰富的集合API，了解各个集合的特点，怎么样在各种各样的场景中使用正确的集合，非常重要，也是一个Java程序员最基本的素

阳光穿透心脏的1/2处/ 2021年12月19日 16:43/ 0 赞/ 357 阅读

相关 Java面试知识点（五十）常见Java集合框架面试问题集锦

数据概览【List】 Arraylist： Object数组 Vector： Object数组 LinkedList：双向循环链表【Set】

爱被打了一巴掌/ 2021年09月30日 00:00/ 0 赞/ 669 阅读