本文主要是介绍Java中常见队列举例详解(非线程安全)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
《Java中常见队列举例详解(非线程安全)》队列用于模拟队列这种数据结构,队列通常是指先进先出的容器,：本文主要介绍Java中常见队列(非线程安全)的相关资料,文中通过代码介绍的非常详细,需要的朋...
一.队列定义
在 Java 中，队列（Queue） 是一种遵循 先进先出（FIFO） 原则的数据结构，可以通过
java.util.Queue接口及其实现类来使用。
二.常见接口
添加元素：
boolean add(E e): 添加元素，若队列满则抛出异常。boolean offer(E e): 添加元素，队列满时返回false。
移除元素：
E remove(): 移除并返回队首元素，队列空时抛出异常。E poll(): 移除并返回队首元素，队列空时返回null。
查看队首元素：
E element(): 返回队首元素但不移除，队列空时抛出异常。E peek(): 返回队首元素但不移除，队列空时返回null。
三.常见实现类
3.1 ArrayDeque
3.1.1 实现原理
* 基于数组进行实现
* 不允许添加null元素
* 在两端插入和删除元素的性能较好，时间复杂度为O(1)
* 没有容量限制，会根据需要自动扩容。
3.1.2 方法图解
3.1.3 demo代码
public class ArrayDequeDemo {
public static void main(String[] args) throws Exception{
ArrayDeque<Integer> deque = new ArrayDeque<>();
for(int i = 7 ; i >=0 ; i--){
deque.addFirst(i);
}
for (int i = 8 ; i < 15 ; i++){
deque.addLast(i);
}
show(deque);
deque.addLast(15);
show(deque);
}
public static void show(ArrayDeque<Integer> deque) throws Exception{
Field elements = ArrayDeque.class.getDeclaredField("elements");
elements.setAccessible(true);
System.out.println(jsONObject.toJSONString(elements.get(deque)));
System.out.println(((Object[])( elements.get(deque))).length);
Field head = ArrayDeque.class.getDeclaredField("head");
head.setAccessible(true);
System.out.println(JSONObject.toJSONString(head.get(deque)));
Field tail = ArrayDeque.class.getDeclaredField("tail");
tail.setAccessible(true);
System.out.println(JSONObject.toJSONString(tail.get(deque)));
}
}3.2 LinkedList
3.1.1 实现原理
* 基于链表实现
* 允许添加null元素
* 在插入和删除元素时性能较好，时间复杂度为O(1)
3.1.2 demo代码
public class LinkedListDemo {
public static void main(String[] args) {
LinkedList<Integer> queue = new LinkedList<>();
for(int i = 0 ; i < 20 ; i++){
queue.add((int)(Math.random()*1000));
queue.addFirst(i);
queue.addLast(i);China编程
}
while (!queue.isEmpty()){
System.out.println(queue.poll());
}
System.out.println(queue.poll());
}
}
3.3 PriorityQueue
3.1.1 实现原理
* 基于二叉堆（通常是最小China编程堆）实现
3.1.2 demo代码
public class PriorityQueueDemo {
public static void main(String[] args) {
PriorityQueue<Integer> queue = new PriorityQueue<>(Integer::compareTo);
for(int i = 0 ; i < 20 ; i++){
queue.add((int)(Math.rand编程China编程om()*1000));
}
while (!queue.isEmpty()){
System.out.println(queue.poll());
}
System.out.println(queue.poll());
}
}3.1.3 最小堆demo代码
class MinHeap{
private final List<Integer> heap;
public MinHeap(){
heap = new ArrayList<>();
}
//左子节点
private int leftChild(int i){
return 2*i+1;
}
//右子节点
private int rightchild(int i){
return 2*i+2;
}
//父节点
private int parent(int i){
return (i-1)/2;
}
//插入节点
public void insert(int x){
heap.add(x);
int index = heap.size()-1;
//上浮节点
while(index > 0 && heap.get(index) < heap.get(parent(index))){
swap(index, parent(index));
index = parent(index);
}
}
//交换节点
private void swap(int i, int j) {
int temp python= heap.get(i);
heap.set(i, heap.get(j));
heap.set(j, temp);
}
//删除最小节点
public int deleteMin(){
if(heap.isEmpty()){
throw new RuntimeException("堆为空");
}
if (heap.size() == 1){
return heap.remove(0);
}
int min = heap.get(0);
heap.set(0,heap.remove(heap.size()-1));
minHeapify(0);
return min;
}
//更新指定节点的最小树
public void minHeapify(int i){
//左子节点
int left = leftChild(i);
//右子节点
int right = rightChild(i);
//最小节点
int smallest = i;
//计算左节点
if(left < heap.size() && heap.get(left) < heap.get(smallest)){
smallest = left;
}
//计算右节点
if(right < heap.size() && heap.get(right) < heap.get(smallest)){
smallest = right;
}
if (smallest != i){
swapjs(i, smallest);
minHeapify(smallest);
}
}
}3.4 优缺点
| 实现类 | 优点 | 缺点 | 使用场景 |
|---|---|---|---|
| LinkedList | 1.支持双端操作 2.动态扩容，无容量限制 | 1.非线程安全 2.链表结构导致内存占用较高 | 1.需要双端队列操作（如栈或队列） 2.单线程环境下需要快速插入/删除 |
| ArrayDeque | 1.基于数组实现，内存连续，访问效率高 2.默认初始容量较小，动态扩容效率优于 | 1.非线程安全 2.容量固定时扩容需要复制数组 | 1.高频次队列操作（如广度优先搜索） 2.替代 |
| PriorityQueue | 1.元素按优先级排序 2.基于堆结构，插入/删除时间复杂度为 | 1.非线程安全 2.遍历顺序不保证按优先级排序 | 1.任务调度（按优先级处理） 2.合并多个有序数据流。 |
总结
到此这篇关于Java中常见队列的文章就介绍到这了,更多相关JAVA常见队列内容请搜索China编程(www.chinasem.cn)以前的文章或继续浏览下面的相关文章希望大家以后多多支持China编程(www.chinasem.cn)！
这篇关于Java中常见队列举例详解(非线程安全)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
