银行排队系统：数据结构期末作业的完整实现与调参指南

简介：这份数据结构期末作业资源面向计算机专业学生与C++初学者，围绕队列这一先进先出结构，实现带VIP优先级的银行排队模拟系统，帮助读者把课堂上的队列理论落到可运行的项目中。压缩包共9个文件、约1.03MB，以cpp源码、txt数据文件、cbp工程配置及exe可执行文件为主，另含编译中间产物与项目布局信息，Code::Blocks打开即可查看与调试。资源已有3369人学习下载，说明其作为课程作业参考具有一定认可度。读者可从中获得双队列优先级调度的完整实现思路、用户信息文件的读取与解析方式，以及STL queue容器的实际用法，并借助工程文件快速复现运行结果，对照理解入队出队、条件判断与服务流程控制等关键环节，适合作为期末作业参考或队列知识点的巩固练习。

1. 银行排队系统：一份能直接跑通的数据结构期末作业

期末周翻到这道题的人不少：用队列模拟银行窗口，要求统计客户平均等待时间、窗口利用率，还得支持多窗口和随机到达。听起来像把课本上的链队列抄一遍就完事，真动手才发现——客户到达时间怎么生成、多个窗口怎么调度、等待时间从哪个时刻开始算，每一步都能让人卡半天。这份银行排队系统作业把离散事件模拟的骨架搭好了：事件驱动的主循环、链式队列的入队出队、多窗口的忙闲判定、统计量的累加输出，全都落在可编译运行的代码里。它适合正在赶数据结构期末作业的学生，也适合想拿一个最小可用案例复习队列与模拟算法的开发者。下面按“先看懂模型、再跑通代码、最后调参数和排错”的顺序拆开讲，每一步都能照着复现。

2. 先立模型再写代码：离散事件模拟的三个核心量

很多人一上来就写Queue类，写到一半发现不知道该在什么时候推进时间，最后靠sleep或者死循环硬凑，跑出来的平均等待时间明显不对。问题不在队列实现，而在没先把模拟模型立住。银行排队本质是一个离散事件系统：时间不是连续流动的，而是从一个事件跳到下一个事件，事件只有两类——客户到达、客户离开。系统状态只在事件发生的瞬间改变，中间的时间段里状态不变。把这一点想清楚，主循环的结构就固定了。

2.1 事件、状态与统计量的定义

先把三个量定义死，后面所有代码都围绕它们转。事件用结构体或字典表示，至少包含发生时刻和类型（到达 / 离开）。状态包括当前排队队列、每个窗口是否忙碌、每个窗口当前客户的结束时刻。统计量包括累计等待时间、服务客户总数、各窗口服务人数、队列最大长度。这里有个容易被忽略的点：平均等待时间 = 累计等待时间 / 服务客户总数，分母是“已经完成服务的客户数”，不是“到达过的客户数”，否则最后几个还在排队的客户会把平均值拉低，这是期末作业里最常见的扣分点。

常见做法是用一个优先队列（最小堆）存事件，按发生时刻排序，每次弹出最早的事件处理。如果作业规模不大、到达间隔和服务时间都是整数，也可以用一个按时间递增的普通列表，插入时保持有序，实现更简单，性能足够。选哪种取决于老师有没有要求“事件驱动”这个关键词——要求了就上堆，没要求用有序列表也能过，但堆的写法更能体现对优先队列的掌握。

2.2 时间推进的两种写法与选型

时间推进有两种典型写法。第一种是事件驱动：维护事件堆，每次取最早事件，把current_time直接跳到该事件时刻。第二种是时间步进：以固定步长（比如 1 分钟）推进，每个步长检查有没有新到达、有没有窗口空闲。前者效率高、时间精度不受步长影响，是标准做法；后者写起来直观，但步长选大了会漏事件，选小了循环次数爆炸。

我一般会选事件驱动，因为银行场景里到达间隔和服务时间差异大，固定步长很容易在“某个窗口 3 分钟就服务完、另一个要 20 分钟”的情况下失真。事件驱动的核心循环长这样：取最早事件 → 把当前时间设为该事件时刻 → 如果是到达事件，客户入队并尝试分配窗口，同时生成下一个到达事件；如果是离开事件，释放窗口，若队列非空则取出队首客户开始服务，并生成该客户的离开事件。循环直到所有到达事件处理完且队列为空、窗口全闲。

2.3 随机数的可复现性：种子必须固定

模拟类作业几乎都要用随机数生成到达间隔和服务时间。这里有个血泪经验：随机种子一定要固定并在报告里写明。不固定种子，每次跑出来的平均等待时间都不一样，你调参数时根本分不清是参数起作用还是随机波动。用 Python 就random.seed(42)，用 C++ 就srand(42)或std::mt19937 gen(42)。固定之后，同一组参数跑出来的统计量完全一致，调参和写报告都省心。另外，到达间隔一般用指数分布（泊松到达），服务时间可以用均匀分布或正态分布，具体看题目有没有给定分布，没给定就用均匀分布并在报告里说明假设。

3. 链式队列的落地：入队、出队与窗口调度的衔接

模型立住之后，队列本身反而是最简单的一环。但“简单”不等于“随便写”，银行排队系统对队列有两个隐含要求：一是队列长度动态变化，二是要能快速取队首判断是否为空。链式队列（带头结点或不带头结点都行）正好满足，数组队列在容量估计不准时会溢出，期末作业里用链队列更稳妥。

3.1 链队列的节点结构与基本操作

下面是一份可直接用的 Python 链队列实现，节点存客户编号和到达时刻，这两个字段在算等待时间时都要用到。

class Node: def __init__(self, cid, arrive_time): self.cid = cid # 客户编号，用于输出和核对 self.arrive_time = arrive_time # 到达时刻，算等待时间要用 self.next = None class LinkedQueue: def __init__(self): self.head = None # 队首指针 self.tail = None # 队尾指针 self.size = 0 def enqueue(self, cid, arrive_time): node = Node(cid, arrive_time) if self.tail is None: # 空队列，头尾都指向新节点 self.head = self.tail = node else: self.tail.next = node self.tail = node self.size += 1 def dequeue(self): if self.head is None: return None node = self.head self.head = node.next if self.head is None: # 出队后队列空了，尾指针要置空 self.tail = None self.size -= 1 return node def is_empty(self): return self.head is None

这段代码的关键在dequeue里那行self.tail = None。不写这行，队列空了之后尾指针还指着已释放的节点，下次enqueue会接在野指针后面，表现为“入队成功但取不出来”，调试时非常隐蔽。C 语言版本同理，free之后要把rear置NULL。参数上，cid用自增整数即可，arrive_time传事件时刻，不要传当前循环计数，否则等待时间会算错。

3.2 多窗口调度：空闲窗口表与最短队列策略

单窗口的调度没什么可说的，出队就服务。多窗口才是这道题的分水岭。常见策略有两种：空闲窗口优先（有窗口空就分配，不管队列长短）和最短队列优先（新客户进队列最短的窗口）。银行实际场景更接近前者——客户排成一队，哪个窗口空了叫下一个，这叫单队列多服务台模型，也是大多数教材默认的模型。如果题目要求每个窗口各自排队，那就得维护多个队列，调度时选最短的那个。

单队列多服务台的实现要点是维护一个“空闲窗口列表”。到达事件发生时，如果空闲列表非空，直接分配窗口并生成离开事件；否则客户入队。离开事件发生时，释放窗口，若主队列非空则立刻出队分配，否则把窗口加回空闲列表。这里有个顺序坑：必须先判断队列再决定窗口去向，如果先加回空闲列表再检查队列，会出现“窗口刚空出来、队列里还有人，但客户还在等”的错位，统计出来的窗口利用率会偏低。

import heapq def simulate(arrival_rate, service_rate, num_windows, seed=42): import random random.seed(seed) events = [] # (时刻, 类型, 客户编号) heapq.heappush(events, (0.0, 'arrive', 0)) queue = LinkedQueue() free_windows = list(range(num_windows)) busy_until = [0.0] * num_windows total_wait = 0.0 served = 0 cid = 0 current_time = 0.0 while events: current_time, etype, cid_evt = heapq.heappop(events) if etype == 'arrive': cid += 1 if free_windows: w = free_windows.pop(0) st = random.expovariate(service_rate) busy_until[w] = current_time + st heapq.heappush(events, (busy_until[w], 'leave', cid)) else: queue.enqueue(cid, current_time) # 生成下一个到达事件 gap = random.expovariate(arrival_rate) heapq.heappush(events, (current_time + gap, 'arrive', cid + 1)) else: # leave served += 1 w = busy_until.index(current_time) # 找到刚空闲的窗口 if not queue.is_empty(): node = queue.dequeue() total_wait += current_time - node.arrive_time st = random.expovariate(service_rate) busy_until[w] = current_time + st heapq.heappush(events, (busy_until[w], 'leave', node.cid)) else: free_windows.append(w) return total_wait / served if served else 0, served

这段代码里busy_until.index(current_time)是个简化写法，窗口数少时没问题，窗口多了建议在事件里直接带上窗口编号，避免浮点相等比较的隐患。arrival_rate和service_rate是单位时间内的到达率和服务率，调大arrival_rate会明显看到平均等待时间上升，这就是后面调参的抓手。

3.3 统计量的累加时机

统计量在哪儿累加，直接决定结果对不对。等待时间在客户开始服务的那一刻累加，用“当前时刻减到达时刻”；服务人数在离开事件里加一；窗口利用率用“忙碌总时长 / (窗口数 × 总模拟时长)”算，忙碌总时长可以在每次分配窗口时累加服务时长。最容易错的是把等待时间在入队时就算——那时候客户还没等到，算出来是零。另一个坑是总模拟时长取最后一个事件时刻，如果最后一个事件是到达，队列里可能还有没服务完的客户，报告里要说明“统计截止到所有到达客户处理完毕”，别让老师以为你漏算了。

4. 参数怎么设：到达率、服务率与窗口数的联动

代码跑通只是及格线，期末作业想拿高分，得能说清楚参数变化对结果的影响。这一章给三组可复现的实验配置，照着跑一遍，报告里的分析就有数据支撑，而不是空谈“等待时间会变长”。

4.1 三组基准参数与预期趋势

判断拥堵有个粗略指标：系统负载 ρ = λ / (c × μ)。ρ 接近 1 时队列会剧烈波动，超过 1 队列理论上无限增长。A 组 ρ ≈ 0.83，B 组 ρ ≈ 1.33（已经过载），C 组 ρ ≈ 0.67。跑 B 组时如果模拟时长不够，平均等待时间会一直涨，这不是代码错，是系统本身不稳定，报告里要指出这一点。调参时把seed固定，只改一个参数，才能看出单一变量的影响。

4.2 用循环批量跑参数扫描

手动改参数跑十几次太慢，写个外层循环批量跑，把结果存成表格直接贴进报告。

results = [] for lam in [0.3, 0.5, 0.8, 1.0]: for c in [1, 2, 3, 4]: avg_wait, served = simulate(lam, 0.3, c, seed=42) results.append((lam, c, round(avg_wait, 2), served)) for r in results: print(f"lambda={r[0]}, windows={r[1]}, avg_wait={r[2]}, served={r[3]}")

跑完会发现 λ=1.0、c=1 时平均等待时间大得离谱，这是 ρ≈3.3 的必然结果，正好用来在报告里解释“为什么银行高峰期要开满窗口”。注意simulate里每次调用都重新seed(42)，保证不同参数组之间的随机序列一致，对比才公平。如果想让模拟更接近真实，可以把模拟时长拉长（比如处理 10000 个客户），样本大了统计量才稳定。

4.3 窗口利用率与“开几个窗口划算”

窗口利用率 = 忙碌时长 / 总时长。c=4 时利用率往往掉到 0.5 以下，意味着两个窗口大半时间在闲着。报告里可以加一段讨论：从排队论角度，利用率 0.7～0.85 是比较经济的区间，太低浪费人力，太高客户等待爆炸。这段分析不用复杂公式，用你跑出来的表格数据说话就行，老师看的是你有没有把数据和结论对上，而不是背公式。

5. 避坑与排查：五个让作业翻车的细节

代码能跑不等于结果可信，下面五条是这类作业里反复出现的翻车点，每条都按“现象 → 原因 → 解决”给出来，交作业前逐条对一遍。

现象一：平均等待时间算出来是 0 或者负数。原因通常是等待时间用了“离开时刻减到达时刻”，把服务时间也算进去了，或者入队时就把等待时间记成当前时刻减到达时刻（此时差值为零）。解决：等待时间只在客户开始服务时计算，公式是start_service_time - arrive_time，服务时间单独统计。

现象二：程序跑着跑着不动了，事件堆为空但队列里还有人。原因是离开事件生成时用了错误的客户编号，或者窗口释放后没有检查队列就结束了循环。解决：主循环的终止条件写成“事件堆为空且队列为空且所有窗口空闲”，并在每次离开事件里强制检查队列，别依赖事件堆自然耗尽。

现象三：多窗口时同一个窗口被分配了两次。原因是空闲窗口列表用了引用或没及时移除，pop之后又append回去。解决：分配窗口时立刻从空闲列表删除，释放时再追加，中间不要有别的路径修改这个列表；调试时打印每次分配和释放的窗口编号，一眼就能看出重复。

现象四：换台机器跑结果就变了。原因是随机种子没固定，或者用了系统时间做种子。解决：种子写死成常量，并在报告里注明；如果用了多线程（一般作业不会），还要注意随机数生成器的线程安全问题。

现象五：窗口利用率超过 100%。原因是忙碌时长重复累加，比如到达和离开事件里都加了服务时长。解决：服务时长只在分配窗口时累加一次，离开事件只负责释放，不碰统计量。这类错误在数字上很显眼，跑完先扫一眼利用率有没有大于 1，能省很多排查时间。

6. 进阶验证：用解析解给模拟结果做交叉校验

模拟跑出来的数字，怎么证明它是对的？最硬的办法是拿排队论的解析解对一遍。单队列多服务台的 M/M/c 模型有现成公式，虽然推导不用你写，但把模拟值和理论值放一起对比，报告的可信度立刻不一样。具体做法：固定 λ、μ、c，跑足够长的模拟（比如 50000 个客户），记录平均等待时间，再按 M/M/c 的等待时间公式算一个理论值，两者误差在 10% 以内就算合理。误差大就回头查统计量的累加时机，十有八九是等待时间或服务人数算错了。

我一般还会做一个“极端用例”验证：令服务率远大于到达率（μ=10, λ=0.1, c=1），此时几乎不该排队，平均等待时间应接近 0；再令 λ 略小于 μ 且 c=1，等待时间应显著大于 0 但不发散。这两个用例能快速暴露事件顺序和窗口释放的逻辑错误，比盯着代码看有效得多。另一个技巧是把客户编号和到达/离开时刻打印成日志，取前 20 条人工核对一遍时间线，事件驱动模拟的 bug 基本都藏在前几个事件里。

血泪经验是：每次改完调度逻辑，先跑极端用例，再跑基准参数，最后才跑参数扫描。顺序反了，你会在一堆波动的数字里怀疑人生。从那以后我每次交这类模拟作业前，都强制走一遍“极端用例 → 固定种子基准 → 解析解对比”三步，报告里的每个数字都能追溯到某次具体运行。希望帮到你。

本文还有配套的精品资源，点击获取