队列（Queue）完全详解¶
重要性：⭐⭐⭐⭐⭐ 难度：⭐⭐ 学习时间：2-3天 前置知识：数组、链表
📚 目录¶
什么是队列？¶
基本概念¶
队列是一种先进先出（FIFO, First In First Out）的线性数据结构。
生活中的例子¶
想象排队买票：
图：队列（Queue）的先进先出（FIFO）结构示意图
- 队首（Front）：允许删除的一端
- 队尾（Rear）：允许插入的一端
- 先进先出：先来的人先服务
为什么学队列？¶
✅ 应用广泛： - 任务调度（操作系统进程调度） - 消息队列（Kafka、RabbitMQ） - 缓冲区（生产者-消费者模型） - 广度优先搜索（BFS） - 打印机任务队列 - 呼叫中心等待队列
✅ 实现简单： - 基本操作：enqueue（入队）、dequeue（出队） - 时间复杂度都是O(1)
✅ 面试常考： - 用队列实现栈 - 滑动窗口最大值 - 二叉树的层序遍历 - 任务调度器
队列的实现¶
方法1：使用Python collections.deque（推荐）¶
Python
from collections import deque
class Queue:
"""使用deque实现队列"""
def __init__(self):
self.items = deque()
def enqueue(self, item):
"""入队：O(1)"""
self.items.append(item)
print(f"入队: {item}")
def dequeue(self):
"""出队：O(1)"""
if not self.is_empty():
item = self.items.popleft()
print(f"出队: {item}")
return item
raise IndexError("队列为空，无法出队")
def peek(self):
"""查看队首元素：O(1)"""
if not self.is_empty():
return self.items[0]
raise IndexError("队列为空")
def is_empty(self):
"""判断队列是否为空"""
return len(self.items) == 0
def size(self):
"""返回队列的大小"""
return len(self.items)
def __str__(self):
return f"队首 -> {list(self.items)} <- 队尾"
# 测试
queue = Queue()
print("初始状态:", queue)
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print("当前队列:", queue)
print("队首元素:", queue.peek())
print("队列大小:", queue.size())
queue.dequeue()
queue.dequeue()
print("出队两次后:", queue)
# 输出：
# 初始状态: 队首 -> [] <- 队尾
# 入队: 1
# 入队: 2
# 入队: 3
# 当前队列: 队首 -> [1, 2, 3] <- 队尾
# 队首元素: 1
# 队列大小: 3
# 出队: 1
# 出队: 2
# 出队两次后: 队首 -> [3] <- 队尾
方法2：使用链表¶
Python
class QueueNode:
"""队列节点"""
def __init__(self, data):
self.data = data
self.next = None
class LinkedListQueue:
"""使用链表实现队列"""
def __init__(self):
self.front = None # 队首指针
self.rear = None # 队尾指针
self.size = 0
def enqueue(self, item):
"""入队：O(1)"""
new_node = QueueNode(item)
if self.is_empty():
# 队列为空，新节点既是队首也是队尾
self.front = self.rear = new_node
else:
# 队列不为空，新节点成为新的队尾
self.rear.next = new_node
self.rear = new_node
self.size += 1
print(f"入队: {item}")
def dequeue(self):
"""出队：O(1)"""
if not self.is_empty():
item = self.front.data
# 移动队首指针
self.front = self.front.next
# 如果队首变为None，队尾也设为None
if self.front is None:
self.rear = None
self.size -= 1
print(f"出队: {item}")
return item
raise IndexError("队列为空，无法出队")
def peek(self):
"""查看队首元素：O(1)"""
if not self.is_empty():
return self.front.data
raise IndexError("队列为空")
def is_empty(self):
"""判断队列是否为空"""
return self.front is None
def get_size(self):
"""返回队列的大小"""
return self.size
def __str__(self):
items = []
current = self.front
while current:
items.append(str(current.data))
current = current.next
return f"队首 -> {' -> '.join(items)} <- 队尾"
# 测试
queue = LinkedListQueue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print("当前队列:", queue)
print("队首元素:", queue.peek())
print("队列大小:", queue.get_size())
queue.dequeue()
print("出队后:", queue)
# 输出：
# 入队: 1
# 入队: 2
# 入队: 3
# 当前队列: 队首 -> 1 -> 2 -> 3 <- 队尾
# 队首元素: 1
# 队列大小: 3
# 出队: 1
# 出队后: 队首 -> 2 -> 3 <- 队尾
方法3：使用C++ STL queue¶
C++
#include <iostream> // 引入头文件
#include <queue>
using namespace std;
int main() {
// 创建队列
queue<int> q;
// 入队
q.push(1);
q.push(2);
q.push(3);
// 访问队首
cout << "队首元素: " << q.front() << endl; // 1
// 访问队尾
cout << "队尾元素: " << q.back() << endl; // 3
// 队列大小
cout << "队列大小: " << q.size() << endl; // 3
// 出队
q.pop();
cout << "出队后队首: " << q.front() << endl; // 2
// 判断是否为空
cout << "队列是否为空: " << (q.empty() ? "是" : "否") << endl; // 否
return 0;
}
队列的操作详解¶
操作1：入队（Enqueue）¶
Python
def enqueue_detailed(queue, items):
"""详细演示入队过程"""
print("=" * 50)
print("入队操作演示")
print("=" * 50)
for item in items:
print(f"\n步骤: 将 {item} 入队")
print(f"入队前: {queue}")
queue.enqueue(item)
print(f"入队后: {queue}")
print(f"队首: {queue.peek()}")
print(f"大小: {queue.size()}")
# 测试
queue = Queue()
enqueue_detailed(queue, [1, 2, 3, 4, 5])
# 输出：
# ==================================================
# 入队操作演示
# ==================================================
#
# 步骤: 将 1 入队
# 入队前: 队首 -> [] <- 队尾
# 入队: 1
# 入队后: 队首 -> [1] <- 队尾
# 队首: 1
# 大小: 1
#
# 步骤: 将 2 入队
# 入队前: 队首 -> [1] <- 队尾
# 入队: 2
# 入队后: 队首 -> [1, 2] <- 队尾
# 队首: 1
# 大小: 2
#
# ...（继续）
入队过程图解：
Text Only
初始状态：
队首 队尾
└─┘
[]
enqueue(1):
队首 队尾
└─1┘
[1]
enqueue(2):
队首 队尾
└─1─2┘
[1, 2]
enqueue(3):
队首 队尾
└─1─2─3┘
[1, 2, 3]
操作2：出队（Dequeue）¶
Python
def dequeue_detailed(queue, n):
"""详细演示出队过程"""
print("=" * 50)
print("出队操作演示")
print("=" * 50)
for i in range(n):
if queue.is_empty():
print("\n队列已为空，无法出队")
break
print(f"\n步骤 {i+1}: 出队")
print(f"出队前: {queue}")
print(f"队首: {queue.peek()}")
item = queue.dequeue()
print(f"出队后: {queue}")
print(f"取出元素: {item}")
# 测试
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print("初始队列:", queue)
dequeue_detailed(queue, 5)
# 输出：
# ==================================================
# 出队操作演示
# ==================================================
#
# 步骤 1: 出队
# 出队前: 队首 -> [1, 2, 3] <- 队尾
# 队首: 1
# 出队: 1
# 出队后: 队首 -> [2, 3] <- 队尾
# 取出元素: 1
#
# 步骤 2: 出队
# 出队前: 队首 -> [2, 3] <- 队尾
# 队首: 2
# 出队: 2
# 出队后: 队首 -> [3] <- 队尾
# 取出元素: 2
#
# 步骤 3: 出队
# 出队前: 队首 -> [3] <- 队尾
# 队首: 3
# 出队: 3
# 出队后: 队首 -> [] <- 队尾
# 取出元素: 3
#
# 步骤 4: 出队
#
# 队列已为空，无法出队
出队过程图解：
Text Only
初始状态：[1, 2, 3]
队首 队尾
└─1─2─3┘
第1次dequeue():
取出: 1
队首 队尾
└─2─3┘
[2, 3]
第2次dequeue():
取出: 2
队首 队尾
└─3┘
[3]
第3次dequeue():
取出: 3
队首 队尾
└─┘
[]
队列的应用¶
应用1：二叉树的层序遍历 ⭐⭐⭐⭐⭐¶
问题：给你二叉树的根节点，返回其节点值的层序遍历。
示例：
解法：使用队列
Python
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 level_order(root):
"""
二叉树的层序遍历
时间：O(n)
空间：O(n)
"""
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue) # 当前层的节点数
level = [] # 存储当前层的值
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)
print(f"层 {len(result)}: {level}")
return result
def level_order_detailed(root):
"""详细版：展示每一步"""
print("=" * 60)
print("二叉树层序遍历（详细版）")
print("=" * 60)
if not root:
print("树为空")
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
level = []
print(f"\n当前层 {len(result) + 1} 有 {level_size} 个节点")
print(f"队列状态: {[node.val for node in queue]}")
for i in range(level_size):
node = queue.popleft()
level.append(node.val)
print(f" 处理节点 {node.val}")
# 子节点入队
children = []
if node.left:
queue.append(node.left)
children.append(f"左: {node.left.val}")
if node.right:
queue.append(node.right)
children.append(f"右: {node.right.val}")
if children:
print(f" 子节点入队: {', '.join(children)}")
result.append(level)
print(f"第 {len(result)} 层结果: {level}")
print("\n" + "=" * 60)
print("最终结果:", result)
return result
# 构建测试树
# 3
# / \
# 9 20
# / \
# 15 7
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
# 测试
result = level_order_detailed(root)
# 输出：
# ============================================================
# 二叉树层序遍历（详细版）
# ============================================================
#
# 当前层 1 有 1 个节点
# 队列状态: [3]
# 处理节点 3
# 子节点入队: 左: 9, 右: 20
# 第 1 层结果: [3]
#
# 当前层 2 有 2 个节点
# 队列状态: [9, 20]
# 处理节点 9
# 处理节点 20
# 子节点入队: 左: 15, 右: 7
# 第 2 层结果: [9, 20]
#
# 当前层 3 有 2 个节点
# 队列状态: [15, 7]
# 处理节点 15
# 处理节点 7
# 第 3 层结果: [15, 7]
#
# ============================================================
# 最终结果: [[3], [9, 20], [15, 7]]
层序遍历过程图解：
Text Only
初始队列: [3]
第1层:
处理: 3
队列: [9, 20]
结果: [[3]]
第2层:
处理: 9, 20
队列: [15, 7]
结果: [[3], [9, 20]]
第3层:
处理: 15, 7
队列: []
结果: [[3], [9, 20], [15, 7]]
最终: [[3], [9, 20], [15, 7]]
图：使用队列进行二叉树层序遍历的过程
应用2：滑动窗口最大值 ⭐⭐⭐⭐⭐¶
问题：给你一个整数数组 nums 和一个整数 k，找出滑动窗口中的最大值。
示例：
Text Only
输入：nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
输出：[3, 3, 5, 5, 6, 7]
解释：
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
解法：单调队列
Python
from collections import deque
def max_sliding_window(nums, k):
"""
滑动窗口最大值
时间：O(n)
空间：O(k)
使用单调递减队列
"""
from collections import deque
result = []
# 队列存储索引（不是值！）
window = deque()
for i, num in enumerate(nums):
print(f"\n处理索引 {i}, 值 {num}")
print(f" 当前队列: {list(window)}")
# 1. 移除窗口外的元素
while window and window[0] <= i - k:
removed_idx = window.popleft()
print(f" 移除窗口外索引 {removed_idx}")
# 2. 移除小于当前元素的值
while window and nums[window[-1]] < num:
removed_idx = window.pop()
print(f" 移除较小值索引 {removed_idx} (值{nums[removed_idx]} < {num})")
# 3. 添加当前元素
window.append(i)
print(f" 添加索引 {i}，队列: {list(window)}")
# 4. 记录窗口最大值
if i >= k - 1:
max_val = nums[window[0]]
result.append(max_val)
print(f" 窗口 [{i-k+1}..{i}] 最大值: {max_val}")
print("\n" + "=" * 60)
print(f"最终结果: {result}")
return result
# 测试
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print("="*60)
print(f"输入: nums = {nums}, k = {k}")
max_sliding_window(nums, k)
# 输出：
# ============================================================
# 输入: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
#
# 处理索引 0, 值 1
# 当前队列: []
# 添加索引 0，队列: [0]
#
# 处理索引 1, 值 3
# 当前队列: [0]
# 移除较小值索引 0 (值1 < 3)
# 添加索引 1，队列: [1]
#
# 处理索引 2, 值 -1
# 当前队列: [1]
# 添加索引 2，队列: [1, 2]
# 窗口 [0..2] 最大值: 3
#
# 处理索引 3, 值 -3
# 当前队列: [1, 2]
# 添加索引 3，队列: [1, 2, 3]
# 窗口 [1..3] 最大值: 3
#
# 处理索引 4, 值 5
# 当前队列: [1, 2, 3]
# 移除窗口外索引 1
# 移除较小值索引 3 (值-3 < 5)
# 移除较小值索引 2 (值-1 < 5)
# 添加索引 4，队列: [4]
# 窗口 [2..4] 最大值: 5
#
# ...（继续）
#
# 最终结果: [3, 3, 5, 5, 6, 7]
滑动窗口过程图解：
Text Only
nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
窗口1: [1, 3, -1]
队列: [3, -1, 1] → 最大: 3
窗口2: [3, -1, -3]
队列: [3, -1, -3] → 最大: 3
窗口3: [-1, -3, 5]
队列: [5] → 最大: 5
窗口4: [-3, 5, 3]
队列: [5, 3] → 最大: 5
窗口5: [5, 3, 6]
队列: [6] → 最大: 6
窗口6: [3, 6, 7]
队列: [7] → 最大: 7
结果: [3, 3, 5, 5, 6, 7]
图：使用单调队列计算滑动窗口最大值的过程
应用3：任务调度器 ⭐⭐⭐⭐¶
问题：给定一个用字符数组表示的CPU任务列表，其中包含使用大写的英文字母表示的26种不同任务。任务可以以任意顺序执行，并且每个任务都可以在1个单位时间内执行完。CPU在任何一个单位时间内都可以执行一个任务，或者在待命状态。然而，两个相同种类的任务之间必须有长度为 n 的冷却时间，因此至少有连续 n 个单位时间内CPU在执行不同的任务，或者在待命状态。
示例：
Text Only
输入：tasks = ["A","A","A","B","B","B"], n = 2
输出：8
解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B
解法：模拟队列
Python
from collections import deque, Counter # Counter计数器：统计元素出现次数
def least_interval(tasks, n):
"""
任务调度器
时间：O(m)，m是任务总数
空间：O(1)
"""
# 统计任务频率
task_count = Counter(tasks)
max_freq = max(task_count.values())
# 计算需要多少个max_freq的任务
max_count = sum(1 for count in task_count.values() if count == max_freq)
# 计算最短时间
# 公式：(max_freq - 1) * (n + 1) + max_count
min_time = (max_freq - 1) * (n + 1) + max_count
# 如果任务数多于计算出的时间，返回任务数
result = max(min_time, len(tasks))
print(f"任务频率: {dict(task_count)}")
print(f"最高频率: {max_freq}")
print(f"最高频率任务数: {max_count}")
print(f"计算时间: ({max_freq} - 1) * ({n} + 1) + {max_count} = {min_time}")
print(f"实际时间: max({min_time}, {len(tasks)}) = {result}")
return result
# 测试
tasks = ["A", "A", "A", "B", "B", "B"]
n = 2
print("=" * 60)
print(f"输入: tasks = {tasks}, n = {n}")
result = least_interval(tasks, n)
print(f"输出: {result}")
# 输出：
# ============================================================
# 输入: tasks = ['A', 'A', 'A', 'B', 'B', 'B'], n = 2
# 任务频率: {'A': 3, 'B': 3}
# 最高频率: 3
# 最高频率任务数: 2
# 计算时间: (3 - 1) * (2 + 1) + 2 = 8
# 实际时间: max(8, 6) = 8
# 输出: 8
任务调度过程图解：
Text Only
tasks = ["A","A","A","B","B","B"], n = 2
A出现3次，B出现3次
任务序列：
A → B → 待命 → A → B → 待命 → A → B
└─────┘ └─────┘ └─────┘
间隔=n=2 间隔=n=2 间隔=n=2
总时间: 8
经典面试题¶
题目1：用队列实现栈 ⭐⭐⭐⭐¶
问题：使用两个队列实现栈。
解法：
Python
class MyStack:
"""
用两个队列实现栈
时间：
- push: O(n)
- pop: O(1)
- top: O(1)
空间：O(n)
"""
def __init__(self):
# 主队列
self.queue1 = []
# 辅助队列
self.queue2 = []
def push(self, x: int) -> None:
"""入栈：O(n)"""
# 新元素入辅助队列
self.queue2.append(x)
# 将主队列的所有元素转移到辅助队列
while self.queue1:
self.queue2.append(self.queue1.pop(0))
# 交换队列
self.queue1, self.queue2 = self.queue2, self.queue1
print(f"push({x}): queue1={self.queue1}")
def pop(self) -> int:
"""出栈：O(1)"""
if self.queue1:
val = self.queue1.pop(0)
print(f"pop(): {val}, queue1={self.queue1}")
return val
raise IndexError("栈为空")
def top(self) -> int:
"""查看栈顶：O(1)"""
if self.queue1:
return self.queue1[0]
raise IndexError("栈为空")
def empty(self) -> bool:
"""判断栈是否为空"""
return not self.queue1
# 测试
stack = MyStack()
print("=" * 60)
print("用队列实现栈测试")
print("=" * 60)
stack.push(1)
stack.push(2)
stack.push(3)
print(f"\n栈顶: {stack.top()}") # 3
stack.pop()
print(f"\n出栈后栈顶: {stack.top()}") # 2
# 输出：
# ============================================================
# 用队列实现栈测试
# ============================================================
# push(1): queue1=[1]
# push(2): queue1=[2, 1]
# push(3): queue1=[3, 2, 1]
#
# 栈顶: 3
# pop(): 3, queue1=[2, 1]
#
# 出栈后栈顶: 2
用队列实现栈图解：
Text Only
初始状态:
queue1: []
queue2: []
push(1):
queue2: [1]
queue1 -> queue2
queue1: [1]
queue2: []
push(2):
queue2: [2]
queue1 -> queue2
queue1: [2, 1]
queue2: []
push(3):
queue2: [3]
queue1 -> queue2
queue1: [3, 2, 1]
queue2: []
pop():
取出: 3
queue1: [2, 1]
题目2：设计循环队列 ⭐⭐⭐⭐¶
问题：设计你的循环队列实现。循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为"环形缓冲器"。
解法：
Python
class MyCircularQueue:
"""
循环队列
时间：O(1) 所有操作
空间：O(k)
"""
def __init__(self, k: int):
"""初始化，队列大小为k"""
self.capacity = k
self.queue = [0] * k
self.head = -1 # 队首指针
self.tail = -1 # 队尾指针
self.size = 0 # 当前大小
def enQueue(self, value: int) -> bool:
"""入队：O(1)"""
if self.isFull():
print(f"入队失败: 队列已满")
return False
if self.isEmpty():
self.head = 0
self.tail = (self.tail + 1) % self.capacity
self.queue[self.tail] = value
self.size += 1
print(f"入队: {value}, head={self.head}, tail={self.tail}, queue={self.queue[:self.size+1]}")
return True
def deQueue(self) -> bool:
"""出队：O(1)"""
if self.isEmpty():
print(f"出队失败: 队列为空")
return False
val = self.queue[self.head]
print(f"出队: {val}")
if self.head == self.tail:
# 队列只有一个元素
self.head = -1
self.tail = -1
else:
self.head = (self.head + 1) % self.capacity
self.size -= 1
return True
def Front(self) -> int:
"""获取队首元素：O(1)"""
if self.isEmpty():
return -1
return self.queue[self.head]
def Rear(self) -> int:
"""获取队尾元素：O(1)"""
if self.isEmpty():
return -1
return self.queue[self.tail]
def isEmpty(self) -> bool:
"""判断队列是否为空：O(1)"""
return self.size == 0
def isFull(self) -> bool:
"""判断队列是否已满：O(1)"""
return self.size == self.capacity
# 测试
queue = MyCircularQueue(3)
print("=" * 60)
print("循环队列测试")
print("=" * 60)
queue.enQueue(1)
queue.enQueue(2)
queue.enQueue(3)
print(f"\n队首: {queue.Front()}, 队尾: {queue.Rear()}")
queue.enQueue(4) # 队列已满
queue.deQueue()
queue.enQueue(4)
print(f"\n队首: {queue.Front()}, 队尾: {queue.Rear()}")
# 输出：
# ============================================================
# 循环队列测试
# ============================================================
# 入队: 1, head=0, tail=0, queue=[1]
# 入队: 2, head=0, tail=1, queue=[1, 2]
# 入队: 3, head=0, tail=2, queue=[1, 2, 3]
#
# 队首: 1, 队尾: 3
# 入队失败: 队列已满
# 出队: 1
# 入队: 4, head=1, tail=0, queue=[2, 3, 4]
#
# 队首: 2, 队尾: 4
循环队列图解：
Text Only
容量: 3
初始状态:
[_, _, _]
head=-1, tail=-1
enQueue(1):
[1, _, _]
head=0, tail=0
enQueue(2):
[1, 2, _]
head=0, tail=1
enQueue(3):
[1, 2, 3]
head=0, tail=2
队列已满！
enQueue(4):
失败
deQueue():
取出1
[_, 2, 3]
head=1, tail=2
enQueue(4):
[4, 2, 3]
head=1, tail=0（循环！）
双端队列¶
什么是双端队列？¶
双端队列（Deque, Double Ended Queue）允许在两端进行插入和删除操作。
Python实现¶
Python
from collections import deque
# 创建双端队列
dq = deque()
# 在右端操作
dq.append(1) # 右端入队: [1]
dq.append(2) # 右端入队: [1, 2]
print(dq.pop()) # 右端出队: 2
# 在左端操作
dq.appendleft(0) # 左端入队: [0, 1]
print(dq.popleft()) # 左端出队: 0
# 查看两端
print(dq[0]) # 队首
print(dq[-1]) # 队尾
# 限制大小
dq = deque(maxlen=3)
dq.append(1)
dq.append(2)
dq.append(3)
dq.append(4) # 自动移除最左端的元素
print(dq) # deque([2, 3, 4], maxlen=3)
应用：滑动窗口¶
Python
from collections import deque
def sliding_window(nums, k):
"""使用双端队列实现滑动窗口"""
window = deque()
result = []
for i, num in enumerate(nums): # enumerate同时获取索引和值
# 移除窗口外的元素
while window and window[0] <= i - k:
window.popleft()
# 维护单调递减
while window and nums[window[-1]] < num: # 负索引：从末尾倒数访问元素
window.pop()
window.append(i)
# 记录结果
if i >= k - 1:
result.append(nums[window[0]])
return result
优先队列¶
什么是优先队列？¶
优先队列是一种特殊的队列，每个元素都有优先级，出队时优先级最高的先出。
Python实现（使用heapq）¶
Python
import heapq
class PriorityQueue:
"""优先队列（最小堆）"""
def __init__(self):
self.heap = []
def push(self, item, priority):
"""入队：O(log n)"""
heapq.heappush(self.heap, (priority, item))
print(f"入队: {item} (优先级{priority})")
def pop(self):
"""出队：O(log n)"""
if self.heap:
priority, item = heapq.heappop(self.heap)
print(f"出队: {item} (优先级{priority})")
return item
raise IndexError("优先队列为空")
def peek(self):
"""查看最高优先级：O(1)"""
if self.heap:
return self.heap[0][1]
raise IndexError("优先队列为空")
# 测试
pq = PriorityQueue()
pq.push("任务A", 3)
pq.push("任务B", 1)
pq.push("任务C", 2)
pq.pop() # 任务B（优先级1）
pq.pop() # 任务C（优先级2）
pq.pop() # 任务A（优先级3）
# 输出：
# 入队: 任务A (优先级3)
# 入队: 任务B (优先级1)
# 入队: 任务C (优先级2)
# 出队: 任务B (优先级1)
# 出队: 任务C (优先级2)
# 出队: 任务A (优先级3)
📝 总结¶
核心要点¶
✅ 队列的特点： - 先进先出（FIFO） - 两端操作：队首出队、队尾入队 - 入队和出队都是O(1)
✅ 队列的实现： - Python deque：高效 - 链表：动态大小 - C++ queue：STL容器
✅ 队列的应用： - 层序遍历 - 滑动窗口 - 任务调度 - BFS - 缓冲区
✅ 高级队列： - 双端队列（Deque） - 优先队列（Priority Queue） - 循环队列（Circular Queue）
下一步¶
继续学习： - 哈希表详解 - 键值对存储 - 树基础 - 层次结构
继续查看其他教程...