Java中队列

news/2024/11/16 17:32:58/

队列是一种常见的数据结构，它按照先进先出（FIFO）的原则管理元素。在 Java 中，队列通常是通过链表或数组实现的，不同的实现类在内部数据结构和操作上可能有所不同。

1.原理

1.数据结构：队列的基本数据结构可以是链表或数组。链表实现的队列（如 LinkedList）允许高效地在两端进行添加和删除操作，而数组实现的队列（如 ArrayDeque）则可以更快地随机访问元素。
2.入队操作：将元素添加到队列的末尾称为入队操作。在链表实现中，入队操作涉及将新元素链接到链表的末尾；而在数组实现中，入队操作将新元素添加到数组的末尾，并更新队尾指针。
3.出队操作：从队列的头部移除元素称为出队操作。无论是链表还是数组实现，出队操作都涉及从队列的头部移除元素，并更新队头指针。
4.队列的大小：队列的大小可以根据添加和删除的元素数量来动态调整。在使用链表实现时，可以方便地添加或删除元素而不需要重新分配内存；而在使用数组实现时，可能需要进行数组扩容或缩小操作
在这里插入图片描述

2.实现

在这里插入图片描述

1.LinkedList

1.特点

1.双向链表结构： 每个元素都包含对其前一个元素和后一个元素的引用，这样可以轻松地在链表中插入和删除元素。
2.支持索引访问： 虽然链表的随机访问效率较低，但LinkedList仍然支持根据索引访问元素，可以使用get(int index)方法获取指定位置的元素。
3.支持头部和尾部操作： LinkedList实现了Deque接口，因此支持在头部和尾部添加、移除元素的操作，如offerFirst(E e)、offerLast(E e)、pollFirst()、pollLast()等。
4.非线程安全： LinkedList不是线程安全的，如果多个线程同时访问一个LinkedList实例并且至少有一个线程修改了列表的结构，那么必须通过外部同步来确保该LinkedList在并发环境中的安全性。
5.迭代器支持： LinkedList提供了ListIterator接口的实现，可以通过迭代器遍历链表中的元素。

2.常用方法

可以查看文档比较多
百度网盘 获取JDKAPI文档
链接：https://pan.baidu.com/s/1Z5mL0vVbXX1mMS8UqRaa6Q
提取码：2ktk
在这里插入图片描述

3.代码实现
LinkedList<String> linkedList = new LinkedList<>();// 添加元素到链表尾部
linkedList.add("A");
linkedList.add("B");
linkedList.add("C");// 在链表头部添加元素
linkedList.addFirst("X");// 在链表尾部添加元素
linkedList.addLast("Y");// 移除链表头部元素
linkedList.removeFirst();// 移除链表尾部元素
linkedList.removeLast();// 获取链表的第一个元素
String first = linkedList.getFirst();// 获取链表的最后一个元素
String last = linkedList.getLast();// 遍历链表元素
for (String element : linkedList) {System.out.println(element);
}

2.PriorityQueue

1.特点

1.基于堆实现： PriorityQueue通常基于堆数据结构实现，通常是一个最小堆（最小优先级队列），也可以通过提供自定义的比较器来创建最大堆（最大优先级队列）。
2.元素排序： 元素可以按照它们的自然顺序（如果它们实现了Comparable接口）或者根据提供的Comparator进行排序。
3.动态增长： PriorityQueue的大小可以动态增长，可以根据需要添加任意数量的元素。
4.不允许null元素： PriorityQueue不允许插入null元素，否则会抛出NullPointerException。
5.不是线程安全的： PriorityQueue不是线程安全的，如果多个线程同时访问一个PriorityQueue实例并且至少有一个线程修改了队列的结构，那么必须通过外部同步来确保该PriorityQueue在并发环境中的安全性。

2.常用方法

在这里插入图片描述

3.代码实现
// 创建一个最小堆（最小优先级队列）
PriorityQueue<Integer> minHeap = new PriorityQueue<>();// 添加元素到优先级队列
minHeap.offer(5);
minHeap.offer(3);
minHeap.offer(8);
minHeap.offer(1);// 获取并移除队列中的最小元素
int minElement = minHeap.poll();
System.out.println("最小元素：" + minElement);// 获取但不移除队列中的最小元素
int peekMinElement = minHeap.peek();
System.out.println("最小元素（但不移除）：" + peekMinElement);// 创建一个最大堆（最大优先级队列），使用自定义比较器
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);// 添加元素到优先级队列
maxHeap.offer(5);
maxHeap.offer(3);
maxHeap.offer(8);
maxHeap.offer(1);// 获取并移除队列中的最大元素
int maxElement = maxHeap.poll();
System.out.println("最大元素：" + maxElement);

3.SynchronousQueue（多线程下安全）

1.特点

1.零容量：SynchronousQueue 是一个零容量的队列，它不保存任何元素。插入操作（offer）只有在有线程等待获取元素时才会成功，否则会一直阻塞。
2.直接传递：生产者线程通过 put 方法插入元素时会阻塞，直到有消费者线程调用 take 方法获取这个元素。这种机制可以实现直接传递数据，而不需要中间的缓冲区。
3.公平性：SynchronousQueue 可以选择是否公平地进行元素获取。在公平模式下，如果多个消费者线程同时等待获取元素，队列会按照线程等待的先后顺序来分配元素。
4.应用场景：适合用于生产者和消费者之间的直接传递数据的场景，例如线程池任务分配、消息传递等。

2.代码实现
BlockingQueue<Object> synchronousQueue = new SynchronousQueue<>();//同步队列
//添加元素
new Thread(()->{try {System.out.println(Thread.currentThread().getName() + "put 1");synchronousQueue.put(1);System.out.println(Thread.currentThread().getName() + "put 2");synchronousQueue.put(2);System.out.println(Thread.currentThread().getName() + "put 3");synchronousQueue.put(3);} catch (InterruptedException e) {throw new RuntimeException(e);}
},"线程A").start();//移除元素
new Thread(()->{try {TimeUnit.SECONDS.sleep(3);System.out.println(Thread.currentThread().getName() + "take" + synchronousQueue.take());TimeUnit.SECONDS.sleep(3);System.out.println(Thread.currentThread().getName() + "take" + synchronousQueue.take());TimeUnit.SECONDS.sleep(3);System.out.println(Thread.currentThread().getName() + "take" + synchronousQueue.take());} catch (InterruptedException e) {throw new RuntimeException(e);}
},"线程B").start();

3.BlockingQueue(阻塞队列)

多线程环境下，BlockingQueue通常用于实现生产者-消费者模式，其中生产者线程将数据放入队列，而消费者线程从队列中取出数据进行处理。
当队列为空时，消费者线程试图从队列中取出元素时会被阻塞，直到队列中有可用元素为止；而当队列已满时，生产者线程试图向队列中放入元素时也会被阻塞，直到队列有空闲位置为止。

1.常用实现

1.ArrayBlockingQueue： 基于数组实现的有界阻塞队列，必须指定队列的容量，适合固定大小的线程池。
2.LinkedBlockingQueue： 基于链表实现的可选有界或无界阻塞队列，默认情况下是无界的，但也可以指定容量创建有界队列。
3.PriorityBlockingQueue： 是一个支持优先级排序的无界阻塞队列，元素按照它们的自然顺序或者根据提供的Comparator进行排序。
4.DelayQueue： 是一个支持延迟元素的无界阻塞队列，其中的元素只有在其指定的延迟时间到达后才能被获取。
5.SynchronousQueue： 是一个不存储元素的阻塞队列，每个插入操作必须等待另一个线程进行相应的删除操作，适合传递性场景。

2.常用方法

1.put(E e)： 将指定的元素插入到队列中，如果队列已满，则阻塞直到队列有空闲位置。
2.take()： 获取并移除队列的头部元素，如果队列为空，则阻塞直到队列中有可用元素。
3.offer(E e, long timeout, TimeUnit unit)： 将指定的元素插入到队列中，如果队列已满，则阻塞直到指定的超时时间。
4.poll(long timeout, TimeUnit unit)： 获取并移除队列的头部元素，如果队列为空，则阻塞直到指定的超时时间。
5.remainingCapacity()： 返回队列中剩余的可用空间。

3.四组API

1.抛出异常
BlockingQueue blockingQueue = new ArrayBlockingQueue<>(3);
//添加元素
System.out.println(blockingQueue.add("AAAA"));
System.out.println(blockingQueue.add("BBBB"));
System.out.println(blockingQueue.add("CCCC"));//获取队列首位元素
System.out.println(blockingQueue.element());//打印元素
blockingQueue.stream().forEach(System.out::print);System.out.println();
//抛出异常：java.lang.IllegalStateException: Queue full
// blockingQueue.add("DDDD");//移除元素
System.out.println(blockingQueue.remove());
System.out.println(blockingQueue.element());
System.out.println(blockingQueue.remove());
System.out.println(blockingQueue.remove());blockingQueue.stream().forEach(System.out::print);
//抛出异常：java.util.NoSuchElementException
System.out.println(blockingQueue.element());//抛出异常：java.util.NoSuchElementException
// System.out.println(blockingQueue.remove());
2.不抛出异常
BlockingQueue blockingQueue = new ArrayBlockingQueue<>(3);
//添加元素
System.out.println(blockingQueue.offer("AAAA"));
System.out.println(blockingQueue.offer("BBBB"));
System.out.println(blockingQueue.offer("CCCC"));//检测队首元素
System.out.println(blockingQueue.peek());//打印元素
blockingQueue.stream().forEach(System.out::print);System.out.println();//不抛出异常 返回 false
// System.out.println(blockingQueue.offer("DDDD"));System.out.println(blockingQueue.poll());
//检测队首元素
System.out.println(blockingQueue.peek());
System.out.println(blockingQueue.poll());
System.out.println(blockingQueue.poll());//打印元素
blockingQueue.stream().forEach(System.out::print);System.out.println();//检测队首元素 null 无异常
System.out.println(blockingQueue.peek());
//null 不抛出异常
// System.out.println(blockingQueue.poll());
3.阻塞等待
BlockingQueue blockingQueue = new ArrayBlockingQueue<>(3);
//添加元素
blockingQueue.put("AAAA");
blockingQueue.put("BBBB");
blockingQueue.put("CCCC");//打印元素
blockingQueue.stream().forEach(System.out::print);System.out.println();//阻塞线程执行，直到元素能够添加进去
// blockingQueue.put("DDDD");System.out.println(blockingQueue.take());
System.out.println(blockingQueue.take());
System.out.println(blockingQueue.take());
//阻塞线程执行，直到能够消费到元素
System.out.println(blockingQueue.take());
4.超时等待
BlockingQueue blockingQueue = new ArrayBlockingQueue<>(3);
//添加元素
System.out.println(blockingQueue.offer("AAAA"));
System.out.println(blockingQueue.offer("BBBB"));
System.out.println(blockingQueue.offer("CCCC"));//检测队首元素
System.out.println(blockingQueue.peek());//打印元素
blockingQueue.stream().forEach(System.out::print);System.out.println();//不抛出异常 等待超过两秒 返回 false
System.out.println(blockingQueue.offer("DDDD",2,TimeUnit.SECONDS));System.out.println(blockingQueue.poll());
//检测队首元素
System.out.println(blockingQueue.peek());
System.out.println(blockingQueue.poll());
System.out.println(blockingQueue.poll());//打印元素
blockingQueue.stream().forEach(System.out::print);System.out.println();//检测队首元素 null 无异常
System.out.println(blockingQueue.peek());
//null 不抛出异常 超过两秒System.out.println(blockingQueue.poll(2,TimeUnit.SECONDS));
5.图示四组API

在这里插入图片描述
不足之处，望海涵！！！


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

相关文章

MVSNet复现及解析

MVSNet复现及解析

目录 0.库安装1.参考链接2.调试过程 0.库安装 我在因为复现point-nerf才来研究MVSNet的&#xff0c;因此大部分库在复现point-nerf安装时候就已经安装了&#xff0c;剩下的基本上就只执行了下面两步&#xff1a; pip install tensorboardX-2.4.1-py2.py3-none-any.whl pip inst…
阅读更多...
数据库的创建

数据库的创建

数据库分类 通过查看对象资源管理器来区分数据库类型 数据库物理文件的组成 : 数据库文件 日志文件 创建一个主数据文件和一个日志文件
阅读更多...
【菜狗学前端】原生Ajax笔记（包含原生ajax的get/post传参方式、返回数据等）

【菜狗学前端】原生Ajax笔记（包含原生ajax的get/post传参方式、返回数据等）

这回图片少&#xff0c;给手动替换了~祝看得愉快&#xff0c;学的顺畅&#xff01;哈哈 一 原生ajax经典四步 (一) 原生ajax经典四步 第一步&#xff1a;创建网络请求的AJAX对象&#xff08;使用XMLHttpRequest&#xff09; JavaScript let xhr new XMLHttpRequest() 第二…
阅读更多...
Spring框架第一篇（Spring概述与IOC思想）

Spring框架第一篇（Spring概述与IOC思想）

文章目录 一、Spring概述二、Spring家族三、Spring Framework四、IOC思想五、IOC容器在Spring中的实现 一、Spring概述 Spring 是最受欢迎的企业级 Java 应用程序开发框架&#xff0c;数以百万的来自世界各地的开发人员使用 Spring 框架来创建性能好、易于测试、可重用的代码。…
阅读更多...
格林兰岛和南极洲的流域边界文件下载

格林兰岛和南极洲的流域边界文件下载

&#xff08;1&#xff09;南极流域系统边界和掩蔽区 下图显示了由戈达德冰面高程小组使用ICESat数据开发的南极分水岭。我们对西南极冰盖&#xff08;系统18-23和1&#xff09;、东南极冰盖&#xff08;系统2-17&#xff09;和南极半岛&#xff08;系统24-27&#xff09;的定…
阅读更多...
力扣哈哈哈哈

力扣哈哈哈哈

public class MyStack {int top;Queue<Integer> q1;Queue<Integer> q2;public MyStack() {q1new LinkedList<Integer>();q2new LinkedList<Integer>();}public void push(int x) {q2.offer(x);//offer是入队方法while (!q1.isEmpty()){q2.offer(q1.pol…
阅读更多...
Mybatis-plus自定义分页工具

Mybatis-plus自定义分页工具

Mybatis-plus自定义分页工具 这里主要是介绍通过MyBatis-Plus使用自定义分页工具进行条件分页查询示例等&#xff0c;方便以后查阅&#xff01;&#xff01;&#xff01; 分页工具类-PageUtils PageUtils package com.wl.cloud.core.utils;import com.baomidou.mybatisplus.cor…
阅读更多...
ceph large omap objects

ceph large omap objects

问题 出现下面告警信息 ceph -scluster:id: xxxxxxxxxxxxxxxxxxxxxxxhealth: HEALTH_WARN7 large omap objects获取问题 pool # ceph health detail HEALTH_WARN 7 large omap objects; 4 clients failing to respond to cache pressure [WRN] LARGE_OMAP_OBJECTS: 7 larg…
阅读更多...
最新文章

Copyright @ 2022~2023