第4讲队列Queue目标让完全没学过编程的人也能理解队列的本质并亲手用Python跑代码验证。一、先讲个故事排队买票场景火车站售票窗口你去火车站买票看到一条长长的队伍窗口 → 张三 → 李四 → 王五 → 赵六 ↑队首 ↑队尾规则排队只能站在队伍最后面 (enqueue/入队)买票只有队首的人能买票 (dequeue/出队)看队首看看谁排在第一个但不让他走 (peek)核心特点先来的先买票后来的后排着这就是FIFOFirstInFirstOut (先进先出)生活中的队列场景为什么像队列排队买奶茶先来的先拿到打印机任务先发送的先打印消息通知先发来的消息先显示BFS广度优先搜索先访问的节点先扩展二、队列 vs 栈本质区别栈 (Stack) - LIFO 队列 (Queue) - FIFO 食堂餐盘 排队买票 ┌─────┐ 张三 → 李四 → 王五 │ 新 │ ← 栈顶 ↑队首 ↑队尾 ├─────┤ │ 旧 │ 出队 ←────── 入队 └─────┘ 后放的先拿 先来的先走操作栈 (LIFO)队列 (FIFO)添加元素push(放栈顶)enqueue(放队尾)移除元素pop(拿栈顶)dequeue(拿队首)看但不拿peek(看栈顶)peek(看队首)生活例子撤销操作排队买票三、队列的基本操作3.1 四个基本操作初始: 空队列 [] enqueue(张三): [张三] ↑队首队尾 enqueue(李四): [张三, 李四] ↑队首 ↑队尾 enqueue(王五): [张三, 李四, 王五] ↑队首 ↑队尾 peek(): 看到 张三 (队首), 但不让他走 dequeue(): 张三 买票走了! [李四, 王五] ↑队首 ↑队尾 dequeue(): 李四 买票走了! [王五] ↑队首队尾 dequeue(): 王五 买票走了! [] 空队列!3.2 Python实现classQueue:def__init__(self):self.items[]defenqueue(self,item):排队: 放到队尾self.items.append(item)print(fenqueue({item}):{self.items})defdequeue(self):出队: 队首离开ifself.is_empty():print(dequeue(): 队列空了! 没人了)returnNoneitemself.items.pop(0)# 拿走第0个(队首)print(fdequeue():{item}离开了, 剩余{self.items})returnitemdefpeek(self):看队首, 但不让他走ifself.is_empty():returnNonereturnself.items[0]defis_empty(self):队列是不是空的returnlen(self.items)0defsize(self):队列里有多少人returnlen(self.items)# 测试queueQueue()queue.enqueue(张三)queue.enqueue(李四)queue.enqueue(王五)print(f当前队首:{queue.peek()})print(f队列长度:{queue.size()})queue.dequeue()queue.dequeue()queue.dequeue()queue.dequeue()# 再出就空了⚠️注意上面的实现用pop(0)从列表头部删除时间复杂度是O(n)因为后面所有元素都要前移。四、Python的deque双端队列4.1 为什么需要deque普通列表pop(0)很慢 (O(n))因为原列表: [A, B, C, D, E] ↑队首 pop(0)后: [B, C, D, E] ↑队首 B,C,D,E 都要前移一位! → O(n)deque(双端队列) 用链表实现两头操作都是O(1)deque: A ↔ B ↔ C ↔ D ↔ E ↑ ↑ 队首 队尾 从队首删除A: B ↔ C ↔ D ↔ E ↑ 新队首 只需要改两个指针! → O(1)4.2 deque代码演示fromcollectionsimportdeque# 创建空队列qdeque()# 入队 (右边/队尾)q.append(张三)q.append(李四)# 也可以从左边入队q.appendleft(VIP)# VIP插队到最前面!# 出队 (左边/队首)personq.popleft()# 看队首/队尾print(f队首:{q[0]})print(f队尾:{q[-1]})# 遍历队列forpersoninq:print(person)4.3 deque vs list 性能对比fromcollectionsimportdequeimporttime# list: pop(0)list_datalist(range(100000))starttime.time()for_inrange(10000):list_data.pop(0)endtime.time()print(flist pop(0) 10000次:{(end-start)*1000:.2f}ms)# deque: popleft()deque_datadeque(range(100000))starttime.time()for_inrange(10000):deque_data.popleft()endtime.time()print(fdeque popleft() 10000次:{(end-start)*1000:.2f}ms)# 结论: deque从头部删除比list快几百倍!五、单调队列滑动窗口最大值5.1 问题引入问题给定数组找每个大小为k的滑动窗口中的最大值。数组: [1, 3, -1, -3, 5, 3, 6, 7], k3 窗口1: [1, 3, -1] 最大值 3 窗口2: [3, -1, -3] 最大值 3 窗口3: [-1, -3, 5] 最大值 5 窗口4: [-3, 5, 3] 最大值 5 窗口5: [5, 3, 6] 最大值 6 窗口6: [3, 6, 7] 最大值 7 结果: [3, 3, 5, 5, 6, 7]暴力做法每个窗口遍历找最大值 → O(n×k)单调队列优化维护一个单调递减的队列队首永远是最大值 → O(n)5.2 单调队列原理核心思想队列里存的是可能成为最大值的元素的索引并且保持递减。第0个(1): 队列空, 入队 队列: [0(1)] 第1个(3): 3 队尾1, 1永远不可能是最大值了, 弹出 入队 1(3) 队列: [1(3)] 第2个(-1): -1 队尾3, 入队 队列: [1(3), 2(-1)] 窗口满了! 队首1(3)就是最大值 输出: 3 第4个(5): 5 队尾-3, 弹出 5 队尾-1, 弹出 5 队尾3, 弹出 入队 4(5) 队列: [4(5)] 输出: 5关键新元素进来时把前面比它小的都弹出 —— 因为它们永远不可能是最大值了5.3 代码实现fromcollectionsimportdequedefmax_sliding_window(nums,k):result[]qdeque()# 存索引, 对应值单调递减fori,numinenumerate(nums):# 1. 把前面比当前小的都弹出whileqandnums[q[-1]]num:q.pop()# 2. 当前索引入队q.append(i)# 3. 检查队首是否滑出窗口ifq[0]i-k1:q.popleft()# 4. 窗口满了, 记录最大值(队首)ifik-1:result.append(nums[q[0]])returnresult# 测试nums[1,3,-1,-3,5,3,6,7]k3print(f数组:{nums}, k{k})print(f滑动窗口最大值:{max_sliding_window(nums,k)})# 输出: [3, 3, 5, 5, 6, 7]六、LeetCode实战 题目1用栈实现队列LC 232题目用两个栈实现队列的 enqueue, dequeue, peek, empty。解法双栈classMyQueue: 思路: 两个栈 - 输入栈: 负责接收新元素 (push) - 输出栈: 负责出队 (pop), 当输出栈空时, 把输入栈全部倒过来 关键: 把输入栈倒到输出栈, 顺序就反了, 实现了FIFO! def__init__(self):self.in_stack[]# 输入栈self.out_stack[]# 输出栈defpush(self,x):入队: 放到输入栈self.in_stack.append(x)defpop(self):出队: 从输出栈拿, 空了就倒self._transfer()returnself.out_stack.pop()defpeek(self):看队首self._transfer()returnself.out_stack[-1]defempty(self):returnnotself.in_stackandnotself.out_stackdef_transfer(self):把输入栈倒到输出栈ifnotself.out_stack:whileself.in_stack:self.out_stack.append(self.in_stack.pop())# 测试queueMyQueue()queue.push(1)queue.push(2)print(queue.peek())# 1print(queue.pop())# 1核心两个栈来回倒顺序反转两次 恢复原顺序实现FIFO 题目2滑动窗口最大值LC 239已在上面单调队列原理部分详细讲解。 题目3设计循环队列LC 622题目设计一个循环队列支持 enqueue, dequeue, front, rear, isEmpty, isFull。解法数组 头尾指针classMyCircularQueue: 循环队列: 用数组实现, 头尾指针循环移动 想象一个环形跑道: - 头指针: 指向队首 - 尾指针: 指向下一个入队位置 - 满了: 尾指针追上头指针 - 空了: 头指针追上尾指针 def__init__(self,k):self.capacityk self.queue[None]*k self.head0# 队首索引self.tail0# 下一个入队位置self.size0# 当前元素个数defenQueue(self,value):ifself.isFull():returnFalseself.queue[self.tail]value self.tail(self.tail1)%self.capacity# 循环!self.size1returnTruedefdeQueue(self):ifself.isEmpty():returnFalseself.head(self.head1)%self.capacity# 循环!self.size-1returnTruedefFront(self):return-1ifself.isEmpty()elseself.queue[self.head]defRear(self):ifself.isEmpty():return-1rear_idx(self.tail-1)%self.capacityreturnself.queue[rear_idx]defisEmpty(self):returnself.size0defisFull(self):returnself.sizeself.capacity# 测试cqMyCircularQueue(3)cq.enQueue(1)cq.enQueue(2)cq.enQueue(3)cq.enQueue(4)# 满了cq.deQueue()cq.enQueue(4)# 可以了!print(cq.Rear())# 4核心(index 1) % capacity实现循环尾指针追上head满head追上tail空。 题目4最近的请求次数LC 933题目写一个类记录最近3000毫秒内的请求次数。解法滑动窗口 队列fromcollectionsimportdequeclassRecentCounter: 思路: 队列里存请求时间, 只保留最近3000ms内的 每次ping: 1. 新时间入队 2. 把队列头部过期的时间(3000ms)弹出 3. 队列长度 最近请求次数 def__init__(self):self.requestsdeque()defping(self,t):# 1. 新请求入队self.requests.append(t)# 2. 弹出过期的whileself.requestsandself.requests[0]t-3000:self.requests.popleft()# 3. 队列长度就是答案returnlen(self.requests)# 测试counterRecentCounter()print(counter.ping(1))# 1print(counter.ping(100))# 2print(counter.ping(3001))# 3print(counter.ping(3002))# 3 (请求1过期了)核心队列天然适合滑动窗口队首是窗口左边界队尾是右边界七、本讲总结 核心要点队列的本质FIFO (先进先出)像排队买票栈 vs 队列栈LIFO(后进先出)队列FIFO(先进先出)Python deque双端队列两头操作都是O(1)单调队列维护单调性队首永远是最大值/最小值循环队列数组 头尾指针循环移动空间复用 面试高频问题问题答案队列和栈的区别?栈LIFO队列FIFO为什么用deque不用list?list.pop(0)是O(n)deque.popleft()是O(1)单调队列解决什么问题?滑动窗口最大值/最小值循环队列怎么判断满/空?用size计数或留一个空位两个栈能实现队列吗?可以输入栈输出栈倒两次顺序恢复 下节预告第5讲链表—— 指针的魔法以及反转、判环、合并等经典操作。课后作业把本讲所有代码亲手跑一遍去 LeetCode 做 LC 232, LC 239, LC 622, LC 933思考单调队列和单调栈有什么区别