数据结构与算法 / 系统课时
队列的先进先出模型
队列的先进先出模型
本课用任务排队示例说明队列的先进先出规则,并实现入队、出队、查看队头和判空操作。完成后,你能选择合适的底层容器,避免列表头部删除带来的线性移动开销。
学习目标
- 理解队尾入队、队头出队的 FIFO 规则
- 使用
deque实现常用队列操作 - 区分队列顺序与业务重试、持久化等职责
队列的两端职责
队列遵循先进先出,即最早进入的元素最先离开。新增元素固定从队尾进入,删除元素固定从队头发生;如果入队和出队都使用同一端,结构就会退化为栈。

Python 列表的 pop(0) 需要移动后续元素,时间复杂度为 。collections.deque 专门支持两端操作,append 和 popleft 均为 ,更适合作为普通队列的底层容器。
主示例
下面封装一个泛型队列。空队列执行 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 才会删除元素。队列只定义处理顺序,并不自动提供容量控制、失败重试、消息确认或持久化,这些能力需要由具体业务系统补充。
广度优先搜索也使用队列:先发现的节点先展开,因此可以按层或按最短边数逐步访问图和树。这里的关键仍是“发现顺序”和“处理顺序”保持一致。
按自己的节奏,确认真正理解。