Python 講解資料結構-Quene 隊列

康韡瀚

5 min readSep 12, 2023

什麼是隊列（Queue）？

隊列是一種數據結構，遵循先進先出（FIFO）的原則。這意味著在隊列中最早添加的元素將最先被移除。隊列的這種行為類似於人們在商店、銀行等地方排隊的方式。

隊列是一種先進先出（First-In-First-Out，簡稱 FIFO）的數據結構，就像人們在排隊等待一樣，先到的人先得到服務。

隊列的主要操作

隊列的基本操作包括：

入隊（Enqueue）: 將新元素添加到隊列的末尾。
出隊（Dequeue）: 移除隊列的第一個元素。
檢視隊首（Peek/Front）: 查看隊列的第一個元素但不移除它。
判斷隊列是否為空: 檢查隊列是否不包含任何元素。

隊列的應用

隊列在計算機科學和日常生活中都有廣泛的應用，例如：

任務排程: 作業系統可以使用隊列來管理等待執行的任務。
印表機列印: 隊列可用於管理等待列印的文檔順序。
廣度優先搜索: 在圖和樹的搜索中，隊列可以用來實現廣度優先搜索算法。

隊列的實現

隊列可以通過多種方式實現，如使用鏈表、數組、堆疊等。不同語言和庫可能提供了不同的隊列實現。

Python: 可以使用內建的 queue 模組。
Java: 可以使用 java.util.Queue 接口和其實現類，如 LinkedList。
C++: 可以使用 STL 中的 std::queue。

結論

隊列是一個重要的數據結構，遵循先進先出的原則。它有多種應用，並可以通過多種方式實現。了解隊列的基本概念和操作對於理解和使用許多計算機科學和日常應用非常有用。

使用 Python 實現隊列

我們可以使用 Python 的內建模組 queue 來實現隊列。以下是一個簡單的範例：

1. 引入模組

from queue import Queue

2. 創建隊列

q = Queue()

3. 入隊

q.put(5)
q.put(10)

4. 出隊

item = q.get()
print(item)  # 輸出 5

5. 檢查隊列是否為空

is_empty = q.empty()
print(is_empty)  # 輸出 False

以上就是使用 Python 實現隊列的基本教學。隊列在計算機科學中有很多應用，例如用於實現廣度優先搜索（Breadth-First Search）等。

Deque vs List vs Queue

deque: 提供了雙端操作，允許在開頭和末尾以常數時間插入和移除元素。不是線程安全的。
list: Python 的標準列表提供了隨機訪問和末尾操作的高效支持，但在開頭插入和移除元素的效率較低。不是線程安全的。
Queue: 在 queue 模組中提供，是線程安全的隊列實現。主要用於多線程編程，不支持隨機訪問和特定的雙端操作。

根據您的具體需求和使用場景（例如是否需要支持多線程），選擇合適的數據結構。在大多數情況下，如果需要高效的雙端操作，deque 通常是最佳選擇。如果只需要末尾操作並且不需要線程安全，則可以使用標準的 list。如果需要線程安全的隊列操作，則可以使用 Queue。

Leetcode 題目解法

933. Number of Recent Calls

You have a RecentCounter class which counts the number of recent requests within a certain time frame.

Implement the RecentCounter class:

RecentCounter() Initializes the counter with zero recent requests.
int ping(int t) Adds a new request at time t, where t represents some time in milliseconds, and returns the number of requests that has happened in the past 3000 milliseconds (including the new request). Specifically, return the number of requests that have happened in the inclusive range [t - 3000, t].

It is guaranteed that every call to ping uses a strictly larger value of t than the previous call.

from queue import Queue
from collections import deque

# ---------陣列解法---------
class RecentCounter:
    def __init__(self):
        self.queue = []
    def ping(self, t: int) -> int:
        self.queue.append(t)
        # 移除所有小於 t - 3000 的請求
        while self.queue[0] < t - 3000:
            self.queue.pop(0)
        # 返回隊列中剩餘元素的數量
        return len(self.queue)

# ---------Queue()解法---------
class RecentCounter:
    def __init__(self):
        self.queue = Queue()
    def ping(self, t: int) -> int:
        self.queue.put(t)
        # 移除所有小於 t - 3000 的請求
        while self.queue.queue[0] < t - 3000:
            self.queue.get()
        # 返回隊列中剩餘元素的數量
        return self.queue.qsize()
# ---------雙端隊列解法---------
class RecentCounter:
    def __init__(self):
        self.deque = deque()
    def ping(self, t: int) -> int:
        self.deque.append(t)
        # 移除所有小於 t - 3000 的請求
        while self.deque[0] < t - 3000:
            self.deque.pop(0)
        # 返回隊列中剩餘元素的數量
        return len(self.deque)