一、基本原理

• 隊列是一種特殊的線性表
• 隊列是一個有序表(可以用數組或鏈表實現)
• 遵循“先來先服務”的原則，它只允許在表的前端（隊頭）進行刪除操作，在表的后端（隊尾）進行插入操作

(一) 核心操作

• 入隊（Enqueue）：在隊尾添加元素。
• 出隊（Dequeue）：從隊頭移除元素。
• 查看隊頭（Front）：獲取隊頭元素但不移除。
• 判空（IsEmpty）：檢查隊列是否為空。

隊列的邏輯結構類似于現實中的排隊場景，例如超市收銀或銀行叫號系統，先到達的顧客優先服務。

(二) 代碼示例

import java.util.LinkedList;
import java.util.Queue;public class Main {public static void main(String[] args) {// 創建一個隊列Queue<Integer> queue = new LinkedList<>();// 入隊queue.offer(10);queue.offer(20);System.out.println("隊列大小: " + queue.size());// 輸出 2// 出隊int front = queue.poll();System.out.println("出隊元素: " + front);  // 輸出 10// 查看隊列的頭元素但不移除它int peek = queue.peek();System.out.println("隊列頭元素: " + peek);  // 輸出 20// 檢查隊列是否為空boolean isEmpty = queue.isEmpty();System.out.println("隊列是否為空: " + isEmpty);  // 輸出 false}
}public interface Queue<E> extends Collection<E> {//插入元素，成功返回true，失敗拋出異常boolean add(E e);//插入元素，成功返回true，失敗返回false或拋出異常 boolean offer(E e);//取出并移除頭部元素，空隊列拋出異常 E remove();//取出并移除頭部元素，空隊列返回null E poll();//取出但不移除頭部元素，空隊列拋出異常 E element();//取出但不移除頭部元素，空隊列返回null E peek();//刪除并返回隊頭元素，當隊列為空，則會阻塞等待E take();
}

二、基本類型

1. 雙端隊列（Deque）

• • 支持在隊頭和隊尾同時進行插入和刪除操作，靈活性更高。

1. 優先隊列（Priority Queue）

• • 元素按優先級出隊，而非順序，適用于任務調度等需要優先級處理的場景。

1. 阻塞隊列

• • 在隊列為空時，出隊操作阻塞；在隊列滿時，入隊操作阻塞，適用于多線程同步場景。

三、實現方式

隊列的實現主要有兩種方式，各自適用于不同場景：

1. 數組實現（順序隊列）

• • 特點：使用固定大小的數組存儲元素，通過兩個指針（front和rear）分別標記隊頭和隊尾。
  • 問題：當rear指針到達數組末尾時，若隊頭有空閑位置，無法直接利用，導致“假溢出”。
  • 優化方案：引入循環隊列，通過模運算實現指針的循環移動，從而高效利用數組空間。

1. 鏈表實現（鏈式隊列）

• • 特點：使用動態鏈表存儲元素，無需預先分配固定大小，通過兩個指針（head和tail）分別指向隊頭和隊尾。
  • 優勢：空間利用率高，適合元素數量不確定或動態變化的場景。

四、復雜度分析

• 時間復雜度：

• • 入隊（Enqueue）：O(1)（數組和鏈表實現均高效）。
  • 出隊（Dequeue）：O(1)（鏈表實現直接操作頭節點；數組實現需移動指針，但循環隊列優化后仍為O(1)）。

• 空間復雜度：

• • 數組實現：固定大小，可能浪費空間或溢出。
  • 鏈表實現：動態分配，空間利用率高，但需額外指針存儲空間。

五、應用場景

隊列在計算機科學和實際工程中具有廣泛應用，以下是一些典型場景：

1. 任務調度與資源管理

• • 操作系統進程調度：CPU按照隊列順序執行進程，確保公平性。
  • 打印機任務隊列：用戶提交的打印任務按順序處理，避免混亂。

1. 消息傳遞與緩沖區管理

• • 網絡數據包處理：接收到的數據包按順序進入隊列，由處理器按順序處理，確保數據完整性。
  • 生產者-消費者模型：生產者將數據放入隊列，消費者從隊列中取出數據，實現解耦和異步處理。

1. 算法與系統設計

• • 廣度優先搜索（BFS）：使用隊列逐層遍歷圖的節點，確保按層次訪問。
  • Web服務器請求處理：客戶端請求按順序進入隊列，服務器按順序響應，避免過載。

1. 異步通信與事件處理

• • 即時通訊應用：如WhatsApp在用戶離線時，消息暫存于隊列，待用戶上線后按順序接收。
  • GUI事件處理：用戶操作事件按順序進入隊列，由事件循環按順序處理。

六、優缺點

• 優點：

• • 邏輯簡單，易于實現。
  • 保證元素順序處理，適用于需要公平性的場景。

• 缺點：

• • 數組實現需預先分配空間，可能浪費或不足。
  • 中間插入或刪除效率低（需移動大量元素），但隊列通常不涉及此類操作。

七、參看資料

Java 中常用隊列用法詳解 - 技術棧