隊列是一種非常基礎且常用的數據結構，它的核心特點是“先進先出”（FIFO，First In First Out）。想象一下，我們在超市排隊結賬，第一個人會最先結賬離開，第二個人隨後，這就是隊列的典型場景——先來的排在前面，先處理。
一、隊列的基本概念¶
- 隊列（Queue）：一種遵循“先進先出”原則的數據結構，只能在一端添加元素（隊尾），在另一端取出元素（隊頭）。
- 隊頭（Front）：隊列的第一個元素，是最早進入隊列的元素。
- 隊尾（Rear）：隊列的最後一個元素，是最晚進入隊列的元素。
- 基本操作：
- 入隊（Enqueue）：將新元素添加到隊尾。
- 出隊（Dequeue）：從隊頭取出並移除元素。
二、隊列如何實現？（以數組爲例）¶
爲了簡單理解隊列的實現，我們可以用一個固定大小的數組來模擬隊列。需要兩個關鍵變量：
- front：指向隊頭（第一個元素），初始值爲 0。
- rear：指向隊尾（最後一個元素），初始值爲 0。
- 數組 arr：用於存儲隊列元素，容量設爲 max_size（例如 5）。
核心規則：¶
- 隊空條件：
front == rear（此時隊列爲空，沒有元素）。 - 隊滿條件：
rear == max_size（此時隊列已滿，無法再入隊）。 - 入隊邏輯：將元素放入
arr[rear]，然後rear++。 - 出隊邏輯：取出
arr[front]，然後front++。
三、實例演示：模擬隊列的“入隊”與“出隊”¶
假設隊列容量爲 5，初始時 front=0，rear=0，數組爲空。
步驟 1：入隊 1、2、3¶
- 入隊 1：
arr[0] = 1，rear=1→ 隊列：[1] - 入隊 2：
arr[1] = 2，rear=2→ 隊列：[1, 2] - 入隊 3：
arr[2] = 3，rear=3→ 隊列：[1, 2, 3]
步驟 2：出隊 1，再入隊 4¶
- 出隊 1：取出
arr[front=0]，front=1→ 隊列：[2, 3] - 入隊 4：
arr[3] = 4，rear=4→ 隊列：[2, 3, 4]
步驟 3：入隊 5，再出隊 2¶
- 入隊 5：
arr[4] = 5，rear=5→ 隊列：[2, 3, 4, 5]（此時隊列已滿，無法再入隊） - 出隊 2：取出
arr[front=1]，front=2→ 隊列：[3, 4, 5]
此時隊列中剩餘元素爲 3, 4, 5，front=2，rear=5，隊列未滿且非空。
四、隊列的應用場景¶
隊列在編程和實際場景中非常常用，例如：
- 任務調度：操作系統中的“任務隊列”（如 CPU 處理任務時，新任務排隊等待）。
- 廣度優先搜索（BFS）：在樹或圖的遍歷中，按層遍歷節點（類似“逐層處理”）。
- 打印機隊列：打印文檔時，先提交的文檔先打印。
- 網絡請求：網頁加載時，同時請求的資源會按順序在隊列中處理。
總結¶
隊列的核心是“先進先出”，通過數組或鏈表等結構可以輕鬆實現。理解隊列的關鍵是記住：入隊從隊尾加，出隊從隊頭取，始終保持“先來先處理”的順序。這種簡單的規則讓隊列在數據處理、任務調度等場景中發揮着重要作用。