基于链队列与优先队列的银行排队系统离散事件模拟

简介这份数据结构期末作业以银行排队系统为主题面向正在学习队列、准备课程设计或期末项目的高校学生重点处理VIP与普通用户的分级排队、按到达顺序服务以及服务窗口模拟等建模与实现问题。压缩包共9个文件、约1.03MB包含C源码、可执行程序、用户信息文本、Code::Blocks工程文件及依赖和布局配置等既能直接运行观察排队效果也便于对照工程结构梳理编译与调试流程。已有3369人学习下载作为队列与优先级调度的练习案例具有一定参考价值。读者可从中理解FIFO队列、多队列优先级处理、文件读取解析、循环与条件控制等知识点并借助完整源码、数据样例和工程组织完成类似作业、实验报告或课程复习体会多队列调度在实际服务系统中的取舍。1. 一套能跑通的银行排队系统抵得上一整个学期的数据结构复习期末周前一周某高校的课程设计题目发下来就一行字银行排队系统。看上去是个老掉牙的队列练习真动手才发现里面塞了链队列、循环队列、优先队列、离散事件模拟和一整套统计输出。这套数据结构期末作业资源做的就是把这堆东西串成一条能跑、能改参数、能出统计报表的完整链路客户按随机间隔到达窗口按空闲表分配VIP 走插队策略最后打印平均等待时长、最大队长和窗口利用率。适合正在赶作业、又不想只交一个空壳队列的人。2. 业务抽象客户排一条链窗口转一个环动手写代码之前先得把业务里的实体和数据结构对上号。银行排队系统里只有三类东西客户、窗口、事件。客户的到来时间不确定、数量不确定所以它需要一个能动态生长的容器窗口数量在开门那一刻就定死了而且会被反复占用、释放所以它需要一个容量固定、操作 O(1) 的环形结构事件则需要按时间排序取最小值。这三者选错任何一个后面统计出来的数字都会失真而且很难查。2.1 客户队列为什么用链队列窗口表为什么用循环队列客户队列的规模无法预知。上午九点和下午三点的客流量差好几倍用定长数组的话开小了溢出开大了浪费中途扩容还要整体搬移指针全部失效。链队列的入队和出队都只动两个指针节点按需malloc客户走了就free内存占用跟着实际人数走。代价是不能随机访问第 k 个客户但排队系统里根本不需要——永远只关心队头和队尾。窗口空闲表正相反。窗口数是配置项比如开 3 个窗口就是 3 个元素一辈子不会变。这种「容量固定 高频复用」的场景最适合循环队列用front和rear两个下标在数组里绕圈rear (rear 1) % MAX_WINDOW出队不需要搬移任何元素也不会产生内存碎片。一个作业里同时用到链队列和循环队列正好把教材上两章的考点都覆盖了而且不是硬凑——是场景真的需要。还有一层考虑是「先进先服务」的语义。空闲窗口表如果做成栈最后一个空出来的窗口会最先被分配结果是窗口轮流吃满又轮流闲置工位利用率会掉。循环队列天然保持「最早空出来的窗口优先被复用」和真实柜台轮转的习惯一致。2.2 事件表三种实现和一笔复杂度账时间推进有两种写法。一种是把时钟按分钟clock一步步扫过去每分钟检查一次有没有人到达、有没有人办完。这种写法直观但有个致命问题绝大部分分钟里什么都没发生扫描全是空转更麻烦的是当到达间隔小于 1 分钟时一格里会挤进多个事件顺序就乱了。另一种是事件驱动时钟不走路直接跳到「下一个事件发生的时刻」。然后维护一张事件表把「到达」和「离开」两类事件都塞进去每次取出时间最早的那个处理。事件表用什么存直接决定程序能撑多大规模。实现方式插入事件取最早事件适用规模备注无序链表O(1)O(n)事件数 100 以内代码最短答辩时不好解释按时间有序数组O(n)O(1)事件数几千插入要搬移客户一多就慢小顶堆优先队列O(log n)O(log n)万级客户无压力推荐正好用上堆排序那一章我一般会选小顶堆。理由不是「显得高级」而是当客户数拉到 1 万以上做压测时前两种实现的耗时会长到肉眼可见而堆基本是线性的。作业要求里通常只写「模拟 100 个客户」但老师追问一句「改成 1 万个要多久」有堆的版本能直接答上来。提示堆里比较的关键字必须是绝对时刻time不是间隔。见过有人存「还有多久发生」取出来还得换算一旦中间插进新事件就全错位了。2.3 结构定义与初始化字段一次性定死字段设计上少一个后面就得返工。客户至少要有编号排查问题时能对上号、到达时刻、需要办理的时长、优先级、实际开始办理时刻用来算等待。队列要带一个length因为最大队长这个指标是作业必考的每次入队出队顺手维护比事后遍历便宜得多。// sim.h —— 核心结构定义 #include stdio.h #include stdlib.h #include math.h #define MAX_WINDOW 8 // 窗口数量上限同时也是循环队列容量 #define VIP_RATIO 3 // 每服务 3 个 VIP 放 1 个普通客户 typedef struct QNode { int id; // 客户编号从 1 开始递增 int arriveTime; // 到达时刻分钟整数 int need; // 本次业务需要办理的时长 int priority; // 0普通 1VIP数值大的优先 int startTime; // 实际开始办理时刻未开始记为 -1 struct QNode *next; } QNode; typedef struct { QNode *front; // 队头出队端 QNode *rear; // 队尾入队端 int length; // 当前排队人数用于统计最大队长 } LinkQueue; void initQueue(LinkQueue *q) { q-front q-rear NULL; // 这里用不带头结点的写法省一个哨兵 q-length 0; } int isEmpty(LinkQueue *q) { return q-front NULL; } void enQueue(LinkQueue *q, QNode *node) { node-next NULL; if (q-rear NULL) { // 空队列队头队尾同时指向新结点 q-front q-rear node; } else { q-rear-next node; // 挂到队尾 q-rear node; } q-length; } QNode* deQueue(LinkQueue *q) { if (isEmpty(q)) return NULL; QNode *p q-front; q-front p-next; if (q-front NULL) q-rear NULL; // 关键删掉最后一个结点时队尾必须同步置空 q-length--; p-next NULL; return p; }这段里最容易翻车的是deQueue中那个if (q-front NULL) q-rear NULL;。漏掉它删空之后rear还指着已释放的内存下一次enQueue会往野指针上挂节点——现象是程序跑几十个客户后随机崩溃gdb一打断点就复现不了典型的玄学崩溃。窗口空闲表用循环队列容量就是窗口数不扩容// 窗口空闲表容量固定窗口数用循环队列复用 typedef struct { int data[MAX_WINDOW]; int front; // 队头下标指向当前可用窗口 int rear; // 队尾下标指向下一个空位 int count; // 当前空闲窗口数 } CirQueue; void initCir(CirQueue *c) { c-front c-rear c-count 0; } void cirPush(CirQueue *c, int windowId) { c-data[c-rear] windowId; c-rear (c-rear 1) % MAX_WINDOW; // 取模实现绕圈 c-count; } int cirPop(CirQueue *c) { if (c-count 0) return -1; // 无空闲窗口 int id c-data[c-front]; c-front (c-front 1) % MAX_WINDOW; c-count--; return id; }这里用count而不是靠front rear判空判满是为了避免「留一个空位」的经典歧义——那种写法下容量 8 的队列实际只能放 7 个窗口窗口一多就少开一个而且现象极隐蔽配置写 8 个窗口打印出来只有 7 个在工作中。加一个count字段判空判满都干净。3. 离散事件模拟时钟只跳不走结构定完接下来是整份作业的核心——主循环。它的本质是维护一个事件堆每次取出时间最早的事件把时钟直接拨到那一刻处理它可能产生的新事件再压回堆里。整个过程中时钟是跳跃的中间那些什么都没有发生的时刻根本不存在。3.1 三个时间量必须分清很多人写崩是因为把「间隔」和「时刻」混成一锅。要分清三个概念到达间隔是相邻两个客户到店的时间差它是随机变量服务时长是一个客户占用窗口多久也是随机变量事件时刻是「当前时钟 间隔」算出来的绝对值存进堆里的必须是它。到达间隔一般用指数分布生成这是排队论里的标准假设对应「客户随机独立到达」。服务时长看题目要求作业里常见的是给一个区间比如每笔业务 2 到 5 分钟用均匀分布就够如果要求更真一点可以用正态分布截断到正数区间。这两组参数决定了系统负荷率负荷率 平均到达率 ÷窗口数 × 平均服务率一旦超过 1队列会无限增长跑出来的平均等待时间是个越来越大的数字——这不是 bug是系统真的撑不住报告里要单独说一句。3.2 主循环把到达和离开两类事件处理干净主循环有两个分支逻辑对称但容易写歪到达事件负责「放人进来」离开事件负责「腾出窗口」两边都要在最后尝试调度一次。int main() { LinkQueue normalQ, vipQ; initQueue(normalQ); initQueue(vipQ); CirQueue idleWin; initCir(idleWin); int winNum 3; // 开 3 个窗口 for (int i 1; i winNum; i) cirPush(idleWin, i); seed 20240601UL; // 固定种子报告里的数字可复现 heapSize 0; int totalCust 0, finished 0, maxQLen 0, clock 0; long long sumWait 0; // 总等待分钟数 heapPush({0, expInterval(2.5), 0, 0}); // 压入第一个到达事件 while (heapSize 0) { Event e heapPop(); clock e.time; // 时钟直接跳到事件时刻不做 if (e.type 0) { // ---------- 到达事件 ---------- QNode *c (QNode*)malloc(sizeof(QNode)); c-id totalCust; c-arriveTime clock; c-need 2 (int)(uniform() * 4); // 业务时长 2~5 分钟 c-priority (totalCust % (VIP_RATIO 1) 0) ? 1 : 0; c-startTime -1; enQueue(c-priority ? vipQ : normalQ, c); int qlen normalQ.length vipQ.length; if (qlen maxQLen) maxQLen qlen; // 每次入队后刷新峰值 if (totalCust 200) { // 控制总到达人数 heapPush({0, clock expInterval(2.5), 0, 0}); } if (idleWin.count 0) { // 有空窗口就立刻调度 int w cirPop(idleWin); QNode *s pickNext(vipQ, normalQ); if (s) { s-startTime clock; sumWait clock - s-arriveTime; heapPush({1, clock s-need, w, s-id}); free(s); } else { cirPush(idleWin, w); // 没人排队窗口还回去 } } } else { // ---------- 离开事件 ---------- finished; int w e.windowId; QNode *s pickNext(vipQ, normalQ); // 窗口空出来叫下一位 if (s) { s-startTime clock; sumWait clock - s-arriveTime; heapPush({1, clock s-need, w, s-id}); free(s); } else { cirPush(idleWin, w); // 没人排队窗口转入空闲表 } } } printf(完成客户 %d 人平均等待 %.2f 分钟最大队长 %d\n, finished, (double)sumWait / finished, maxQLen); return 0; }参数上要盯住几个地方。expInterval(2.5)里的 2.5 是平均到达间隔调小就是客流变密2 (int)(uniform() * 4)生成 2 到 5 分钟的均匀服务时长改这两个数就能造出「高峰时段」「窗口减半」这类场景做对照实验。totalCust 200是终止条件客户放完就只剩离开事件堆自然清空。注意finished放在离开事件里而不是到达事件里。有人图省事在到达分支里累加完成人数结果最后一个客户的离开事件还在堆里没处理人数就已经统计完了平均等待时间分母偏大、开口时间偏小报表看着「一切正常」实际上少了最后几个人。这种错最难查因为数字没有荒谬到让人警觉。3.3 随机数不要直接用 rand()这份作业里所有「随机」都必须可复现。用rand()的问题在于不同编译器、不同平台的实现不一样同一份代码在助教机器上和你的机器上跑出两套数字报告里的表格就对不上了。自己实现一个线性同余发生器二十行不到换任何环境结果都一样。static unsigned long seed 20240601UL; // 线性同余发生器同一 seed 在任何编译器上都产生同一序列 unsigned int lcg() { seed seed * 1103515245UL 12345UL; return (unsigned int)((seed 16) 0x7FFF); // 取中间 15 位避开低位的短周期 } double uniform() { return lcg() / 32768.0; } // 映射到 [0,1) // 指数分布产生平均值为 mean 的到达间隔对应泊松到达流 int expInterval(double mean) { double u uniform(); if (u 1e-9) u 1e-9; // 防 log(0) 得到 inf int v (int)(-mean * log(u) 0.5); // 加 0.5 是四舍五入避免系统性偏低 return v 1 ? 1 : v; // 至少 1 分钟避免同一刻挤进多个到达 }参数说明1103515245和12345是 ANSI C 推荐的乘数与增量周期够用右移 16 位再取 15 位是为了丢掉低位那几位周期极短的部分否则生成的间隔会呈现明显的规律性画个直方图一眼就能看出来。u 1e-9那个兜底必须有log(0)返回负无穷强转成int是未定义行为在有些机器上直接给个负数队列长度算出来是负的。4. VIP 插队与多窗口调度优先队列怎么落单队列单窗口是教材例题真实的课程设计十有八九要求加 VIP 和多个窗口。这一章是拉开差距的地方——大部分作业卡在「多个窗口抢同一个客户」和「VIP 把普通客户饿死」两个问题上。4.1 三种 VIP 策略绝对优先、配额、加权随机策略实现方式优点风险适用场景绝对优先VIP 队列非空就永远先出代码 3 行VIP 等待几乎为 0普通客户可能等不到饥饿题目只说「VIP 优先」配额交替每服务 k 个 VIP 放 1 个普通两类客户都能推进需维护一个计数器老师要求「兼顾公平」加权随机按概率 p 从 VIP 取统计特性平滑结果不可解释报告难写有概率论要求的课题绝对优先写起来最省事但一跑就露馅把 VIP 比例调到 1:3、负荷率稍高一点普通队列的平均等待能飙到几十分钟最大队长长期卡在几十人不动。这不是系统崩了是普通客户真的排不上队。我一般用配额交替也就是代码里那个VIP_RATIO 3——先服务 3 个 VIP强制放 1 个普通客户计数器清零重来。这样 VIP 的等待时间还是明显低于普通客户但普通队列不会被彻底饿死报表上能同时看到两条曲线答辩时也好解释这个参数是怎么定的。4.2 空闲窗口表与 pickNext 的落地调度分两步先从空闲窗口表里取出一个窗口再从客户队列里挑一个人。这两步的顺序不能反——先挑人再找窗口很容易在没窗口的时候把人取出来又塞不回去得加回滚逻辑。正确顺序是先确认有空窗口再取窗口取到窗口后如果发现没客户把窗口还回去。static int vipServedBurst 0; // 连续服务了几个 VIP // 从两级队列里挑下一个客户返回 NULL 表示无人排队 QNode* pickNext(LinkQueue *vipQ, LinkQueue *normalQ) { if (!isEmpty(vipQ) (isEmpty(normalQ) || vipServedBurst VIP_RATIO)) { vipServedBurst; // 计入配额 return deQueue(vipQ); } if (!isEmpty(normalQ)) { vipServedBurst 0; // 放行一个普通客户后配额清零 return deQueue(normalQ); } return NULL; // 两个队列都空 }vipServedBurst必须是静态变量或者挂在全局状态里不能放进函数内当局部变量否则每次调用都从 0 开始等于退化成了绝对优先——这是个极其隐蔽的逻辑错误代码看起来完全正确跑起来 VIP 全程优先你还以为是配额参数没生效。多窗口的分配细节也要盯客户被分配到窗口w之后离开事件里必须带着同一个w这样窗口才能回到空闲表的正确位置。如果离开事件不记录窗口号只记一个「有窗口空了」那么空闲表里会出现重复 id 或者丢失 id表现是跑一段时间后可用窗口数越来越少最后只剩一个窗口在工作。4.3 参数怎么调一张对照表这套参数不需要猜改完就能看见趋势。下面是我实测下来比较稳的一组直接填进去就能跑出有区分度的结果参数取值改大的效果改小的效果窗口数winNum3平均等待显著下降队列迅速堆积可能不收敛平均到达间隔mean2.5 分钟客流变稀等待趋近 0负荷率上升队长暴涨服务时长区间2~5 分钟单笔业务变长占用窗口更久窗口周转快排队缓解VIP 比例1:3VIP 更多普通等待变长VIP 优势不明显区分度低VIP 配额VIP_RATIO3普通客户更容易被饿死VIP 优先体现不出来调参的时候一次只动一个其余锁死。全部一起改跑出来的数字没法归因报告里写「加上 VIP 之后平均等待变长了」也说不清是 VIP 造成的还是窗口数变了造成的。这个习惯在做任何仿真实验时都成立。5. 避坑与排查五个让结果失真的细节代码能跑通只是开始跑出来的数字对不对是另一回事。下面这几条都是我实际踩过的现象看起来都像「程序没问题是数据凑巧」实际上每一条都在悄悄改变结论。5.1 平均等待时间把没排队的人也算进分母现象平均等待时间算出来只有零点几分钟但最大队长有十几个人两个数字严重不匹配。 原因分母用了总到达人数而分子只累加了「实际开始服务」的那部分客户的等待时间。客户在模拟结束时还没轮到等待时间没进分子人却算进了分母平均值被稀释。 解决分母固定用finished也就是真正办完的人数和分子的口径严格对齐。如果一定要统计全体就得在循环结束后遍历两个队列里残留的客户把他们的「结束时刻 − 到达时刻」补进分子并在报告里注明这是「未完成客户的截至时刻等待」。两种口径都行混着用一定错。5.2 时钟用自增导致同刻多事件乱序现象偶尔出现某个客户的开始时间早于到达时间等待时间是负数。 原因把主循环写成了for (clock 0; clock END; clock)每一分钟里按固定顺序检查到达和离开。当同一分钟里既有到达又有离开时先处理哪个全看代码书写顺序就可能出现「窗口先空出来客户后到达」的倒挂。 解决改回事件驱动堆里按time排序时间相同时用一个稳定的次序规则比如「离开优先于到达」保证同刻事件的顺序确定。等待时间出现负数是一个强烈的信号看到就先查时钟推进方式别去怀疑随机数。5.3 最后一批客户的离开事件被丢掉现象窗口利用率算出来只有百分之四十几但看日志明明每个窗口从头忙到尾。 原因终止条件写成了「所有客户都已到达就跳出循环」堆里剩的离开事件没处理总忙碌时长少算了一大截。 解决终止条件必须是「事件堆为空」而不是「客户放完了」。客户放完只是不再产生新事件已排队的和正在办理的还得继续往外走。这一条改动只有一行影响的是利用率、平均队长、平均等待三个指标属于性价比最高的修复。5.4 同一时刻把两个客户分给了同一个窗口现象某个窗口的忙碌总时长超过了模拟总时长或者两个客户的服务区间完全重叠。 原因空闲窗口表在出队、入队之间漏了一次配对。常见写法是先cirPop拿窗口然后判断队列为空就return忘了把窗口cirPush回去于是这个窗口从表里消失另一种是先cirPop两次一次判断、一次分配第二个客户拿到的还是同一个 id。 解决把「取窗口—取客户—配对成功或回滚」写成一段不可分割的逻辑所有分支都要么消耗掉窗口要么还回去。调试时打开一个日志开关每次分配打印时刻 窗口号 客户号扫一眼有没有重复的窗口号就能定位。5.5 随机种子写死但代码路径不同结果对不上现象同一份代码重新编译一次结果就变了。 原因seed是全局变量但被声明成了非静态或者有多个源文件各自维护一份seed链接顺序变了初始值也跟着变。另一个来源是浮点累加顺序不同——sumWait用double累加几千次编译器开-O2之后可能重排。 解决seed加static只在一个文件里定义累加量用long long存整数分钟最后输出时再转double除。整数累加没有重排误差任何优化级别下结果都一样。这一点在需要把数字写进报告表格的时候特别重要改一次代码所有数据全变是件很崩溃的事。6. 验证与压测怎么证明这组数字不是编的跑出结果不难难的是让这组数字站得住。我通常做三层验证从便宜到贵。第一层是量纲检查。平均等待时间必须小于最大等待时间最大队长必须大于等于平均队长窗口忙碌总时长必须小于等于「窗口数 × 模拟总时长」平均利用率必须在 0 到 1 之间。这四条只要有一条不成立程序一定有逻辑错误先修再谈结论。第二层是解析解对照。把服务时长换成指数分布、窗口数设成 1就退化成了标准 M/M/1 模型平均等待时间有闭式解 Wq λ / (μ(μ − λ))。取平均到达间隔 2.5 分钟λ 0.4、平均服务时长 2 分钟μ 0.5负荷率 ρ 0.8算出来 Wq ≈ 8 分钟。模拟跑 2000 个客户平均等待落在 7 到 9 分钟之间就算对上了差出一个数量级多半是统计口径错了而不是随机波动。指标解析值M/M/1模拟可接受区间偏差过大时先查平均等待 Wq≈ 8.0 分钟7.0 ~ 9.0分母口径、终止条件平均队长 Lq≈ 3.2 人2.6 ~ 3.8队长采样时机窗口利用率 ρ0.800.76 ~ 0.84忙碌时长累加是否漏算第三层是 Little 定律自查这一层最通用换成多窗口、加 VIP 都成立平均队长 到达率 × 平均逗留时间。要用上它得先有「平均队长」这个量而代码里只记了峰值。加一个面积法统计几行就够static long long areaQ 0; // 队长对时间的积分 static int lastClock 0, lastLen 0; // 每次时钟推进时调用把这之前那段时间的队长铺进面积里 void advanceClock(int now, int curLen) { areaQ (long long)lastLen * (now - lastClock); lastClock now; lastLen curLen; } // 循环结束后平均队长 areaQ / 总时长 // 再验证 Little 定律平均队长 ≈ 到达率 × 平均逗留时间areaQ用long long是必须的1 万个客户、几万分钟、队长几十人乘出来轻松超过int上限溢出成负数之后所有统计全废而且不会有任何报错。压测环节就一件事把客户数从 200 加到 10000看耗时和内存。堆版本在普通机器上应该一秒内出结果内存占用随堆里同时存在的事件数走正常只有几十个。如果耗时随客户数平方增长说明哪里藏了线性查找如果内存一路涨说明deQueue出来的节点没有free。最后一个是可复现性验证也是最容易被忽略的同一个seed连跑三次三次输出的每一个数字必须完全一致把seed加 1 再跑平均等待应该有明显波动但仍在合理区间。前者保证报告里的表格可复现后者保证你的随机数真的在随机而不是退化成了一个固定序列。从那以后我每次交这类仿真作业都会先把seed固定、跑三遍比对输出再拿解析解卡一遍区间两个都对上才敢往报告里写数字。吃过一次亏——图表画得挺漂亮助教随手改了客户数结论直接从「VIP 有效」翻成「VIP 无效」那场面相当尴尬。希望帮到你。本文还有配套的精品资源点击获取