沉梦听雨的编程指南 沉梦听雨的编程指南
首页
  • 基础篇
  • 集合篇
  • 并发篇
  • JVM
  • 新特性
  • 计算机网络
  • 操作系统
  • 数据结构与算法
  • 基础篇
  • MySql
  • Redis
  • 达梦数据库
  • Spring
  • SpringBoot
  • Mybatis
  • Shiro
  • 设计须知
  • UML画图
  • 权限校验
  • 设计模式
  • API网关
  • RPC
  • 消息队列
  • SpringCloud
  • 分布式事务
  • 云存储
  • 搜索引擎
  • 多媒体框架
  • 虚拟机
  • 开发工具篇
  • 工具库篇
  • 开发技巧篇
  • 工具类系列
  • 随笔
  • 前端环境搭建
  • HTML与CSS
  • JS学习
  • Axios入门
  • Vue Router入门
  • Pinia入门
  • Vue3入门
  • Vue3进阶
  • 黑马Vue3
  • 脚手架搭建
  • 瑞吉外卖
  • 黑马点评
  • vue-blog
  • 沉梦接口开放平台
  • 用户中心
  • 聚合搜索平台
  • 仿12306项目
  • 壁纸小程序项目
  • RuoYi-Vue
  • 博客搭建
  • 网站收藏箱
  • 断墨寻径摘录
  • 费曼学习法
Github (opens new window)

沉梦听雨

时间是最好的浸渍剂,而沉淀是最好的提纯器🚀
首页
  • 基础篇
  • 集合篇
  • 并发篇
  • JVM
  • 新特性
  • 计算机网络
  • 操作系统
  • 数据结构与算法
  • 基础篇
  • MySql
  • Redis
  • 达梦数据库
  • Spring
  • SpringBoot
  • Mybatis
  • Shiro
  • 设计须知
  • UML画图
  • 权限校验
  • 设计模式
  • API网关
  • RPC
  • 消息队列
  • SpringCloud
  • 分布式事务
  • 云存储
  • 搜索引擎
  • 多媒体框架
  • 虚拟机
  • 开发工具篇
  • 工具库篇
  • 开发技巧篇
  • 工具类系列
  • 随笔
  • 前端环境搭建
  • HTML与CSS
  • JS学习
  • Axios入门
  • Vue Router入门
  • Pinia入门
  • Vue3入门
  • Vue3进阶
  • 黑马Vue3
  • 脚手架搭建
  • 瑞吉外卖
  • 黑马点评
  • vue-blog
  • 沉梦接口开放平台
  • 用户中心
  • 聚合搜索平台
  • 仿12306项目
  • 壁纸小程序项目
  • RuoYi-Vue
  • 博客搭建
  • 网站收藏箱
  • 断墨寻径摘录
  • 费曼学习法
Github (opens new window)
  • 基础篇

  • 集合篇

    • Java集合概述
    • List接口
    • Set接口
    • Queue接口
      • Queue 与 Deque 的区别
      • ArrayDeque 与 LinkedList 的区别
      • 说一说 PriorityQueue(优先级队列)
    • Map接口
  • 并发篇

  • JVM

  • 新特性

  • Java核心技术卷I

  • Java
  • 集合篇
沉梦听雨
2023-08-10
目录

Queue接口

# Queue 集合详解

# Queue 与 Deque 的区别

Queue 是单端队列,只能从一端插入元素,另一端删除元素,实现上一般遵循 先进先出(FIFO) 规则。

Queue 扩展了 Collection 的接口,根据 因为容量问题而导致操作失败后处理方式的不同 可以分为两类方法: 一种在操作失败后会抛出异常,另一种则会返回特殊值。

Queue 接口 抛出异常 返回特殊值
插入队尾 add(E e) offer(E e)
删除队首 remove() poll()
查询队首元素 element() peek()

Deque 是双端队列,在队列的两端均可以插入或删除元素。

Deque 扩展了 Queue 的接口, 增加了在队首和队尾进行插入和删除的方法,同样根据失败后处理方式的不同分为两类:

Deque 接口 抛出异常 返回特殊值
插入队首 addFirst(E e) offerFirst(E e)
插入队尾 addLast(E e) offerLast(E e)
删除队首 removeFirst() pollFirst()
删除队尾 removeLast() pollLast()
查询队首元素 getFirst() peekFirst()
查询队尾元素 getLast() peekLast()

事实上,Deque 还提供有 push() 和 pop() 等其他方法,可用于模拟栈。

# ArrayDeque 与 LinkedList 的区别

ArrayDeque 和 LinkedList 都实现了 Deque 接口,两者都具有队列的功能,但两者有什么区别呢?

  • ArrayDeque 是基于可变长的数组和双指针来实现,而 LinkedList 则通过链表来实现。
  • ArrayDeque 不支持存储 NULL 数据,但 LinkedList 支持。
  • ArrayDeque 是在 JDK1.6 才被引入的,而LinkedList 早在 JDK1.2 时就已经存在。
  • ArrayDeque 插入时可能存在扩容过程, 不过均摊后的插入操作依然为 O(1)。虽然 LinkedList 不需要扩容,但是每次插入数据时均需要申请新的堆空间,均摊性能相比更慢。

从性能的角度上,选用 ArrayDeque 来实现队列要比 LinkedList 更好。此外,ArrayDeque 也可以用于实现栈。

# 说一说 PriorityQueue(优先级队列)

PriorityQueue 是在 JDK1.5 中被引入的, 其与 Queue 的区别在于元素出队顺序是与优先级相关的,即总是优先级最高的元素先出队。

这里列举其相关的一些要点:

  • PriorityQueue 利用了二叉堆的数据结构来实现的,底层使用可变长的数组来存储数据
  • PriorityQueue 通过堆元素的上浮和下沉,实现了在 O(logn) 的时间复杂度内插入元素和删除堆顶元素。
  • PriorityQueue 是非线程安全的,且不支持存储 NULL 和 non-comparable 的对象。
  • PriorityQueue 默认是小顶堆,但可以接收一个 Comparator 作为构造参数,从而来自定义元素优先级的先后。

二叉堆(binary heap)是一种基于完全二叉树的数据结构,它满足如下两个性质:

  1. 父节点的键值总是大于或等于(小于或等于)任何一个子节点的键值。
  2. 每个节点的左子树和右子树都是一个二叉堆(称为堆的性质)。

根据性质 1,我们可以将二叉堆划分为两种类型:最大堆和最小堆。

  • 在最大堆中,父节点的键值总是大于或等于任何一个子节点的键值。
  • 在最小堆中,父节点的键值总是小于或等于任何一个子节点的键值。

PriorityQueue 在面试中可能更多的会出现在手撕算法的时候,典型例题包括堆排序、求第K大的数、带权图的遍历等,所以需要会熟练使用才行。

上次更新: 2025/3/26 17:30:17
Set接口
Map接口

← Set接口 Map接口→

Theme by Vdoing | Copyright © 2023-2025 沉梦听雨 | MIT License
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式