一文學(xué)會隊列入門：Python數(shù)據(jù)結(jié)構(gòu)與算法
作者：子午Python
隊列是計算機(jī)科學(xué)中的一個核心概念，有廣泛的應(yīng)用，如任務(wù)調(diào)度、數(shù)據(jù)同步等。了解其基本操作和特性，能夠幫助我們更好地解決實際問題。
隊列(Queue)是一種特殊的線性數(shù)據(jù)結(jié)構(gòu)，其操作遵循先進(jìn)先出(FIFO)的原則，即最先添加到隊列中的元素最先被移除。
隊列的基本概念
隊列的基本操作包括：入隊(Enqueue)將元素添加到隊列的尾部，和出隊(Dequeue)從隊列的頭部移除元素。 在Python中，我們可以使用列表來簡單地模擬隊列，但為了效率更高，我們經(jīng)常使用 collections 模塊中的 deque 類來實現(xiàn)隊列。
from collections import deque
# 創(chuàng)建一個隊列
queue = deque()
# 入隊操作
queue.append(10)
queue.append(20)
queue.append(30)
# 此時隊列的狀態(tài)為 [10, 20, 30]出隊操作
從隊列的頭部移除元素。
# 出隊操作
first_element = queue.popleft() # 移除并返回頭部元素，結(jié)果是 10
# 此時隊列的狀態(tài)為 [20, 30]隊列的輔助操作
(1) 查看隊首和隊尾元素
# 查看隊首元素
front_element = queue[0] # 結(jié)果是 20
# 查看隊尾元素
rear_element = queue[-1] # 結(jié)果是 30(2) 檢查隊列是否為空
is_empty = not bool(queue) # 如果隊列為空，結(jié)果為 True(3) 獲取隊列的大小
size = len(queue) # 結(jié)果是 2，因為隊列中有兩個元素優(yōu)先隊列
優(yōu)先隊列是一種特殊的隊列，其中每個元素都有一個與之相關(guān)的優(yōu)先級。Python的heapq模塊提供了實現(xiàn)優(yōu)先隊列的工具。
import heapq
# 創(chuàng)建一個空的優(yōu)先隊列
priority_queue = []
# 入隊操作
heapq.heappush(priority_queue, (1, "Task 1")) # 數(shù)字1表示優(yōu)先級
heapq.heappush(priority_queue, (3, "Task 3"))
heapq.heappush(priority_queue, (2, "Task 2"))
# 出隊操作（按優(yōu)先級）
task = heapq.heappop(priority_queue) # 結(jié)果是 (1, "Task 1")雙端隊列
deque 不僅可以作為一個隊列使用，還可以支持從兩端添加和刪除元素，因此被稱為雙端隊列。
dq = deque()
# 從頭部和尾部添加元素
dq.appendleft(10)
dq.append(20)
# 從頭部和尾部移除元素
dq.popleft() # 結(jié)果是 10
dq.pop() # 結(jié)果是 20實戰(zhàn)案例：任務(wù)調(diào)度
假設(shè)我們有一個打印機(jī)，需要處理一系列的打印任務(wù)。任務(wù)有不同的優(yōu)先級，并且需要在有限的時間內(nèi)完成。我們可以使用隊列來模擬這個過程。
from random import randint
class PrintTask:
def __init__(self, priority):
self.priority = priority
self.time_needed = randint(1, 5) # 隨機(jī)生成所需時間
def tick(self):
"""減少任務(wù)所需的時間"""
self.time_needed -= 1
def is_done(self):
"""檢查任務(wù)是否完成"""
return self.time_needed <= 0
# 創(chuàng)建任務(wù)隊列
tasks = deque()
# 生成10個隨機(jī)任務(wù)
for _ in range(10):
p = randint(1, 5)
tasks.append(PrintTask(p))
# 處理任務(wù)
while tasks:
current_task = tasks.popleft()
current_task.tick()
print(f"Processing task with priority {current_task.priority}... Time left: {current_task.time_needed}")
if not current_task.is_done():
tasks.append(current_task)
else:
print(f"Task with priority {current_task.priority} is done!")小結(jié)
隊列是計算機(jī)科學(xué)中的一個核心概念，有廣泛的應(yīng)用，如任務(wù)調(diào)度、數(shù)據(jù)同步等。了解其基本操作和特性，能夠幫助我們更好地解決實際問題。
責(zé)任編輯：趙寧寧
來源：
子午Python
