队列实现与双端队列
使用 Python 的 deque 构建队列，实现循环队列，并用单调双端队列解决滑动窗口最大值问题。
队列实现与双端队列 是 CoddyKit 上的免费 DSA Interview Prep 课时。 这是第 2 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。
Queue 数据结构
队列是一种先进先出（FIFO）的数据结构。最先入队的元素会最先出队，就像商店里的结账队伍一样。核心操作包括 enqueue（添加到队尾）和 dequeue（从队首移除）。要使队列高效，这两种操作都必须是 O(1)。
使用 Python 列表作为队列看似方便，但这是错误的：list.pop(0) 的复杂度为 O(n)，因为所有元素都需要移动。正确的工具是 collections.deque，它提供 O(1) 的 appendleft、append、popleft 和 pop 操作。
from collections import deque
queue = deque()
# Enqueue (add to rear)
queue.append(10)
queue.append(20)
queue.append(30)
print('Queue:', queue) # deque([10, 20, 30])
# Peek front
print('Front:', queue[0]) # 10
# Dequeue (remove from front)
print('Dequeued:', queue.popleft()) # 10
print('Queue after:', queue) # deque([20, 30])使用双端队列实现 Queue 类
将 deque 封装在带有命名操作的 Queue 类中，以符合面试官的预期。内部的 enqueue 调用 append，而 dequeue 调用 popleft。peek 操作读取 queue[0]，但不会将其移除。
from collections import deque
class Queue:
def __init__(self):
self._data = deque()
def enqueue(self, val):
self._data.append(val)
def dequeue(self):
if self.is_empty():
raise IndexError('dequeue from empty queue')
return self._data.popleft()
def peek(self):
if self.is_empty():
raise IndexError('peek at empty queue')
return self._data[0]
def is_empty(self):
return len(self._data) == 0
def __len__(self):
return len(self._data)
q = Queue()
q.enqueue(1); q.enqueue(2); q.enqueue(3)
print(q.peek()) # 1
print(q.dequeue()) # 1
print(len(q)) # 2使用队列进行 BFS
队列的经典应用是广度优先搜索（BFS）。将根节点入队；当队列非空时，取出一个节点，处理它，然后将尚未访问的邻居节点入队。由于 BFS 按层处理节点，它可以自然地在无权图中找到最短路径。队列中始终最多保存相邻两层中的节点。
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbour in graph[node]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)
return order
graph = {0:[1,2], 1:[0,3,4], 2:[0,5], 3:[1], 4:[1], 5:[2]}
print(bfs(graph, 0)) # [0, 1, 2, 3, 4, 5]循环队列（LeetCode 622）
LeetCode 622“设计循环队列”：实现一个能够循环使用空间的固定容量队列。使用一个大小为 k 的数组和两个指针：head 与 tail。在队尾入队，在队首出队，并对 k 取模来计算位置。count 变量用于区分队列已满和为空的情况（否则，这两种状态按 k 取模后都会呈现相同的头尾位置）。
class MyCircularQueue:
def __init__(self, k):
self.data = [0] * k
self.head = 0
self.tail = 0
self.count = 0
self.k = k
def enQueue(self, value):
if self.isFull(): return False
self.data[self.tail] = value
self.tail = (self.tail + 1) % self.k
self.count += 1
return True
def deQueue(self):
if self.isEmpty(): return False
self.head = (self.head + 1) % self.k
self.count -= 1
return True
def Front(self):
return -1 if self.isEmpty() else self.data[self.head]
def Rear(self):
return -1 if self.isEmpty() else self.data[(self.tail - 1) % self.k]
def isEmpty(self): return self.count == 0
def isFull(self): return self.count == self.k
cq = MyCircularQueue(3)
print(cq.enQueue(1), cq.enQueue(2), cq.enQueue(3)) # True True True
print(cq.enQueue(4)) # False (full)
print(cq.Rear()) # 3
print(cq.isFull()) # True
print(cq.deQueue()) # True
print(cq.enQueue(4)) # True使用单调双端队列求滑动窗口最大值
LeetCode 239“滑动窗口最大值”：对于每个大小为 k 的窗口，找出其中的最大元素。暴力方法的复杂度为 O(n*k)。O(n) 的方法使用存储索引的单调递减双端队列。对于每个新元素：从队首移除窗口范围之外的索引；从队尾移除值更小的索引（它们不可能成为任何未来窗口的最大值）。队首始终保存最大值。
from collections import deque
def maxSlidingWindow(nums, k):
dq = deque() # stores indices, decreasing values
result = []
for i, n in enumerate(nums):
# Remove indices outside window
while dq and dq[0] < i - k + 1:
dq.popleft()
# Remove smaller elements from back
while dq and nums[dq[-1]] < n:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])
return result
print(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3))
# [3, 3, 5, 5, 6, 7]为什么队列要用双端队列，而不是普通列表？
Python 的 list.pop(0) 会以 O(n) 的复杂度移除第一个元素，因为其余每个元素都必须向左移动一位。进行 n 次插入和 n 次删除时，总复杂度就是 O(n²)。collections.deque 是由固定大小块组成的双向链表；popleft 只需调整一个指针，因此复杂度为 O(1)。对于包含 10^5 个节点的图进行 BFS 时，O(n) 与 O(n²) 的差别，就是 100 毫秒与 100 秒的差别。
import timeit
n = 10000
# Using list (O(n) per popleft)
list_time = timeit.timeit(
stmt='q = list(range(n)); [q.pop(0) for _ in range(n)]',
globals={'n': n}, number=10
)
# Using deque (O(1) per popleft)
from collections import deque
deque_time = timeit.timeit(
stmt='q = deque(range(n)); [q.popleft() for _ in range(n)]',
globals={'n': n, 'deque': deque}, number=10
)
print(f'List: {list_time:.4f}s')
print(f'Deque: {deque_time:.4f}s')
print(f'Speedup: {list_time / deque_time:.1f}x')二叉树的层序遍历（LeetCode 102）
LeetCode 102“二叉树的层序遍历”：按层返回所有节点值。使用一个队列；在每层开始时记录队列大小（也就是当前层的节点数）。恰好取出这么多个节点，收集它们的值，并将它们的子节点入队。重复此过程，直到队列为空。
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def levelOrder(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level = []
level_size = len(queue)
for _ in range(level_size):
node = queue.popleft()
level.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
result.append(level)
return result
root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(levelOrder(root)) # [[3], [9, 20], [15, 7]]使用 heapq 的优先队列
Python 的 heapq 模块提供最小堆（优先队列）：最小元素总是最先出队。heapq.heappush(h, item) 会以 O(log n) 的复杂度添加元素，heapq.heappop(h) 会以 O(log n) 的复杂度移除最小元素。对于迪杰斯特拉算法和前 k 个元素等问题，heapq 可以替代简单队列。
import heapq
pq = []
heapq.heappush(pq, 5)
heapq.heappush(pq, 1)
heapq.heappush(pq, 3)
heapq.heappush(pq, 2)
print('Min:', heapq.heappop(pq)) # 1
print('Min:', heapq.heappop(pq)) # 2
print('Min:', heapq.heappop(pq)) # 3
# Tasks with priorities
tasks = [(2, 'send email'), (1, 'fix bug'), (3, 'write docs')]
heapq.heapify(tasks)
while tasks:
priority, task = heapq.heappop(tasks)
print(f'Priority {priority}: {task}')解题模式：单词接龙中的队列
LeetCode 127“单词接龙”：将一个单词转换为另一个单词时，仅使用字典中的单词，求所需的最少单字符替换次数。可以将其建模为图：相差一个字符的单词之间有边相连。在该图上执行 BFS 可以找到最短路径（最少步数），时间复杂度为 O(n * L²)，其中 n 是字典大小，L 是单词长度。
from collections import deque
def ladderLength(beginWord, endWord, wordList):
word_set = set(wordList)
if endWord not in word_set:
return 0
queue = deque([(beginWord, 1)])
visited = {beginWord}
while queue:
word, steps = queue.popleft()
for i in range(len(word)):
for ch in 'abcdefghijklmnopqrstuvwxyz':
new_word = word[:i] + ch + word[i+1:]
if new_word == endWord:
return steps + 1
if new_word in word_set and new_word not in visited:
visited.add(new_word)
queue.append((new_word, steps + 1))
return 0
print(ladderLength('hit', 'cog', ['hot','dot','dog','lot','log','cog'])) # 5collections.deque 作为双端队列
collections.deque 是一种双端队列：您可以高效地从两端添加和移除元素。方法包括：用于前端的 appendleft 和 popleft，以及用于后端的 append 和 pop。因此，双端队列既可以充当 FIFO 队列（右端添加 + popleft），也可以充当 LIFO 栈（append + pop）。滑动窗口最大值会同时使用两端：从左侧移除旧索引，从右侧移除较小值。
from collections import deque
dq = deque([3, 4, 5])
dq.appendleft(2) # add to front: [2,3,4,5]
dq.appendleft(1) # add to front: [1,2,3,4,5]
dq.append(6) # add to rear: [1,2,3,4,5,6]
print(dq.popleft()) # 1 (from front)
print(dq.pop()) # 6 (from rear)
print(list(dq)) # [2, 3, 4, 5]队列、双端队列与堆总结
请根据问题选择合适的工具。需要按 FIFO 顺序处理数据或执行 BFS 时，请使用简单队列（双端队列）。需要求滑动窗口最大值或最小值时，请使用单调双端队列——它会移除不占优势的元素，从而维护有序不变量。需要获取不受顺序影响的全局最小值或最大值时，例如在迪杰斯特拉算法或前 k 个元素问题中，请使用优先队列（heapq）。知道该选择哪种工具以及选择原因，是面试官重点考查的技能。
快速检查
请检验您对本课中“数据结构与算法——编程面试准备”概念的理解。
课程回顾
本课中您学到了：collections.deque 提供 O(1) 的入队和出队操作，因此是 Python 中正确的队列实现；BFS 使用队列逐层处理节点，从而在无权图中寻找最短路径；以及单调递减双端队列通过移除不占优势的索引，在 O(n) 时间内解决滑动窗口最大值问题。接下来，我们将深入学习单调栈模式。
常见问题解答
「队列实现与双端队列」课时是免费的吗？
是的 — 「队列实现与双端队列」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。
「队列实现与双端队列」这节课中我会学到什么？
使用 Python 的 deque 构建队列，实现循环队列，并用单调双端队列解决滑动窗口最大值问题。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 DSA Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 2 节课，共 4 节。
「队列实现与双端队列」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 DSA Interview Prep 课中编写并运行代码吗？
能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。