---

前言

• 本篇文章，我們一起來學習隊列的知識。

---

一、隊列

1.1 隊列是什么?

• 隊列（queue）是一種遵循先入先出規則的線性數據結構。
• 

1.2 隊列的類比

• 顧名思義，隊列模擬了排隊現象，即新來的人不斷加入隊列尾部，而位于隊列頭部的人逐個離開。

二、隊列的常用操作

• 隊列的操作效率

方法名	描述	時間復雜度
push()	元素入隊，即將元素添加至隊尾	$O(1)$
pop()	隊首元素出隊	$O(1)$
peek()	訪問隊首元素	$O(1)$

• 實際上 python 中有寫好的 隊列的類， 我們可以直接使用隊列的包

代碼演示：

from collections import deque# 初始化隊列
# 在 Python 中，我們一般將雙向隊列類 deque 當作隊列使用
# 雖然 queue.Queue() 是純正的隊列類，但不太好用，因此不推薦
que: deque[int] = deque()# 元素入隊
que.append(1)
que.append(3)
que.append(2)
que.append(5)
que.append(4)# 訪問隊首元素
front: int = que[0]# 元素出隊
pop: int = que.popleft()# 獲取隊列的長度
size: int = len(que)# 判斷隊列是否為空
is_empty: bool = len(que) == 0

三、隊列的實現

• 為了實現隊列，我們需要一種數據結構，可以在一端添加元素，并在另一端刪除元素，鏈表和數組都符合要求

3.1 基于數組實現隊列

• 我們可以數組的第一個元素當成隊頭，每次入隊的時候，相當于是在添加數組，出隊的時候，我們返回數組的第一個元素，并將其從數組中刪除。
• 但是在數組中刪除首元素的時間復雜度為 $O(n)$，這會導致出隊操作效率較低。然而，我們可以采用以下巧妙方法來避免這個問題。
  • 我們可以使用一個變量 front 指向隊首元素的索引，并維護一個變量 size 用于記錄隊列長度。定義 rear = front + size ，這個公式計算出的 rear 指向隊尾元素之后的下一個位置。

3.1.1 基于環形數組實現的隊列

• 在不斷進行入隊和出隊的過程中，front 和 rear 都在向右移動，當它們到達數組尾部時就無法繼續移動了。為了解決此問題，我們可以將數組視為首尾相接的“環形數組”。
• 對于環形數組，我們需要讓 front 或 rear 在越過數組尾部時，直接回到數組頭部繼續遍歷。這種周期性規律可以通過“取余操作”來實現，代碼如下所示：

代碼演示：

class ArrayQueue:"""基于環形數組實現的隊列"""def __init__(self, size: int):"""構造方法"""self._nums: list[int] = [0] * size  # 用于存儲隊列元素的數組self._front: int = 0  # 隊首指針，指向隊首元素self._size: int = 0  # 隊列長度def capacity(self) -> int:"""獲取隊列的容量"""return len(self._nums)def size(self) -> int:"""獲取隊列的長度"""return self._sizedef is_empty(self) -> bool:"""判斷隊列是否為空"""return self._size == 0def push(self, num: int):"""入隊"""if self._size == self.capacity():raise IndexError("隊列已滿")# 計算隊尾指針，指向隊尾索引 + 1# 通過取余操作實現 rear 越過數組尾部后回到頭部rear: int = (self._front + self._size) % self.capacity()# 將 num 添加至隊尾self._nums[rear] = numself._size += 1def pop(self) -> int:"""出隊"""num: int = self.peek()# 隊首指針向后移動一位，若越過尾部，則返回到數組頭部self._front = (self._front + 1) % self.capacity()self._size -= 1return numdef peek(self) -> int:"""訪問隊首元素"""if self.is_empty():raise IndexError("隊列為空")return self._nums[self._front]def to_list(self) -> list[int]:"""返回列表用于打印"""res = [0] * self.size()j: int = self._frontfor i in range(self.size()):res[i] = self._nums[(j % self.capacity())]j += 1return res

3.1.2 基于動態數組實現的隊列

• 3.1.2 實現的隊列仍然具有局限性：其長度不可變。
• 然而，這個問題不難解決，我們可以將數組替換為動態數組，從而引入擴容機制。

代碼演示：

class DynamicArrayQueue:"""基于動態數組實現的隊列"""def __init__(self):"""構造方法"""self._nums: list[int] = []  # 動態數組用于存儲隊列元素self._front: int = 0  # 隊首指針def size(self) -> int:"""獲取隊列的長度"""return len(self._nums) - self._frontdef is_empty(self) -> bool:"""判斷隊列是否為空"""return self.size() == 0def push(self, num: int):"""入隊"""self._nums.append(num)  # 直接添加到列表尾部def pop(self) -> int:"""出隊"""if self.is_empty():raise IndexError("隊列為空")num: int = self.peek()self._front += 1  # 增加隊首指針# 清理不再使用的空間（可選）if self._front > len(self._nums) // 2:  # 如果已移除的元素超過一半self._resize()  # 縮減隊列的內部數組return numdef peek(self) -> int:"""訪問隊首元素"""if self.is_empty():raise IndexError("隊列為空")return self._nums[self._front]def _resize(self):"""縮減隊列的內部數組"""self._nums = self._nums[self._front:]  # 創建新列表，只包含有效元素self._front = 0  # 重置front指針def to_list(self) -> list[int]:"""返回列表用于打印"""return self._nums[self._front:]  # 返回從當前front開始的有效元素# 使用隊列
dq = DynamicArrayQueue()
dq.push(1)
dq.push(2)
print(dq.pop())  # 輸出: 1
dq.push(3)
print(dq.to_list())  # 輸出: [2, 3]

3.2 基于鏈表實現隊列

• 我們可以將鏈表的“頭節點”和“尾節點”分別視為“隊首”和“隊尾”，規定隊尾僅可添加節點，隊首僅可刪除節點。

代碼演示：

class LinkedListQueue:"""基于鏈表實現的隊列"""def __init__(self):"""構造方法"""self._front: ListNode | None = None  # 頭節點 frontself._rear: ListNode | None = None  # 尾節點 rearself._size: int = 0def size(self) -> int:"""獲取隊列的長度"""return self._sizedef is_empty(self) -> bool:"""判斷隊列是否為空"""return self._size == 0def push(self, num: int):"""入隊"""# 在尾節點后添加 numnode = ListNode(num)# 如果隊列為空，則令頭、尾節點都指向該節點if self._front is None:self._front = nodeself._rear = node# 如果隊列不為空，則將該節點添加到尾節點后else:self._rear.next = nodeself._rear = nodeself._size += 1def pop(self) -> int:"""出隊"""num = self.peek()# 刪除頭節點self._front = self._front.nextself._size -= 1return numdef peek(self) -> int:"""訪問隊首元素"""if self.is_empty():raise IndexError("隊列為空")return self._front.valdef to_list(self) -> list[int]:"""轉化為列表用于打印"""queue = []temp = self._frontwhile temp:queue.append(temp.val)temp = temp.nextreturn queue

四、隊列的典型應用

• 淘寶訂單。購物者下單后，訂單將加入隊列中，系統隨后會根據順序處理隊列中的訂單。在雙十一期間，短時間內會產生海量訂單，高并發成為工程師們需要重點攻克的問題。
• 各類待辦事項。任何需要實現“先來后到”功能的場景，例如打印機的任務隊列、餐廳的出餐隊列等，隊列在這些場景中可以有效地維護處理順序。

---

總結

• 文章介紹了隊列的實現方式，還有其常用函數，最后我們基于數組還有鏈表實現了隊列。