JAVA中常见队列详解-非线程安全
目录
一.队列定义
二.常见接口
三.常见实现类
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<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);}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<Integer> 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<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 = 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.默认初始容量较小，动态扩容效率优于 | 1.非线程安全 2.容量固定时扩容需要复制数组 | 1.高频次队列操作（如广度优先搜索） 2.替代 |
| PriorityQueue | 1.元素按优先级排序 2.基于堆结构，插入/删除时间复杂度为 | 1.非线程安全 2.遍历顺序不保证按优先级排序 | 1.任务调度（按优先级处理） 2.合并多个有序数据流。 |