java Queue 详解

news/2024/11/23 20:44:10/

Java Queue 详解

Queue 是 Java 集合框架中用于实现 队列 数据结构的接口,位于 java.util 包中。队列是一种 先进先出(FIFO) 的数据结构,元素按照插入的顺序依次出队。


1. Queue 的基本特性

  1. FIFO(First-In-First-Out)

    • 队列中的第一个元素是最先被处理的。
    • 特殊实现(如 Deque)可以支持双向队列操作。
  2. 队列操作

    • 插入元素:add() / offer()
    • 访问元素(不移除):element() / peek()
    • 移除元素:remove() / poll()
  3. 接口定义
    Queue 是一个接口,继承自 java.util.Collection

  4. 实现类

    • LinkedList(常用)
    • PriorityQueue
    • ArrayDeque
    • ConcurrentLinkedQueue(线程安全)

2. Queue 的方法

Queue 接口提供了以下主要方法:

方法描述
add(E e)将指定元素插入队列,如果队列已满,则抛出异常。
offer(E e)将指定元素插入队列,如果队列已满,则返回 false
remove()移除并返回队列头部的元素,如果队列为空,则抛出异常。
poll()移除并返回队列头部的元素,如果队列为空,则返回 null
element()返回队列头部的元素(不移除),如果队列为空,则抛出异常。
peek()返回队列头部的元素(不移除),如果队列为空,则返回 null

方法对比

方法类型抛出异常返回特殊值
插入add()offer()
移除remove()poll()
访问(不移除)element()peek()

3. Queue 的实现类

3.1 LinkedList

  • LinkedListQueue 的常用实现之一,底层基于链表实现。
  • 它既可以用作队列(FIFO),也可以用作双向队列Deque)。
示例:
java">import java.util.LinkedList;
import java.util.Queue;public class LinkedListQueue {public static void main(String[] args) {Queue<String> queue = new LinkedList<>();// 添加元素queue.add("A");queue.add("B");queue.add("C");// 访问头部元素System.out.println("Head: " + queue.peek()); // 输出:A// 移除元素System.out.println("Removed: " + queue.poll()); // 输出:A// 遍历队列for (String item : queue) {System.out.println(item); // 输出:B, C}}
}

3.2 PriorityQueue

  • 基于 堆(Heap) 实现的队列,元素按照自然顺序或自定义顺序排序。
  • 特点
    • 不保证 FIFO 顺序,优先级高的元素先出队。
    • 适合实现优先级任务调度。
示例:
java">import java.util.PriorityQueue;public class PriorityQueueExample {public static void main(String[] args) {PriorityQueue<Integer> pq = new PriorityQueue<>();// 添加元素pq.add(5);pq.add(2);pq.add(8);pq.add(1);// 按优先级移除元素while (!pq.isEmpty()) {System.out.println(pq.poll()); // 输出:1, 2, 5, 8}}
}

注意PriorityQueue 不支持 null 元素。


3.3 ArrayDeque

  • 基于 动态数组 实现的双端队列Deque)。
  • 特点
    • LinkedList 更高效(无额外的链表节点开销)。
    • 可以用作栈(LIFO)或队列(FIFO)。
示例:
java">import java.util.ArrayDeque;
import java.util.Queue;public class ArrayDequeExample {public static void main(String[] args) {Queue<String> queue = new ArrayDeque<>();// 添加元素queue.offer("X");queue.offer("Y");queue.offer("Z");// 访问头部元素System.out.println("Head: " + queue.peek()); // 输出:X// 移除元素System.out.println("Removed: " + queue.poll()); // 输出:X}
}

3.4 ConcurrentLinkedQueue

  • 是一个线程安全的非阻塞队列,基于 CAS(Compare-And-Swap) 实现。
  • 适用场景
    • 适用于高并发场景下的无界队列
示例:
java">import java.util.concurrent.ConcurrentLinkedQueue;public class ConcurrentQueueExample {public static void main(String[] args) {ConcurrentLinkedQueue<String> queue = new ConcurrentLinkedQueue<>();// 添加元素queue.offer("P");queue.offer("Q");queue.offer("R");// 访问头部元素System.out.println("Head: " + queue.peek()); // 输出:P// 移除元素System.out.println("Removed: " + queue.poll()); // 输出:P}
}

4. 特殊队列

4.1 阻塞队列(BlockingQueue)

  • 提供阻塞操作的队列接口,位于 java.util.concurrent 包中。
  • 主要实现类
    • ArrayBlockingQueue:基于数组的有界阻塞队列
    • LinkedBlockingQueue:基于链表的阻塞队列
    • PriorityBlockingQueue:支持优先级排序的阻塞队列
    • SynchronousQueue:一个没有存储能力的队列,直接在生产者和消费者之间传递数据。
示例:
java">import java.util.concurrent.ArrayBlockingQueue;public class BlockingQueueExample {public static void main(String[] args) throws InterruptedException {ArrayBlockingQueue<String> queue = new ArrayBlockingQueue<>(3);// 添加元素queue.put("1");queue.put("2");queue.put("3");// 移除元素System.out.println(queue.take()); // 输出:1}
}

特点

  • 队列满时,插入操作会阻塞。
  • 队列空时,删除操作会阻塞。

4.2 双端队列(Deque)

  • Queue 的子接口,支持从两端插入和删除元素。
  • 常见实现:
    • ArrayDeque
    • LinkedList
示例:
java">import java.util.Deque;
import java.util.LinkedList;public class DequeExample {public static void main(String[] args) {Deque<String> deque = new LinkedList<>();// 添加元素deque.addFirst("A");deque.addLast("B");// 访问头尾元素System.out.println("First: " + deque.getFirst()); // 输出:ASystem.out.println("Last: " + deque.getLast());   // 输出:B// 移除元素deque.removeFirst();System.out.println("After removing first: " + deque);}
}

5. Queue 的常见用例

5.1 任务调度

  • 使用 PriorityQueueBlockingQueue 实现任务调度。

5.2 消息队列

  • 使用 ConcurrentLinkedQueueBlockingQueue 实现线程间通信。

5.3 树/图的广度优先搜索(BFS)

  • 使用 Queue 存储待访问的节点。
示例:
java">import java.util.LinkedList;
import java.util.Queue;public class BFSExample {public static void main(String[] args) {Queue<Integer> queue = new LinkedList<>();// 初始化队列queue.offer(1);while (!queue.isEmpty()) {int node = queue.poll();System.out.println("Visited node: " + node);// 模拟添加邻居节点if (node < 3) {queue.offer(node + 1);}}}
}

输出

Visited node: 1
Visited node: 2
Visited node: 3

6. 总结

常用实现类对比

实现类特点适用场景
LinkedList基于链表,支持双端队列操作;性能适中。一般队列操作或双向队列
PriorityQueue元素按优先级排序,不保证 FIFO 顺序。优先级任务调度。
ArrayDeque高效实现队列和栈;比 LinkedList 更节省内存。双端队列或栈的实现。
ConcurrentLinkedQueue线程安全的无界队列,适用于高并发场景。多线程环境下的队列操作。
BlockingQueue提供阻塞操作,用于线程间通信。生产者-消费者模式。

选择 Queue 实现时,应根据具体需求(如是否需要优先级、线程安全等)选择合适的实现类。


http://www.ppmy.cn/news/1549365.html

相关文章

鸿蒙学习高效开发与测试-应用程序框架和HarmonyOS SDK(3)

文章目录 1、应用程序框架1、规范化后台进程管理2、原生支持分布式3、支持多设备的统一窗口管理4、 组件共享及面向对象5、逻辑与界面解耦6、灵活扩展机制2、HarmonyOS SDK1、 开放能力 Kit2、开放能力的检索和使用3、 方舟工具链4、前端编译器架构1、应用程序框架 应 用 程 序…

基于 RBF 神经网络辨识的单神经元 PID 模型参考自适应控制

这是一个基于 RBF 神经网络辨识 和 单神经元 PID 模型参考自适应控制 的系统框图&#xff0c;包含以下主要部分&#xff1a; RBF 神经网络模块&#xff1a;用于对系统进行辨识&#xff0c;输入误差 e(t)e(t)e(t) 和误差变化量 Δe(t)\Delta e(t)Δe(t)&#xff0c;输出与系统特…

【实用技能】使用 TX Text Control 创建带有嵌入式附件的 PDF 文档

TX Text Control .NET Server for ASP.NET&#xff08;下载试用最新版&#xff09;是一款Web应用程序的文档处理控件&#xff0c;包括用于 ASP.NET、ASP.NET Core 和 Angular 的文档编辑和查看的客户端包。目前TX Text Control .NET Server for ASP.NET 支持 .NET 5、.NET 6 和…

低代码开发平台搭建思考与实战

什么是低代码开发平台&#xff1f; 低代码开发平台是一种平台软件&#xff0c;人们能通过它提供的图形化配置功能&#xff0c;快速配置出满足各种特定业务需求的功能软件。 具有以下特点&#xff1a; 提供可视化界面进行程序开发0代码或少量代码快速生成应用 什么是低代码产…

刷题-1122

1. 蛇形矩阵是由1开始的自然数依次排列成的一个矩阵上三角形。 例如&#xff0c;当输入5时&#xff0c;应该输出的三角形为&#xff1a; 1 3 6 10 15 2 5 9 14 4 8 13 7 12 11 import sys def generate_snake_matrix(n):matrix [[0]*n for _ in range(n)]curent_num 1…

KVM虚拟机拷贝与迁移

在使用虚拟的过程中,经常需要快速复制虚拟机以构建集群环境,不同的虚拟机管理软件有不同的管理方法,KVM(Kernel-based Virtual Machine)是一种比较流行的开源虚拟机,使用KVM复制虚拟机的过程可以分为几个步骤。这里假设你已经有了一个运行中的虚拟机,并且想要创建它的多…

【大数据技术基础 | 实验十二】Hive实验:Hive分区

文章目录 一、实验目的二、实验要求三、实验原理四、实验环境五、实验步骤&#xff08;一&#xff09;启动Hadoop集群&#xff08;二&#xff09;用命令进入Hive客户端&#xff08;三&#xff09;通过HQL语句进行实验 六、实验结果七、实验心得 一、实验目的 掌握Hive分区的用…

QT 实现仿制 网络调试器(未实现连接唯一性) QT5.12.3环境 C++实现

网络调试助手&#xff1a; 提前准备&#xff1a;在编写代码前&#xff0c;要在.pro工程文件中&#xff0c;添加network模块。 服务端&#xff1a; 代码&#xff1a; widget.h #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QtWidgets> #inclu…