简介：这份数据结构期末作业以银行排队系统为主题，面向正在学习队列、准备课程设计或期末项目的高校学生，重点处理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 分钟时，一格里会挤进多个事件，顺序就乱了。

另一种是事件驱动：时钟不走路，直接跳到「下一个事件发生的时刻」。然后维护一张事件表，把「到达」和「离开」两类事件都塞进去，每次取出时间最早的那个处理。事件表用什么存，直接决定程序能撑多大规模。

我一般会选小顶堆。理由不是「显得高级」，而是当客户数拉到 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=普通 1=VIP，数值大的优先 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 比例调到 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 参数怎么调：一张对照表

这套参数不需要猜，改完就能看见趋势。下面是我实测下来比较稳的一组，直接填进去就能跑出有区分度的结果：

调参的时候一次只动一个，其余锁死。全部一起改，跑出来的数字没法归因，报告里写「加上 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 分钟之间就算对上了；差出一个数量级，多半是统计口径错了，而不是随机波动。

第三层是 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 无效」，那场面相当尴尬。希望帮到你。

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