别再死记硬背了！用‘双队列’思路秒解PTA银行排队题，附Python/Java双版本代码-洪萨配资

双队列调度实战：从PTA银行排队题到高并发任务处理

在编程竞赛和面试中，队列是最基础却最常考的数据结构之一。今天我们不只讲解一道PTA题目，而是深入剖析"双队列调度"这一经典模式，它不仅能解决银行窗口排队问题，还能应用于CPU任务调度、消息队列处理等真实场景。我们将通过Python和Java两种现代语言的实现，展示如何用更优雅的方式处理这类问题。

1. 理解双队列调度模型

双队列调度本质上是一种多通道差异化服务系统的抽象。在银行场景中，A窗口处理速度是B窗口的两倍，这类似于计算机系统中的优先级队列：高优先级任务获得更多计算资源。

这类问题的核心特征包括：

存在多个服务通道（窗口、队列、处理器等）
各通道服务速率不同（通常成简单整数比）
有明确的分流规则（如奇偶分流、优先级判断）
需要按完成顺序输出结果

关键识别点：当题目描述中出现"不同处理速度"、"按某种规则分流"、"按完成顺序输出"等关键词时，很可能适用双队列模型。

2. 问题分析与抽象化思考

原题描述银行有两个窗口，A窗口处理速度是B窗口的两倍。顾客根据编号奇偶分流，最终按业务完成顺序输出。我们需要将其抽象为通用模型：

输入： - N个任务/顾客 - 分流规则（如奇偶性） - 各队列处理速度比（如2:1） 处理： - 根据规则将任务分配到不同队列 - 按照速度比从各队列取出任务处理 - 某一队列空时自动切换到另一队列 输出： - 按任务完成顺序排列的结果

这种抽象使得解决方案能应用于各类相似场景，如：

多核CPU任务调度
网络请求分流处理
工厂生产线优化

3. Python实现与collections.deque妙用

Python的collections.deque是实现队列的理想选择，相比列表(list)在头部操作上有O(1)时间复杂度。下面是Python实现：

from collections import deque def bank_queue_simulation(customers): queue_a = deque() queue_b = deque() # 分流阶段 for customer in customers: if customer % 2 == 1: # 奇数 queue_a.append(customer) else: # 偶数 queue_b.append(customer) result = [] a_len, b_len = len(queue_a), len(queue_b) total = a_len + b_len # 处理阶段 for i in range(1, total + 1): if not queue_a: # A队列空 result.append(queue_b.popleft()) elif not queue_b: # B队列空 result.append(queue_a.popleft()) elif i % 3 == 0: # 每第三个从B出队 result.append(queue_b.popleft()) else: # 其他从A出队 result.append(queue_a.popleft()) return result # 示例使用 customers = [2, 1, 3, 9, 4, 11, 13, 15] print(bank_queue_simulation(customers)) # 输出: [1, 3, 2, 9, 11, 4, 13, 15]

代码亮点分析：

使用deque替代列表提升性能
清晰的两个阶段：分流→处理
通过模运算(i%3)实现2:1处理比例
队列空检查确保健壮性

4. Java实现与LinkedList选择

Java中LinkedList实现了Queue接口，是队列操作的经典选择。下面是Java实现：

import java.util.LinkedList; import java.util.Queue; public class BankQueue { public static int[] simulateBankQueue(int[] customers) { Queue<Integer> queueA = new LinkedList<>(); Queue<Integer> queueB = new LinkedList<>(); // 分流阶段 for (int customer : customers) { if (customer % 2 != 0) { queueA.add(customer); } else { queueB.add(customer); } } int total = customers.length; int[] result = new int[total]; int index = 0; // 处理阶段 for (int i = 1; i <= total; i++) { if (queueA.isEmpty()) { result[index++] = queueB.poll(); } else if (queueB.isEmpty()) { result[index++] = queueA.poll(); } else if (i % 3 == 0) { result[index++] = queueB.poll(); } else { result[index++] = queueA.poll(); } } return result; } public static void main(String[] args) { int[] customers = {2, 1, 3, 9, 4, 11, 13, 15}; int[] result = simulateBankQueue(customers); for (int num : result) { System.out.print(num + " "); } // 输出: 1 3 2 9 11 4 13 15 } }

Java实现特点：

使用Queue接口编程，LinkedList作为具体实现
poll()方法安全获取并移除队列头部
isEmpty()检查比Python的not queue更显式
数组预分配提升性能

5. 解题模板与举一反三

基于以上分析，我们可以总结出双队列调度问题的通用解题模板：

初始化阶段
- 创建两个队列
- 定义分流规则（如奇偶、优先级等）
分流阶段
- 遍历输入元素
- 根据规则将元素分配到不同队列
处理阶段
- 确定处理比例（如2:1、3:1等）
- 按比例交替从队列取出元素
- 处理队列空的情况
输出阶段
- 收集处理结果
- 按要求格式化输出

变种问题识别表：

问题特征	可能变种	解决方案调整
窗口/队列数量变化	三队列调度	增加队列，调整处理比例
处理速度比例变化	3:1而非2:1	修改模运算基数
动态分流规则	基于数值范围而非奇偶	修改分流条件判断
加入到达时间	考虑顾客到达时间间隔	引入时间变量模拟

6. 性能优化与边界情况

在实际编码中，我们需要考虑以下优化点和边界情况：

优化建议：

预分配结果数组/列表空间（如Java实现所示）
在分流阶段同时计数队列长度，避免后续反复计算
对于固定处理比例，可以用计数器替代模运算

边界情况处理：

空输入处理
所有顾客都去一个窗口的情况
顾客数量不满足完整处理周期（如最后只剩1个A窗口顾客）
超大输入规模时的内存管理

Python优化版示例：

def optimized_bank_queue(customers): queue_a, queue_b = [], [] a_count = b_count = 0 # 分流并计数 for c in customers: if c % 2: queue_a.append(c) a_count += 1 else: queue_b.append(c) b_count += 1 result = [0] * len(customers) idx = 0 a_ptr = b_ptr = 0 # 使用处理周期概念 while a_ptr < a_count or b_ptr < b_count: # 处理两个A for _ in range(2): if a_ptr < a_count: result[idx] = queue_a[a_ptr] idx += 1 a_ptr += 1 else: break # 处理一个B if b_ptr < b_count: result[idx] = queue_b[b_ptr] idx += 1 b_ptr += 1 return result

这种实现避免了模运算，使用明确的处理周期概念，可能更易理解和维护。