deque 的 20 個實際應用範例
1. FIFO 佇列
模擬簡單的先進先出佇列：
from collections import deque
queue = deque()
queue.append("A") # 加入佇列
queue.append("B")
queue.append("C")
print(queue.popleft()) # 移除並返回最早進入的元素，輸出: A
print(queue) # 剩下的佇列: deque(['B', 'C'])
2. LIFO 堆疊
模擬簡單的後進先出堆疊：
from collections import deque
stack = deque()
stack.append("A") # 加入堆疊
stack.append("B")
stack.append("C")
print(stack.pop()) # 移除並返回最後加入的元素，輸出: C
print(stack) # 剩下的堆疊: deque(['A', 'B'])
3. 廣度優先搜尋 (BFS)
用 deque 高效實現 BFS：
from collections import deque
graph = {1: [2, 3], 2: [4, 5], 3: [6], 4: [], 5: [], 6: []}
def BFS(start):
queue = deque([start])
visited = set()
while queue:
node = queue.popleft() # 取出當前節點
if node not in visited:
print(node, end=" ") # 處理節點
visited.add(node)
queue.extend(graph[node]) # 加入鄰居節點
BFS(1) # 輸出: 1 2 3 4 5 6
4. 滑動視窗問題
使用固定長度的 deque 計算滑動視窗的總和：
from collections import deque
def sliding_window_sum(arr, k):
window = deque()
window_sum = 0
for i, num in enumerate(arr):
window.append(num)
window_sum += num
if len(window) > k: # 視窗超過大小時移除左端
window_sum -= window.popleft()
if len(window) == k: # 滿足視窗大小，輸出總和
print(f"視窗 {list(window)} 的總和為 {window_sum}")
sliding_window_sum([1, 2, 3, 4, 5], 3)
# 輸出:
# 視窗 [1, 2, 3] 的總和為 6
# 視窗 [2, 3, 4] 的總和為 9
# 視窗 [3, 4, 5] 的總和為 12
5. 旋轉資料
使用 rotate 操作旋轉資料：
from collections import deque
dq = deque([1, 2, 3, 4, 5])
dq.rotate(2) # 向右旋轉 2 步
print(dq) # 輸出: deque([4, 5, 1, 2, 3])
dq.rotate(-3) # 向左旋轉 3 步
print(dq) # 輸出: deque([2, 3, 4, 5, 1])
6. 固定長度佇列
限制 deque 長度來儲存最近的 N 筆資料：
from collections import deque
dq = deque(maxlen=3) # 限制長度為 3
dq.extend([1, 2, 3])
print(dq) # 輸出: deque([1, 2, 3], maxlen=3)
dq.append(4) # 超出長度時，自動移除左端元素
print(dq) # 輸出: deque([2, 3, 4], maxlen=3)
7. 判斷回文
使用 deque 高效判斷字串是否為回文：
from collections import deque
def is_palindrome(string):
dq = deque(string)
while len(dq) > 1:
if dq.popleft() != dq.pop(): # 左右兩端不相等則非回文
return False
return True
print(is_palindrome("level")) # 輸出: True
print(is_palindrome("hello")) # 輸出: False
8. 最近使用（LRU）快取
模擬最近使用快取（LRU Cache）的邏輯：
from collections import deque
cache = deque(maxlen=3) # 限制快取長度為 3
def access_page(page):
if page in cache:
cache.remove(page) # 如果已存在，移至最右端
cache.append(page)
print("目前快取:", list(cache))
access_page(1)
access_page(2)
access_page(3)
access_page(2)
access_page(4)
# 輸出:
# 目前快取: [1]
# 目前快取: [1, 2]
# 目前快取: [1, 2, 3]
# 目前快取: [1, 3, 2]
# 目前快取: [3, 2, 4]
9. 時間序列處理
管理時間序列資料，確保只保留最近的資料點：
from collections import deque
import time
timestamps = deque()
def add_event():
now = time.time()
timestamps.append(now)
def cleanup(threshold):
while timestamps and timestamps[0] < time.time() - threshold:
timestamps.popleft()
# 模擬事件
add_event()
time.sleep(1)
add_event()
time.sleep(2)
cleanup(2) # 移除超過 2 秒的舊資料
print(timestamps) # 只保留最近的事件
10. 模擬回合制遊戲
使用 deque 模擬玩家輪流行動：
from collections import deque
players = deque(["Player1", "Player2", "Player3", "Player4"])
while len(players) > 1:
current = players.popleft() # 當前玩家
print(f"{current} 的回合")
players.append(current) # 加回隊尾（輪到下一位）
print(f"勝利者是: {players[0]}")
總結
deque 是一個功能強大且高效的資料結構，適合用於：
- 佇列（FIFO）
- 堆疊（LIFO）
- 限制長度的快取
- 時間序列與回文檢查等
deque 的另外 10 個應用範例，涵蓋更多實際場景，進一步展現其靈活性與高效能：
1. 模擬循環隊列
適合處理多輪循環的場景，例如音樂播放列表：
from collections import deque
playlist = deque(["Song1", "Song2", "Song3", "Song4"])
for _ in range(6): # 循環播放 6 次
current_song = playlist.popleft()
print(f"播放: {current_song}")
playlist.append(current_song) # 加回隊尾
2. 節點層次遍歷
用於樹的層次遍歷（Level Order Traversal）：
from collections import deque
def level_order_traversal(tree):
if not tree:
return
queue = deque([tree])
while queue:
node = queue.popleft()
print(node["value"], end=" ")
if node.get("left"):
queue.append(node["left"])
if node.get("right"):
queue.append(node["right"])
# 測試二叉樹
tree = {
"value": 1,
"left": {"value": 2, "left": {"value": 4}, "right": {"value": 5}},
"right": {"value": 3},
}
level_order_traversal(tree) # 輸出: 1 2 3 4 5
3. 用作稀疏矩陣的列管理
使用 deque 儲存非零元素，進行矩陣壓縮與訪問：
from collections import deque
# 建立稀疏矩陣的行
sparse_row = deque([(1, 3), (4, 7)]) # (索引, 值)
# 新增非零元素
sparse_row.append((5, 2))
print("行內容:", sparse_row)
# 遍歷非零元素
for idx, val in sparse_row:
print(f"索引: {idx}, 值: {val}")
4. 延遲工作處理
模擬一個延遲任務處理系統：
from collections import deque
import time
tasks = deque()
# 加入任務
tasks.append((time.time() + 2, "Task1")) # 延遲 2 秒執行
tasks.append((time.time() + 4, "Task2")) # 延遲 4 秒執行
# 處理任務
while tasks:
current_time = time.time()
task_time, task_name = tasks[0]
if current_time >= task_time:
print(f"執行: {task_name}")
tasks.popleft()
time.sleep(1)
5. 計算最近 N 次的平均值
維護一個固定長度的視窗來計算平均值：
from collections import deque
window = deque(maxlen=5) # 固定視窗大小
nums = [10, 20, 30, 40, 50, 60]
for num in nums:
window.append(num)
print(f"最近 {len(window)} 個數字: {list(window)}, 平均值: {sum(window) / len(window)}")
6. 文字分解與重組
將句子分解為單詞，並進行處理：
from collections import deque
sentence = "Python deque is very useful"
words = deque(sentence.split()) # 分解句子
print("原始順序:", words)
# 反向重組句子
words.reverse()
print("反向順序:", " ".join(words))
7. 模擬雙向遊戲角色移動
用來記錄角色左右移動的步伐：
from collections import deque
steps = deque()
steps.append("left")
steps.append("right")
steps.append("left")
steps.appendleft("start") # 起始位置
print("步驟順序:", list(steps))
steps.pop() # 移除最後一步
print("剩餘步驟:", list(steps))
8. 解碼括號表達式
用 deque 處理括號展開問題：
from collections import deque
def decode_expression(expression):
stack = deque()
for char in expression:
if char == ')':
temp = ""
while stack and stack[-1] != '(':
temp = stack.pop() + temp
stack.pop() # 移除 '('
stack.append(temp[::-1]) # 範例操作：反轉括號內內容
else:
stack.append(char)
return "".join(stack)
print(decode_expression("a(bc)d")) # 輸出: abcd
9. 用於序列優化
計算滑動最小值：
from collections import deque
def sliding_window_minimum(nums, k):
dq = deque()
result = []
for i, num in enumerate(nums):
while dq and dq[0] < i - k + 1: # 移除超出視窗範圍的索引
dq.popleft()
while dq and nums[dq[-1]] > num: # 移除無效的索引
dq.pop()
dq.append(i) # 新增當前索引
if i >= k - 1: # 開始輸出最小值
result.append(nums[dq[0]])
return result
print(sliding_window_minimum([10, 2, 4, 8, 6, 1], 3)) # 輸出: [2, 2, 4, 1]
10. 日誌系統記錄
用來儲存最近的 N 條日誌：
from collections import deque logs = deque(maxlen=5) # 只保留最近 5 條日誌 def log_event(event): logs.append(event) print("目前日誌:", list(logs)) log_event("啟動系統") log_event("加載模組") log_event("用戶登入") log_event("用戶登出") log_event("關閉系統") log_event("重新啟動") # 最舊日誌自動移除
沒有留言:
張貼留言