Java中常見隊列舉例詳解(非線程安全)

更新時間：2025年06月09日 11:53:02 作者：m2442600094_

隊列用于模擬隊列這種數(shù)據結構,隊列通常是指先進先出的容器,這篇文章主要介紹了Java中常見隊列(非線程安全)的相關資料,文中通過代碼介紹的非常詳細,需要的朋友可以參考下

一.隊列定義

在 Java 中，隊列（Queue） 是一種遵循 先進先出（FIFO） 原則的數(shù)據結構，可以通過 java.util.Queue 接口及其實現(xiàn)類來使用。

二.常見接口

添加元素：
- boolean add(E e): 添加元素，若隊列滿則拋出異常。
- boolean offer(E e): 添加元素，隊列滿時返回 false。
移除元素：
- E remove(): 移除并返回隊首元素，隊列空時拋出異常。
- E poll(): 移除并返回隊首元素，隊列空時返回 null。
查看隊首元素：
- E element(): 返回隊首元素但不移除，隊列空時拋出異常。
- E peek(): 返回隊首元素但不移除，隊列空時返回 null。

三.常見實現(xiàn)類

3.1 ArrayDeque

3.1.1 實現(xiàn)原理

* 基于數(shù)組進行實現(xiàn)
* 不允許添加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 實現(xiàn)原理

* 基于鏈表實現(xiàn)
* 允許添加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 實現(xiàn)原理

* 基于二叉堆（通常是最小堆）實現(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é)點
    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)缺點

實現(xiàn)類優(yōu)點缺點使用場景

LinkedList

實現(xiàn)類	優(yōu)點	缺點	使用場景
LinkedList	1.支持雙端操作 2.動態(tài)擴容，無容量限制	1.非線程安全 2.鏈表結構導致內存占用較高	1.需要雙端隊列操作（如?；蜿犃校?/p> 2.單線程環(huán)境下需要快速插入/刪除
ArrayDeque	1.基于數(shù)組實現(xiàn)，內存連續(xù)，訪問效率高 2.默認初始容量較小，動態(tài)擴容效率優(yōu)于 `LinkedList`	1.非線程安全 2.容量固定時擴容需要復制數(shù)組	1.高頻次隊列操作（如廣度優(yōu)先搜索） 2.替代 `Stack` 類實現(xiàn)棧（性能更優(yōu)）
PriorityQueue	1.元素按優(yōu)先級排序 2.基于堆結構，插入/刪除時間復雜度為 `O(log n)`	1.非線程安全 2.遍歷順序不保證按優(yōu)先級排序	1.任務調度（按優(yōu)先級處理） 2.合并多個有序數(shù)據流。

1.支持雙端操作

2.動態(tài)擴容，無容量限制

1.非線程安全

2.鏈表結構導致內存占用較高

1.需要雙端隊列操作（如?；蜿犃校?/p>

2.單線程環(huán)境下需要快速插入/刪除

ArrayDeque

1.基于數(shù)組實現(xiàn)，內存連續(xù)，訪問效率高

2.默認初始容量較小，動態(tài)擴容效率優(yōu)于 LinkedList

1.非線程安全

2.容量固定時擴容需要復制數(shù)組

1.高頻次隊列操作（如廣度優(yōu)先搜索）