Python隊列的練習題有哪些

Python隊列的練習題有哪些

隊列（Queue）是計算機科學中一種常見的數據結構，遵循先進先出（FIFO, First In First Out）的原則。Python 提供了多種方式來實現隊列，例如使用 list、collections.deque 或 queue.Queue 等模塊。為了幫助大家更好地理解和掌握隊列的使用，本文將提供一系列練習題，涵蓋基礎操作、算法應用、實際場景模擬等內容。

目錄

1. 隊列的基礎操作
2. 隊列的算法應用
3. 隊列的實際場景模擬
4. 隊列的高級應用
5. 總結

1. 隊列的基礎操作

1.1 實現一個簡單的隊列

使用 Python 的 list 實現一個簡單的隊列，并完成以下操作： - 入隊（enqueue） - 出隊（dequeue） - 查看隊首元素（peek） - 判斷隊列是否為空（is_empty）

示例代碼：

class SimpleQueue:
    def __init__(self):
        self.queue = []

    def enqueue(self, item):
        self.queue.append(item)

    def dequeue(self):
        if not self.is_empty():
            return self.queue.pop(0)
        else:
            raise IndexError("Dequeue from an empty queue")

    def peek(self):
        if not self.is_empty():
            return self.queue[0]
        else:
            raise IndexError("Peek from an empty queue")

    def is_empty(self):
        return len(self.queue) == 0

# 測試
q = SimpleQueue()
q.enqueue(1)
q.enqueue(2)
print(q.peek())  # 輸出: 1
print(q.dequeue())  # 輸出: 1
print(q.is_empty())  # 輸出: False

1.2 使用 collections.deque 實現隊列

collections.deque 是 Python 中一個高效的雙端隊列實現，適合用于隊列操作。請使用 deque 實現一個隊列，并完成以下操作： - 入隊（enqueue） - 出隊（dequeue） - 查看隊首元素（peek） - 判斷隊列是否為空（is_empty）

示例代碼：

from collections import deque

class DequeQueue:
    def __init__(self):
        self.queue = deque()

    def enqueue(self, item):
        self.queue.append(item)

    def dequeue(self):
        if not self.is_empty():
            return self.queue.popleft()
        else:
            raise IndexError("Dequeue from an empty queue")

    def peek(self):
        if not self.is_empty():
            return self.queue[0]
        else:
            raise IndexError("Peek from an empty queue")

    def is_empty(self):
        return len(self.queue) == 0

# 測試
q = DequeQueue()
q.enqueue(1)
q.enqueue(2)
print(q.peek())  # 輸出: 1
print(q.dequeue())  # 輸出: 1
print(q.is_empty())  # 輸出: False

1.3 使用 queue.Queue 實現線程安全隊列

queue.Queue 是 Python 標準庫中提供的線程安全隊列實現。請使用 queue.Queue 實現一個隊列，并完成以下操作： - 入隊（put） - 出隊（get） - 查看隊列大?。?code>qsize） - 判斷隊列是否為空（empty）

示例代碼：

from queue import Queue

q = Queue()
q.put(1)
q.put(2)
print(q.qsize())  # 輸出: 2
print(q.get())  # 輸出: 1
print(q.empty())  # 輸出: False

2. 隊列的算法應用

2.1 使用隊列實現棧

請使用隊列實現一個棧（Stack），并完成以下操作： - 入棧（push） - 出棧（pop） - 查看棧頂元素（top） - 判斷棧是否為空（is_empty）

提示： 可以使用兩個隊列來實現棧的功能。

示例代碼：

from collections import deque

class StackUsingQueue:
    def __init__(self):
        self.queue1 = deque()
        self.queue2 = deque()

    def push(self, item):
        self.queue1.append(item)

    def pop(self):
        if not self.is_empty():
            while len(self.queue1) > 1:
                self.queue2.append(self.queue1.popleft())
            result = self.queue1.popleft()
            self.queue1, self.queue2 = self.queue2, self.queue1
            return result
        else:
            raise IndexError("Pop from an empty stack")

    def top(self):
        if not self.is_empty():
            return self.queue1[-1]
        else:
            raise IndexError("Top from an empty stack")

    def is_empty(self):
        return len(self.queue1) == 0

# 測試
stack = StackUsingQueue()
stack.push(1)
stack.push(2)
print(stack.top())  # 輸出: 2
print(stack.pop())  # 輸出: 2
print(stack.is_empty())  # 輸出: False

2.2 使用隊列實現廣度優先搜索（BFS）

廣度優先搜索（BFS）是圖算法中常用的一種遍歷方法，通常使用隊列來實現。請使用隊列實現 BFS，并完成以下操作： - 遍歷圖中的所有節點 - 返回從起點到目標節點的最短路徑

示例代碼：

from collections import deque

def bfs(graph, start, target):
    visited = set()
    queue = deque([(start, [start])])

    while queue:
        node, path = queue.popleft()
        if node == target:
            return path
        if node not in visited:
            visited.add(node)
            for neighbor in graph[node]:
                queue.append((neighbor, path + [neighbor]))

    return None

# 測試
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}
print(bfs(graph, 'A', 'F'))  # 輸出: ['A', 'C', 'F']

2.3 使用隊列解決約瑟夫問題

約瑟夫問題是一個經典的數學問題，描述如下：n 個人圍成一圈，從第 k 個人開始報數，數到 m 的人出列，直到所有人都出列。請使用隊列解決約瑟夫問題。

示例代碼：

from collections import deque

def josephus(n, k, m):
    queue = deque(range(1, n + 1))
    result = []
    queue.rotate(-(k - 1))  # 從第 k 個人開始

    while queue:
        queue.rotate(-(m - 1))  # 數到 m 的人出列
        result.append(queue.popleft())

    return result

# 測試
print(josephus(7, 3, 4))  # 輸出: [3, 7, 4, 2, 6, 5, 1]

3. 隊列的實際場景模擬

3.1 模擬打印機任務隊列

假設有一個打印機任務隊列，任務按照到達順序依次處理。請模擬以下場景： - 任務到達時入隊 - 打印機處理任務時出隊 - 打印當前任務隊列

示例代碼：

from collections import deque

class PrinterQueue:
    def __init__(self):
        self.queue = deque()

    def add_task(self, task):
        self.queue.append(task)
        print(f"Task '{task}' added to the queue.")

    def process_task(self):
        if self.queue:
            task = self.queue.popleft()
            print(f"Processing task: {task}")
        else:
            print("No tasks in the queue.")

    def show_queue(self):
        print("Current queue:", list(self.queue))

# 測試
printer = PrinterQueue()
printer.add_task("Document1")
printer.add_task("Document2")
printer.show_queue()  # 輸出: Current queue: ['Document1', 'Document2']
printer.process_task()  # 輸出: Processing task: Document1
printer.show_queue()  # 輸出: Current queue: ['Document2']

3.2 模擬銀行排隊系統

假設有一個銀行排隊系統，客戶按照到達順序依次辦理業務。請模擬以下場景： - 客戶到達時入隊 - 柜員處理客戶時出隊 - 顯示當前排隊客戶列表

示例代碼：

from collections import deque

class BankQueue:
    def __init__(self):
        self.queue = deque()

    def add_customer(self, customer):
        self.queue.append(customer)
        print(f"Customer '{customer}' joined the queue.")

    def serve_customer(self):
        if self.queue:
            customer = self.queue.popleft()
            print(f"Serving customer: {customer}")
        else:
            print("No customers in the queue.")

    def show_queue(self):
        print("Current queue:", list(self.queue))

# 測試
bank = BankQueue()
bank.add_customer("Alice")
bank.add_customer("Bob")
bank.show_queue()  # 輸出: Current queue: ['Alice', 'Bob']
bank.serve_customer()  # 輸出: Serving customer: Alice
bank.show_queue()  # 輸出: Current queue: ['Bob']

4. 隊列的高級應用

4.1 使用優先隊列實現任務調度

優先隊列（Priority Queue）是一種特殊的隊列，元素按照優先級出隊。請使用 heapq 模塊實現一個優先隊列，并完成以下操作： - 添加任務（add_task） - 處理最高優先級任務（process_task） - 顯示當前任務隊列

示例代碼：

import heapq

class PriorityQueue:
    def __init__(self):
        self.queue = []
        self.index = 0

    def add_task(self, task, priority):
        heapq.heappush(self.queue, (priority, self.index, task))
        self.index += 1
        print(f"Task '{task}' added with priority {priority}.")

    def process_task(self):
        if self.queue:
            priority, index, task = heapq.heappop(self.queue)
            print(f"Processing task: {task} (priority: {priority})")
        else:
            print("No tasks in the queue.")

    def show_queue(self):
        print("Current queue:", [task for priority, index, task in sorted(self.queue)])

# 測試
pq = PriorityQueue()
pq.add_task("Task1", 2)
pq.add_task("Task2", 1)
pq.show_queue()  # 輸出: Current queue: ['Task2', 'Task1']
pq.process_task()  # 輸出: Processing task: Task2 (priority: 1)
pq.show_queue()  # 輸出: Current queue: ['Task1']

4.2 使用隊列實現消息隊列

消息隊列是一種常見的分布式系統組件，用于解耦生產者和消費者。請使用 queue.Queue 實現一個簡單的消息隊列，并完成以下操作： - 生產者發送消息（send_message） - 消費者接收消息（receive_message） - 顯示當前消息隊列

示例代碼：

from queue import Queue
import threading

class MessageQueue:
    def __init__(self):
        self.queue = Queue()

    def send_message(self, message):
        self.queue.put(message)
        print(f"Message '{message}' sent.")

    def receive_message(self):
        if not self.queue.empty():
            message = self.queue.get()
            print(f"Received message: {message}")
        else:
            print("No messages in the queue.")

    def show_queue(self):
        print("Current queue:", list(self.queue.queue))

# 測試
mq = MessageQueue()
mq.send_message("Hello")
mq.send_message("World")
mq.show_queue()  # 輸出: Current queue: ['Hello', 'World']
mq.receive_message()  # 輸出: Received message: Hello
mq.show_queue()  # 輸出: Current queue: ['World']

5. 總結

本文通過一系列練習題，從基礎操作到高級應用，全面介紹了 Python 中隊列的使用。希望通過這些練習，您能夠更好地理解和掌握隊列的概念和應用場景。如果您有任何問題或建議，歡迎在評論區留言！

參考資料： - Python 官方文檔: https://docs.python.org/3/library/queue.html - 《算法導論》