第4讲：队列（Queue）

第4讲：队列（Queue）

目标：让完全没学过编程的人，也能理解队列的本质，并亲手用Python跑代码验证。

一、先讲个故事：排队买票

场景：火车站售票窗口

你去火车站买票，看到一条长长的队伍：

窗口 → 张三 → 李四 → 王五 → 赵六 ↑队首 ↑队尾

规则：

• 排队：只能站在队伍最后面 (enqueue/入队)
• 买票：只有队首的人能买票 (dequeue/出队)
• 看队首：看看谁排在第一个，但不让他走 (peek)

核心特点：先来的先买票，后来的后排着

这就是FIFO=FirstInFirstOut (先进先出)

生活中的队列

二、队列 vs 栈：本质区别

栈 (Stack) - LIFO 队列 (Queue) - FIFO 食堂餐盘 排队买票 ┌─────┐ 张三 → 李四 → 王五 │ 新 │ ← 栈顶 ↑队首 ↑队尾 ├─────┤ │ 旧 │ 出队 ←────── 入队 └─────┘ 后放的先拿 先来的先走

三、队列的基本操作

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(f"enqueue({item}):{self.items}")defdequeue(self):"""出队: 队首离开"""ifself.is_empty():print("dequeue(): 队列空了! 没人了")returnNoneitem=self.items.pop(0)# 拿走第0个(队首)print(f"dequeue():{item}离开了, 剩余{self.items}")returnitemdefpeek(self):"""看队首, 但不让他走"""ifself.is_empty():returnNonereturnself.items[0]defis_empty(self):"""队列是不是空的"""returnlen(self.items)==0defsize(self):"""队列里有多少人"""returnlen(self.items)# 测试queue=Queue()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# 创建空队列q=deque()# 入队 (右边/队尾)q.append("张三")q.append("李四")# 也可以从左边入队q.appendleft("VIP")# VIP插队到最前面!# 出队 (左边/队首)person=q.popleft()# 看队首/队尾print(f"队首:{q[0]}")print(f"队尾:{q[-1]}")# 遍历队列forpersoninq:print(person)

4.3 deque vs list 性能对比

fromcollectionsimportdequeimporttime# list: pop(0)list_data=list(range(100000))start=time.time()for_inrange(10000):list_data.pop(0)end=time.time()print(f"list pop(0) 10000次:{(end-start)*1000:.2f}ms")# deque: popleft()deque_data=deque(range(100000))start=time.time()for_inrange(10000):deque_data.popleft()end=time.time()print(f"deque popleft() 10000次:{(end-start)*1000:.2f}ms")# 结论: deque从头部删除比list快几百倍!

五、单调队列：滑动窗口最大值

5.1 问题引入

问题：给定数组，找每个大小为k的滑动窗口中的最大值。

数组: [1, 3, -1, -3, 5, 3, 6, 7], k=3 窗口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=[]q=deque()# 存索引, 对应值单调递减fori,numinenumerate(nums):# 1. 把前面比当前小的都弹出whileqandnums[q[-1]]<num:q.pop()# 2. 当前索引入队q.append(i)# 3. 检查队首是否滑出窗口ifq[0]<i-k+1:q.popleft()# 4. 窗口满了, 记录最大值(队首)ifi>=k-1:result.append(nums[q[0]])returnresult# 测试nums=[1,3,-1,-3,5,3,6,7]k=3print(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())# 测试queue=MyQueue()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.capacity=k self.queue=[None]*k self.head=0# 队首索引self.tail=0# 下一个入队位置self.size=0# 当前元素个数defenQueue(self,value):ifself.isFull():returnFalseself.queue[self.tail]=value self.tail=(self.tail+1)%self.capacity# 循环!self.size+=1returnTruedefdeQueue(self):ifself.isEmpty():returnFalseself.head=(self.head+1)%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.size==0defisFull(self):returnself.size==self.capacity# 测试cq=MyCircularQueue(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.requests=deque()defping(self,t):# 1. 新请求入队self.requests.append(t)# 2. 弹出过期的whileself.requestsandself.requests[0]<t-3000:self.requests.popleft()# 3. 队列长度就是答案returnlen(self.requests)# 测试counter=RecentCounter()print(counter.ping(1))# 1print(counter.ping(100))# 2print(counter.ping(3001))# 3print(counter.ping(3002))# 3 (请求1过期了)

核心：队列天然适合"滑动窗口"，队首是窗口左边界，队尾是右边界！

七、本讲总结

🧠 核心要点

1. 队列的本质：FIFO (先进先出)，像排队买票
2. 栈 vs 队列：栈LIFO(后进先出)，队列FIFO(先进先出)
3. Python deque：双端队列，两头操作都是O(1)
4. 单调队列：维护单调性，队首永远是最大值/最小值
5. 循环队列：数组 + 头尾指针循环移动，空间复用

📝 面试高频问题

🎯 下节预告

第5讲：链表—— 指针的魔法，以及反转、判环、合并等经典操作。

💪课后作业：

1. 把本讲所有代码亲手跑一遍
2. 去 LeetCode 做 LC 232, LC 239, LC 622, LC 933
3. 思考：单调队列和单调栈有什么区别？