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） - 查看队列大小（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 - 《算法导论》