队列与 collections.deque
快速从两端入队和出队
队列与 collections.deque 是 CoddyKit 上的免费 Competitive Programming Academy 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Competitive Programming Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Competitive Programming Academy 课程共包含 4 节课。
先进先出
队列按照元素到达的顺序处理它们，就像商店门口的队伍。先进入的元素先出去。
为什么不使用列表
列表可以从前端弹出元素，但 pop(0) 需要 O(n) 时间，因为其他每个元素都要向左移动。对于大型输入来说，这太慢了。
q = []
q.pop(0) # O(n), avoid this认识 collections.deque
collections 中的双端队列可以在两端以 O(1) 时间添加和移除元素。它是竞赛编程中的首选结构。
from collections import deque
q = deque()在队尾入队
使用 append 将新元素添加到右端，就像操作列表一样。这一端就是队列的队尾。
q.append(1)
q.append(2)从队首出队
使用 popleft 从左端移除最早加入的元素。该操作为常数时间，并实现真正的 FIFO 行为。
first = q.popleft() # returns 1两端都可以操作
双端队列还支持 appendleft 和从右端调用 pop。这种灵活性让一个结构既可以充当栈，也可以充当队列。
q.appendleft(0)
last = q.pop()弹出前先检查
从空双端队列中移除元素会引发错误，因此在循环中请用 while q 检查，以确保遍历安全。
while q:
x = q.popleft()队列驱动 BFS
竞赛编程中最常见的用途是BFS。您先将起始节点入队，然后不断从队首弹出节点并加入它的邻居。
简易 BFS 框架
这个循环会逐层访问节点。每个邻居都会被加入队列，之后按照到达顺序进行处理。
while q:
node = q.popleft()
for nb in graph[node]:
q.append(nb)限制双端队列大小
设置最大长度后，双端队列已满时会丢弃最早的元素，非常适合滑动窗口和近期历史记录。
window = deque(maxlen=3)一种结构，多种用途
请记住，双端队列在两端都很快，因此需要队列、栈或滑动缓冲区时都可以优先考虑它。
快速检查
您需要在队列中快速移除队首元素。哪种选择是正确的？
回顾：双端队列是快速队列
您认识了 collections.deque：使用 append 和 popleft 实现 O(1) 的 FIFO，两端都可以操作，还能用最大长度处理窗口。它是 BFS 的基础。🎯
用 AI 导师学习 Python — 免费
在浏览器中编写并运行真实代码，获得全天候 AI 导师的即时帮助，并在网页或应用中继续学习。
- 课程
- 30
- 课程
- 120
常见问题解答
「队列与 collections.deque」课时是免费的吗？
是的 — 「队列与 collections.deque」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Competitive Programming Academy 课程的其余内容，请升级到 CoddyKit PRO。 Competitive Programming Academy 课程共包含 4 节课。
「队列与 collections.deque」这节课中我会学到什么？
快速从两端入队和出队 你通过在浏览器中直接运行的动手代码来练习 Competitive Programming Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Competitive Programming Academy 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Competitive Programming Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。
「队列与 collections.deque」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Competitive Programming Academy 课中编写并运行代码吗？
能。每节 Competitive Programming Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 使用栈匹配括号
- 单调栈：下一个更大元素
- 队列与 collections.deque
- 使用双端队列求滑动窗口最大值