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