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); } 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<>(); } //左子節(jié)點 private int leftChild(int i){ return 2*i+1; } //右子節(jié)點 private int rightChild(int i){ return 2*i+2; } //父節(jié)點 private int parent(int i){ return (i-1)/2; } //插入節(jié)點 public void insert(int x){ heap.add(x); int index = heap.size()-1; //上浮節(jié)點 while(index > 0 && heap.get(index) < heap.get(parent(index))){ swap(index, parent(index)); index = parent(index); } } //交換節(jié)點 private void swap(int i, int j) { int temp = heap.get(i); heap.set(i, heap.get(j)); heap.set(j, temp); } //刪除最小節(jié)點 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; } //更新指定節(jié)點的最小樹 public void minHeapify(int i){ //左子節(jié)點 int left = leftChild(i); //右子節(jié)點 int right = rightChild(i); //最小節(jié)點 int smallest = i; //計算左節(jié)點 if(left < heap.size() && heap.get(left) < heap.get(smallest)){ smallest = left; } //計算右節(jié)點 if(right < heap.size() && heap.get(right) < heap.get(smallest)){ smallest = right; } if (smallest != i){ swap(i, smallest); minHeapify(smallest); } } }
3.4 優(yōu)缺點
實現類 | 優(yōu)點 | 缺點 | 使用場景 |
---|---|---|---|
LinkedList | 1.支持雙端操作 2.動態(tài)擴容,無容量限制 | 1.非線程安全 2.鏈表結構導致內存占用較高 | 1.需要雙端隊列操作(如?;蜿犃校?/p> 2.單線程環(huán)境下需要快速插入/刪除 |
ArrayDeque | 1.基于數組實現,內存連續(xù),訪問效率高 2.默認初始容量較小,動態(tài)擴容效率優(yōu)于 | 1.非線程安全 2.容量固定時擴容需要復制數組 | 1.高頻次隊列操作(如廣度優(yōu)先搜索) 2.替代 |
PriorityQueue | 1.元素按優(yōu)先級排序 2.基于堆結構,插入/刪除時間復雜度為 | 1.非線程安全 2.遍歷順序不保證按優(yōu)先級排序 | 1.任務調度(按優(yōu)先級處理) 2.合并多個有序數據流。 |
總結
到此這篇關于Java中常見隊列的文章就介紹到這了,更多相關JAVA常見隊列內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!
相關文章
springcloud微服務基于redis集群的單點登錄實現解析
這篇文章主要介紹了springcloud微服務基于redis集群的單點登錄實現解析,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2019-09-09java?Stream流常見操作方法(反射,類加載器,類加載,反射)
這篇文章主要介紹了java?Stream流常見操作方法(反射,類加載器,類加載,反射),文章圍繞主題展開詳細的內容介紹,展開詳細的內容介紹,具有一定參考價值,感興趣的小伙伴可以參考一下2022-06-06Java中的SimpleDateFormat的線程安全問題詳解
這篇文章主要介紹了Java中的SimpleDateFormat的線程安全問題詳解,sonar 是一個代碼質量管理工具,SonarQube是一個用于代碼質量管理的開放平臺,為項目提供可視化報告, 連續(xù)追蹤項目質量演化過程,需要的朋友可以參考下2024-01-01