目录一.队列定义二.常见接口三.常见实现类3.1 ArrayDeque 3.1.1 实现原理3.1.2 方法图解3.1.3 demo代码3.2 LinkedList 3.1.1 实现原理3.1.2 demo代码3.3 PriorityQueue 3.1.1 实现原理3.1.2 demo代码3.1.3 最小堆demo代码3.4 优缺点总结一.队列定义在 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 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 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 queue = new LinkedList<>();for(int i = 0 ; i < 20 ; i++){queue.add((int)(Math.random()*1000));queue.addFirst(i);queue.addLast(i);}while (!queue.isEmpty()){System.out.println(queue.poll());}System.out.println(queue.poll());}}3.3 PriorityQueue 3.1.1 实现原理* 基于二叉堆（通常是最小堆）实现3.1.2 demo代码public class PriorityQueueDemo {public static void main(String[] args) {PriorityQueue queue = new PriorityQueue<>(Integer::compareTo);for(int i = 0 ; i < 20 ; i++){queue.add((int)(Math.random()*1000));}while (!queue.isEmpty()){System.out.println(queue.poll());}System.out.println(queue.poll());}
}3.1.3 最小堆demo代码class MinHeap{private final List 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 = 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){swap(i, smallest);minHeapify(smallest);}}}3.4 优缺点实现类优点缺点使用场景LinkedList
1.支持双端操作
2.动态扩容，无容量限制
1.非线程安全
2.链表结构导致内存占用较高
1.需要双端队列操作（如栈或队列）
2.单线程环境下需要快速插入/删除
ArrayDeque
1.基于数组实现，内存连续，访问效率高
2.默认初始容量较小，动态扩容效率优于
LinkedList
1.非线程安全
2.容量固定时扩容需要复制数组
1.高频次队列操作（如广度优先搜索）
2.替代
Stack类实现栈（性能更优）
PriorityQueue
1.元素按优先级排序
2.基于堆结构，插入/删除时间复杂度为
O(log n)
1.非线程安全
2.遍历顺序不保证按优先级排序
1.任务调度（按优先级处理）
2.合并多个有序数据流。
总结到此这篇关于Java中常见队列的文章就介绍到这了,更多相关JAVA常见队列内容请搜索脚本之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持脚本之家！
您可能感兴趣的文章:Java 队列实现原理及简单实现代码java中栈和队列的实现和API的用法(详解) Java消息队列的简单实现代码java队列实现方法(顺序队列,链式队列,循环队列) java实现消息队列的两种方式(小结)
