队列

队列

简介

队列是一种操作受限的线性表，只允许在一端（队尾，Rear）进行插入操作，在另一端（队首，Front）进行删除操作。

队列的概念

队列（Queue）是一种常用的数据结构，也被称为后进先出表。它遵循先进先出（FIFO，First In First Out）的原则。

在Python中，虽然没有内置的队列类型，但我们可以使用内置模块 quere 或列表 list 或集合 set 来实现队列的基本操作。

队列的基本操作

• 入队（Enqueue）：在队尾添加一个元素。
• 出队（Dequeue）：从队首移除一个元素。
• 查看队首元素（Peek/Front）：不移除，仅查看队首元素。
• 检查队列是否为空（IsEmpty）：检查队列是否没有元素。

使用内置模块队列

import queue

# 创建一个新的队列
q = queue.Queue()

# 向队列中添加元素
for i in range(5):
    q.put(i)
    # 查看队列中的元素个数
    print(q.qsize())

# 从队列中取出元素
while not q.empty():
    print(q.get())

使用列表实现队列

使用列表的特定方法，也可以实现队列操作

class QueueUsingList:
    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)
        # 如果队列为空，则返回 None
        return None

    # 查看队首元素
    def peek(self):
        # 判断队列是否为空
        if not self.is_empty():
            # 不为空返回列表中的第一个元素
            return self.queue[0]
        # 为空返回 None
        return None

    # 判断队列是否为空
    def is_empty(self):
        # 判断列表中元素个数是否为 0
        return len(self.queue) == 0

    # 获取队列中元素个数
    def size(self):
        # 返回列表中元素个数
        return len(self.queue)

if __name__ == '__main__':
    # 应用代码
    q = QueueUsingList()

    for i in range(5):
        q.enqueue(i*10)
        print(q.size())

    while not q.is_empty():
        print(q.dequeue())

5. 队列的应用示例

队列常用于任务调度、广度优先搜索（BFS）等场景，最典型的就是各种排队叫号系统的应用。

任务调度示例

def task_scheduler():
    task_queue = QueueUsingDeque()
    # 假设我们有一系列任务
    tasks = ["任务1", "任务2", "任务3", "任务4"]

    # 将任务入队
    for task in tasks:
        task_queue.enqueue(task)

    # 按顺序处理任务
    while not task_queue.is_empty():
        current_task = task_queue.dequeue()
        print(f"正在执行任务: {current_task}")

# 调用函数
task_scheduler()

6. 总结

队列是一种重要的数据结构，理解其概念和实现对于编程和算法设计至关重要。