Java中常見(jiàn)隊(duì)列舉例詳解(非線程安全)
一.隊(duì)列定義
在 Java 中，隊(duì)列（Queue） 是一種遵循 先進(jìn)先出（FIFO） 原則的數(shù)據(jù)結(jié)構(gòu)，可以通過(guò)
java.util.Queue接口及其實(shí)現(xiàn)類來(lái)使用。
二.常見(jià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。
三.常見(jiàn)實(shí)現(xiàn)類
3.1 ArrayDeque
3.1.1 實(shí)現(xiàn)原理
* 基于數(shù)組進(jìn)行實(shí)現(xiàn)
* 不允許添加null元素
* 在兩端插入和刪除元素的性能較好，時(shí)間復(fù)雜度為O(1)
* 沒(méi)有容量限制，會(huì)根據(jù)需要自動(dòng)擴(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) | 使用場(chǎng)景 |
|---|---|---|---|
| LinkedList | 1.支持雙端操作 2.動(dòng)態(tài)擴(kuò)容，無(wú)容量限制 | 1.非線程安全 2.鏈表結(jié)構(gòu)導(dǎo)致內(nèi)存占用較高 | 1.需要雙端隊(duì)列操作（如棧或隊(duì)列） 2.單線程環(huán)境下需要快速插入/刪除 |
| ArrayDeque | 1.基于數(shù)組實(shí)現(xiàn)，內(nèi)存連續(xù)，訪問(wèn)效率高 2.默認(rèn)初始容量較小，動(dòng)態(tài)擴(kuò)容效率優(yōu)于 | 1.非線程安全 2.容量固定時(shí)擴(kuò)容需要復(fù)制數(shù)組 | 1.高頻次隊(duì)列操作（如廣度優(yōu)先搜索） 2.替代 |
| PriorityQueue | 1.元素按優(yōu)先級(jí)排序 2.基于堆結(jié)構(gòu)，插入/刪除時(shí)間復(fù)雜度為 | 1.非線程安全 2.遍歷順序不保證按優(yōu)先級(jí)排序 | 1.任務(wù)調(diào)度（按優(yōu)先級(jí)處理） 2.合并多個(gè)有序數(shù)據(jù)流。 |
總結(jié)
到此這篇關(guān)于Java中常見(jiàn)隊(duì)列的文章就介紹到這了,更多相關(guān)JAVA常見(jiàn)隊(duì)列內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Java捕獲ThreadPoolExecutor內(nèi)部線程異常的四種方法
這篇文章主要為大家詳細(xì)介紹了Java捕獲ThreadPoolExecutor內(nèi)部線程異常的四種方法,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以參考一下2025-03-03
Java?集合框架底層數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)深度解析(示例詳解)
Java 集合框架（Java Collections Framework, JCF）是支撐高效數(shù)據(jù)處理的核心組件,其底層數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)直接影響性能與適用場(chǎng)景,這篇文章主要介紹Java集合框架底層數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)深度解析,需要的朋友可以參考下2025-06-06
springboot使用filter獲取自定義請(qǐng)求頭的實(shí)現(xiàn)代碼
這篇文章主要介紹了springboot使用filter獲取自定義請(qǐng)求頭的實(shí)例代碼，代碼簡(jiǎn)單易懂，非常不錯(cuò)，具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2019-05-05
這篇文章主要介紹了對(duì)RestTemplate的深度解析，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-10-10
Java BufferedReader相關(guān)源碼實(shí)例分析
這篇文章主要介紹了Java BufferedReader相關(guān)源碼實(shí)例分析,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-10-10
子類繼承父類時(shí)構(gòu)造函數(shù)相關(guān)問(wèn)題解析
這篇文章主要介紹了子類繼承父類時(shí)構(gòu)造函數(shù)相關(guān)問(wèn)題解析,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-11-11
Spring?Boot開發(fā)時(shí)Java對(duì)象和Json對(duì)象之間的轉(zhuǎn)換
在Spring?Boot開發(fā)中,我們經(jīng)常需要處理Java對(duì)象和Json對(duì)象之間的轉(zhuǎn)換,本文將介紹如何在Spring?Boot項(xiàng)目中實(shí)現(xiàn)Java對(duì)象和Json對(duì)象之間的轉(zhuǎn)換,感興趣的朋友跟隨小編一起看看吧2023-09-09
這篇文章主要介紹了如何解決grails2.3.2中不能運(yùn)行fork模式的異常，大家參考使用吧2013-11-11
在平常的開發(fā)工作中,我們經(jīng)常需要部署項(xiàng)目,開發(fā)測(cè)試完成后,最關(guān)鍵的一步就是部署,這篇文章主要介紹了docker編寫java的jar的相關(guān)資料,文中通過(guò)代碼介紹的非常詳細(xì),需要的朋友可以參考下2025-09-09
這篇文章主要為大家介紹了java線程池參數(shù)自定義設(shè)置詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-11-11