数据结构与算法 / 系统课时

队列的先进先出模型

队列的先进先出模型

本课用任务排队示例说明队列的先进先出规则,并实现入队、出队、查看队头和判空操作。完成后,你能选择合适的底层容器,避免列表头部删除带来的线性移动开销。

学习目标

  • 理解队尾入队、队头出队的 FIFO 规则
  • 使用 deque 实现常用队列操作
  • 区分队列顺序与业务重试、持久化等职责

队列的两端职责

队列遵循先进先出,即最早进入的元素最先离开。新增元素固定从队尾进入,删除元素固定从队头发生;如果入队和出队都使用同一端,结构就会退化为栈。

队列先进先出的结构与数据流

Python 列表的 pop(0) 需要移动后续元素,时间复杂度为 O(n)O(n)。collections.deque 专门支持两端操作,append 和 popleft 均为 O(1)O(1),更适合作为普通队列的底层容器。

主示例

下面封装一个泛型队列。空队列执行 dequeue 或 front 时抛出明确异常,避免静默返回错误结果。

python
from collections import deque
from typing import Deque, Generic, TypeVar

T = TypeVar("T")

class Queue(Generic[T]):
    def __init__(self) -> None:
        self._items: Deque[T] = deque()

    def enqueue(self, item: T) -> None:
        self._items.append(item)

    def dequeue(self) -> T:
        if self.is_empty():
            raise IndexError("不能从空队列出队")
        return self._items.popleft()

    def front(self) -> T:
        if self.is_empty():
            raise IndexError("空队列没有队头元素")
        return self._items[0]

    def is_empty(self) -> bool:
        return not self._items

    def __len__(self) -> int:
        return len(self._items)

def main() -> None:
    tasks = Queue[str]()
    for task in ["生成课程结构", "生成课时正文", "执行导入校验"]:
        tasks.enqueue(task)

    print("当前队头:", tasks.front())
    while not tasks.is_empty():
        print("处理:", tasks.dequeue())
    print("剩余任务:", len(tasks))

if __name__ == "__main__":
    main()

预期输出:

text
当前队头: 生成课程结构
处理: 生成课程结构
处理: 生成课时正文
处理: 执行导入校验
剩余任务: 0

使用边界

front 只查看队头,不改变队列;dequeue 才会删除元素。队列只定义处理顺序,并不自动提供容量控制、失败重试、消息确认或持久化,这些能力需要由具体业务系统补充。

广度优先搜索也使用队列:先发现的节点先展开,因此可以按层或按最短边数逐步访问图和树。这里的关键仍是“发现顺序”和“处理顺序”保持一致。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

队列的先进先出模型

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通