Java中常見隊(duì)列舉例詳解(非線程安全)
一.隊(duì)列定義
在 Java 中,隊(duì)列(Queue) 是一種遵循 先進(jìn)先出(FIFO) 原則的數(shù)據(jù)結(jié)構(gòu),可以通過
java.util.Queue
接口及其實(shí)現(xiàn)類來使用。
二.常見接口
添加元素:
boolean add(E e)
: 添加元素,若隊(duì)列滿則拋出異常。boolean offer(E e)
: 添加元素,隊(duì)列滿時(shí)返回false
。
移除元素:
E remove()
: 移除并返回隊(duì)首元素,隊(duì)列空時(shí)拋出異常。E poll()
: 移除并返回隊(duì)首元素,隊(duì)列空時(shí)返回null
。
查看隊(duì)首元素:
E element()
: 返回隊(duì)首元素但不移除,隊(duì)列空時(shí)拋出異常。E peek()
: 返回隊(duì)首元素但不移除,隊(duì)列空時(shí)返回null
。
三.常見實(shí)現(xiàn)類
3.1 ArrayDeque
3.1.1 實(shí)現(xiàn)原理
* 基于數(shù)組進(jìn)行實(shí)現(xiàn)
* 不允許添加null元素
* 在兩端插入和刪除元素的性能較好,時(shí)間復(fù)雜度為O(1)
* 沒有容量限制,會根據(jù)需要自動擴(kuò)容。
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 實(shí)現(xiàn)原理
* 基于鏈表實(shí)現(xiàn)
* 允許添加null元素
* 在插入和刪除元素時(shí)性能較好,時(shí)間復(fù)雜度為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 實(shí)現(xiàn)原理
* 基于二叉堆(通常是最小堆)實(shí)現(xiàn)
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é)點(diǎn) private int leftChild(int i){ return 2*i+1; } //右子節(jié)點(diǎn) private int rightChild(int i){ return 2*i+2; } //父節(jié)點(diǎn) private int parent(int i){ return (i-1)/2; } //插入節(jié)點(diǎn) public void insert(int x){ heap.add(x); int index = heap.size()-1; //上浮節(jié)點(diǎn) while(index > 0 && heap.get(index) < heap.get(parent(index))){ swap(index, parent(index)); index = parent(index); } } //交換節(jié)點(diǎn) private void swap(int i, int j) { int temp = heap.get(i); heap.set(i, heap.get(j)); heap.set(j, temp); } //刪除最小節(jié)點(diǎn) 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é)點(diǎn)的最小樹 public void minHeapify(int i){ //左子節(jié)點(diǎn) int left = leftChild(i); //右子節(jié)點(diǎn) int right = rightChild(i); //最小節(jié)點(diǎn) int smallest = i; //計(jì)算左節(jié)點(diǎn) if(left < heap.size() && heap.get(left) < heap.get(smallest)){ smallest = left; } //計(jì)算右節(jié)點(diǎn) if(right < heap.size() && heap.get(right) < heap.get(smallest)){ smallest = right; } if (smallest != i){ swap(i, smallest); minHeapify(smallest); } } }
3.4 優(yōu)缺點(diǎn)
實(shí)現(xiàn)類 | 優(yōu)點(diǎn) | 缺點(diǎn) | 使用場景 |
---|---|---|---|
LinkedList | 1.支持雙端操作 2.動態(tài)擴(kuò)容,無容量限制 | 1.非線程安全 2.鏈表結(jié)構(gòu)導(dǎo)致內(nèi)存占用較高 | 1.需要雙端隊(duì)列操作(如?;蜿?duì)列) 2.單線程環(huán)境下需要快速插入/刪除 |
ArrayDeque | 1.基于數(shù)組實(shí)現(xiàn),內(nèi)存連續(xù),訪問效率高 2.默認(rèn)初始容量較小,動態(tài)擴(kuò)容效率優(yōu)于 | 1.非線程安全 2.容量固定時(shí)擴(kuò)容需要復(fù)制數(shù)組 | 1.高頻次隊(duì)列操作(如廣度優(yōu)先搜索) 2.替代 |
PriorityQueue | 1.元素按優(yōu)先級排序 2.基于堆結(jié)構(gòu),插入/刪除時(shí)間復(fù)雜度為 | 1.非線程安全 2.遍歷順序不保證按優(yōu)先級排序 | 1.任務(wù)調(diào)度(按優(yōu)先級處理) 2.合并多個(gè)有序數(shù)據(jù)流。 |
總結(jié)
到此這篇關(guān)于Java中常見隊(duì)列的文章就介紹到這了,更多相關(guān)JAVA常見隊(duì)列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
SpringCloud之Zuul網(wǎng)關(guān)原理及其配置講解
這篇文章主要介紹了SpringCloud之Zuul網(wǎng)關(guān)原理及其配置講解,具有很好的參考價(jià)值,希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2022-03-03springcloud微服務(wù)基于redis集群的單點(diǎn)登錄實(shí)現(xiàn)解析
這篇文章主要介紹了springcloud微服務(wù)基于redis集群的單點(diǎn)登錄實(shí)現(xiàn)解析,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-09-09java?Stream流常見操作方法(反射,類加載器,類加載,反射)
這篇文章主要介紹了java?Stream流常見操作方法(反射,類加載器,類加載,反射),文章圍繞主題展開詳細(xì)的內(nèi)容介紹,展開詳細(xì)的內(nèi)容介紹,具有一定參考價(jià)值,感興趣的小伙伴可以參考一下2022-06-06Java中的SimpleDateFormat的線程安全問題詳解
這篇文章主要介紹了Java中的SimpleDateFormat的線程安全問題詳解,sonar 是一個(gè)代碼質(zhì)量管理工具,SonarQube是一個(gè)用于代碼質(zhì)量管理的開放平臺,為項(xiàng)目提供可視化報(bào)告, 連續(xù)追蹤項(xiàng)目質(zhì)量演化過程,需要的朋友可以參考下2024-01-01Spring啟動后獲取所有擁有特定注解的Bean實(shí)例代碼
這篇文章主要介紹了Spring啟動后獲取所有擁有特定注解的Bean實(shí)例代碼,分享了相關(guān)代碼示例,小編覺得還是挺不錯(cuò)的,具有一定借鑒價(jià)值,需要的朋友可以參考下2018-02-02