银行排队系统数据结构期末作业：链队列与优先队列实战

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

1. 银行排队系统：一份能直接交的数据结构期末作业该长什么样

期末周最怕的不是不会写代码，而是打开题目一看——“银行排队系统”，脑子里只有“队列”两个字，剩下的全靠编。真到答辩现场，导师问一句“你这套系统为什么用链队列不用循环队列”，答不上来，前面写的几百行就白搭了。这份数据结构期末作业要解决的就是这件事：把银行排队系统从一句题目要求，拆成一套有需求、有选型、有模块、有验收标准的完整方案。它适合正在赶期末作业的学生，也适合想拿一个经典案例练手队列、优先队列和离散事件模拟的开发者。下面按“需求怎么立、结构怎么搭、代码怎么落、坑怎么避、最后怎么验收”一路走完，你照着改参数就能交。

2. 需求与选型：先把业务场景翻译成数据结构问题

2.1 银行排队到底在模拟什么

很多人一上来就写Queue，写完发现根本不知道要输出什么。问题出在没把业务翻译成计算模型。银行排队系统的本质是一个离散事件模拟：时间不是连续的，而是一个个“事件”推进的——客户到达是一个事件，窗口完成服务是一个事件，每个事件发生时系统状态跳变一次。

把场景拆开，核心要素只有四类：

• 客户：到达时刻、需要办理的业务类型、预计服务时长；
• 窗口：数量、当前是否空闲、正在服务的客户；
• 队列：等待中的客户按什么规则排队；
• 时钟：当前模拟到第几分钟，下一个事件在什么时候发生。

这四类要素决定了你需要的数据结构：客户和窗口用结构体/类表示，队列用链式或顺序存储，时钟就是一个不断取最小值的变量。想清楚这一层，后面写代码才不会东拼西凑。

2.2 为什么是链队列而不是循环队列

这是答辩最常被问的一题，必须能答。银行排队有两个特点：队列长度不可预知，高峰期可能排几十人，闲时可能一个人都没有；频繁出队入队，每个客户到达就入队，窗口空闲就出队。

循环队列容量固定，写死MAXSIZE = 100，一旦模拟参数调大（比如把到达率调高、模拟 8 小时），队列溢出直接翻车。链队列按需申请节点，长度理论上无上限，出队入队都是 O(1)，正好匹配“长度动态、操作频繁”的场景。代价是每个节点多一个指针的空间开销，以及需要手动释放内存——这个代价在作业规模下完全可以接受。

提示：如果导师要求必须用顺序存储，那就把循环队列容量设成“理论最大排队人数”并加溢出保护，同时在报告里说明容量估算依据，别默默写死一个数。

2.3 普通队列不够用：优先队列与多窗口调度

真实银行有 VIP 客户、对公业务、普通个人业务，优先级不同。如果全部先进先出，VIP 客户排在普通客户后面，模拟结果就失真了。所以队列层要支持两种模式：

• 普通模式：单一链队列，严格 FIFO；
• 优先级模式：按业务类型分多条队列，或用一个带优先级的堆。

我一般会做成“多队列 + 调度策略”的结构：每个业务类型一条链队列，窗口空闲时按优先级从高到低扫描取人。这样既保留了队列的 FIFO 语义，又实现了优先级，比直接上堆更贴近银行业务，报告里也好解释。

2.4 技术栈与工程结构

作业规模不需要复杂框架，C/C++ 或 Python 都行。用 C 语言能体现指针和内存管理，答辩时更能说明“我真的自己实现了队列”；用 Python 则把精力放在模拟逻辑上。下面以 C 语言为主线，Python 版本在关键处给对照。

工程结构建议按职责分文件，别全塞一个main.c：

bank_queue/ ├── main.c # 入口：读参数、跑模拟、输出统计 ├── queue.h # 链队列结构与操作声明 ├── queue.c # 链队列实现（入队/出队/判空/销毁） ├── customer.h # 客户与窗口结构体定义 ├── simulate.c # 离散事件模拟核心 └── simulate.h

分文件的好处是答辩时能指着说“队列是独立模块，可以单独测试”，这比一坨代码有说服力得多。

3. 总体设计：链队列、事件驱动与统计输出的三层结构

3.1 数据模型设计：客户、窗口与队列节点

先把结构体定清楚，后面所有逻辑都围绕它们转。

// customer.h typedef enum { NORMAL = 0, VIP = 1, CORPORATE = 2 } BizType; typedef struct { int id; // 客户编号，用于输出追踪 int arriveTime; // 到达时刻（分钟） int serviceTime; // 预计服务时长（分钟） BizType type; // 业务类型，决定优先级 } Customer; typedef struct { int id; // 窗口编号 int freeTime; // 窗口变为空闲的时刻 int servedCount; // 已服务人数 int totalBusy; // 累计忙碌时长 } Window;

freeTime是关键设计：它让“窗口什么时候空出来”变成一个可以直接比较的整数，模拟时不用维护复杂的窗口状态机。arriveTime和serviceTime都用分钟为单位，避免浮点误差。

队列节点则把客户包一层：

// queue.h typedef struct QNode { Customer data; struct QNode *next; } QNode; typedef struct { QNode *front; // 队头，出队 QNode *rear; // 队尾，入队 int length; // 当前排队人数 } LinkQueue;

带头尾指针是链队列的标准做法：入队操作rear->next = node; rear = node;，出队操作front = front->next;，两者都是 O(1)。length字段让统计排队人数不用遍历，答辩时被问“怎么快速得到队长”就能答上。

3.2 队列模块实现：入队、出队与销毁

队列操作要写得干净，每个函数只做一件事，并且处理边界。

// queue.c void InitQueue(LinkQueue *q) { q->front = q->rear = NULL; q->length = 0; } int EnQueue(LinkQueue *q, Customer c) { QNode *node = (QNode *)malloc(sizeof(QNode)); if (!node) return 0; // 内存不足，返回失败 node->data = c; node->next = NULL; if (q->rear == NULL) { // 空队列，头尾都指向新节点 q->front = q->rear = node; } else { q->rear->next = node; q->rear = node; } q->length++; return 1; } int DeQueue(LinkQueue *q, Customer *out) { if (q->front == NULL) return 0; // 空队列 QNode *tmp = q->front; *out = tmp->data; q->front = tmp->next; if (q->front == NULL) q->rear = NULL; // 出队后为空，尾指针复位 free(tmp); q->length--; return 1; } void DestroyQueue(LinkQueue *q) { Customer tmp; while (DeQueue(q, &tmp)) { } // 逐个释放，避免内存泄漏 }

这里有两个容易忽略的点：出队后如果队列变空，必须把rear置 NULL，否则下次入队会走到错误分支；销毁函数必须存在，模拟结束后调用，否则长时间模拟会泄漏内存。答辩时主动提这两点，导师会认为你考虑过边界。

3.3 模拟引擎：事件驱动的主循环

模拟核心是一个循环：每次找出“下一个事件”，推进时钟，处理事件。事件只有两类——客户到达、窗口完成服务。

// simulate.c 核心逻辑（简化） void RunSimulation(int totalCustomers, int windowCount, double arriveRate, LinkQueue queues[]) { Window windows[MAX_WINDOW]; for (int i = 0; i < windowCount; i++) { windows[i].id = i + 1; windows[i].freeTime = 0; windows[i].servedCount = 0; windows[i].totalBusy = 0; } int nextArrive = 0; // 下一个客户到达时刻 int served = 0; // 已完成服务的客户数 while (served < totalCustomers) { // 1. 找出最早空闲的窗口 int w = 0; for (int i = 1; i < windowCount; i++) if (windows[i].freeTime < windows[w].freeTime) w = i; // 2. 若下一个客户在窗口空闲前到达，先入队 if (nextArrive <= windows[w].freeTime && nextArrive < totalCustomers) { Customer c = GenerateCustomer(nextArrive, arriveRate); EnQueue(&queues[c.type], c); nextArrive += NextInterval(arriveRate); // 指数分布间隔 continue; } // 3. 窗口空闲，按优先级取客户 Customer c; if (!PickByPriority(queues, &c)) { // 所有队列为空，时钟跳到下一个到达时刻 if (nextArrive >= totalCustomers) break; continue; } // 4. 服务该客户，更新窗口状态 windows[w].freeTime += c.serviceTime; windows[w].servedCount++; windows[w].totalBusy += c.serviceTime; served++; } PrintStatistics(windows, windowCount, totalCustomers); }

这段代码的设计说明：主循环每轮只处理一个“最小时间”的事件，保证模拟顺序正确；PickByPriority按 VIP、对公、普通的顺序扫描队列，实现优先级调度；NextInterval用指数分布生成到达间隔，比固定间隔更接近真实客流。参数arriveRate控制客流强度，调大它就能模拟高峰期，这是验收时演示系统行为的好抓手。

3.4 统计输出：让结果能写进报告

模拟跑完必须输出可量化的指标，否则报告里没东西写。至少输出：

这些指标直接对应报告里的“实验结果与分析”章节，表格一贴，结论自然出来：比如“窗口从 2 个增加到 3 个，平均等待时间下降 40%”，这就是有数据支撑的分析，比空谈“系统运行良好”强得多。

4. 关键实现细节：优先级调度、随机分布与内存管理

4.1 优先级调度的两种实现与取舍

优先级调度有两种常见写法。第一种是多队列扫描：每个业务类型一条链队列，窗口空闲时从高优先级到低优先级依次检查，取第一条非空队列的队头。实现简单，优先级层次固定，适合作业规模。

第二种是优先队列（堆）：所有客户进一个堆，按优先级和时间排序。插入和取出都是 O(log n)，但需要自己实现堆的上浮下沉，代码量翻倍，而且 FIFO 语义要靠“同优先级按到达时间排序”来补，容易出错。

我的建议是作业用多队列扫描，报告里加一段“为什么不用堆”的讨论：本场景优先级类别少（3 类），多队列扫描的最坏复杂度是 O(类别数)，实际就是常数级，比堆更直观。这样既展示了选型思考，又不用写一堆堆代码。

// 按优先级取客户：VIP > 对公 > 普通 int PickByPriority(LinkQueue queues[], Customer *out) { BizType order[3] = { VIP, CORPORATE, NORMAL }; for (int i = 0; i < 3; i++) { if (DeQueue(&queues[order[i]], out)) return 1; } return 0; // 全部为空 }

注意order数组把优先级顺序显式写出来，改优先级只改这一行，不用动逻辑，这是可维护性的体现。

4.2 随机到达与服务时长的分布选择

如果所有客户固定每 2 分钟到、固定服务 3 分钟，模拟结果毫无意义。真实客流近似泊松到达，到达间隔服从指数分布；服务时长可以用均匀分布或正态分布近似。

C 语言里用rand()生成均匀分布，再用逆变换法转成指数分布：

#include <stdlib.h> #include <math.h> // 生成均值为 mean 的指数分布随机数（到达间隔） double ExpInterval(double mean) { double u = (double)rand() / RAND_MAX; // (0,1) if (u <= 0.0) u = 1e-6; // 防止 log(0) return -mean * log(u); }

参数mean就是平均到达间隔，比如平均每 2 分钟来一个客户，mean = 2.0。服务时长可以用mean + (rand()%5 - 2)做简单扰动，或者用正态分布。报告里要说明分布假设的依据，这是“实验设计”的一部分，导师很看重。

注意：rand()前要调用srand(time(NULL))播种，否则每次运行结果一样，演示时会被认为“数据是编的”。但做对比实验时又要固定种子，保证不同窗口数下客流一致，这个细节写进报告能加分。

4.3 内存管理与边界条件

链队列最大的坑是内存泄漏和野指针。三个地方必须检查：

• malloc返回值判空，失败时要有降级处理（比如直接结束模拟并报错）；
• 出队后队列为空时rear复位为 NULL；
• 模拟结束对所有队列调用DestroyQueue。

另外，窗口数不能超过MAX_WINDOW，客户数不能为负，到达率为 0 会导致除零或死循环。这些边界在main里做参数校验，比在模拟循环里到处判断更清晰。

// main.c 参数校验片段 if (windowCount <= 0 || windowCount > MAX_WINDOW) { printf("窗口数必须在 1~%d 之间\n", MAX_WINDOW); return 1; } if (arriveRate <= 0.0) { printf("到达率必须为正数\n"); return 1; }

4.4 用 Python 快速验证逻辑

如果时间紧，可以先用 Python 把模拟逻辑跑通，再翻译成 C。Python 的queue.Queue或collections.deque能快速搭原型，验证统计指标是否合理，避免在 C 里调半天发现逻辑本身错了。

from collections import deque import random def simulate(total, windows, mean_arrive): queues = {0: deque(), 1: deque(), 2: deque()} # 0普通 1VIP 2对公 free = [0] * windows waits = [] t = 0 for cid in range(total): t += random.expovariate(1 / mean_arrive) # 简化：先找最早空闲窗口，再决定是否等待 w = free.index(min(free)) start = max(t, free[w]) waits.append(start - t) free[w] = start + random.randint(2, 6) return sum(waits) / len(waits)

原型跑通后，把deque换成自己写的链队列，逻辑一一对应，翻译成本很低。这也是我带项目时的习惯：先用最省事的方式验证算法，再上正式实现。

5. 避坑与排查：这类作业最容易翻车的五个点

5.1 模拟时钟倒退或死循环

现象：程序跑不完，或者输出的等待时间出现负数。

原因：事件推进逻辑写错，比如窗口空闲时间没有正确累加，或者“下一个到达时刻”没有更新，导致主循环一直在同一时刻打转。

解决：在主循环里打印每次事件的时间和类型（调试开关控制），观察时钟是否单调递增。确保每次处理事件后，要么nextArrive前进，要么某个窗口的freeTime前进，二者必居其一。

5.2 队列长度统计与实际不符

现象：报告里最大排队长度是 5，但输出日志里明明排了 10 个人。

原因：length字段只在入队时加、出队时忘了减，或者出队后队列为空时没有复位rear，导致后续入队接到已释放节点上。

解决：把length的增减和front/rear的修改放在同一个函数里，出队后立即判断空队列并复位尾指针。写一个单元测试：连续入队 3 个、出队 3 个，检查length是否为 0、front和rear是否都为 NULL。

5.3 优先级导致低优先级客户“饿死”

现象：VIP 客户源源不断时，普通客户平均等待时间异常大，甚至模拟结束都没被服务。

原因：严格优先级调度下，高优先级队列非空就永远不取低优先级，这是策略本身的特性，不是 bug。

解决：在报告里明确说明这是“绝对优先级”策略及其代价，然后给出改进方案：比如“时间片轮转 + 优先级”或“等待超时提升优先级”。作业里不一定要实现改进版，但能讨论清楚就是加分项。

5.4 随机数导致结果不可复现

现象：同一组参数跑两次，平均等待时间差很多，报告里的数据对不上。

原因：每次运行都用time(NULL)播种，客流序列不同。

解决：做对比实验时固定种子（如srand(42)），并在报告里注明“固定随机种子以保证可复现”。演示时可以换种子展示系统的鲁棒性，但报告数据必须来自固定种子。

5.5 内存泄漏在长时间模拟中暴露

现象：模拟 10 万客户时程序变慢甚至崩溃。

原因：出队节点没有free，或者异常分支提前return跳过了销毁。

解决：所有出队路径统一走DeQueue，销毁逻辑集中在DestroyQueue；用valgrind（Linux）或编译器的内存检查工具跑一遍小规模模拟，确认无泄漏再放大参数。

6. 验收与答辩：用三组对比实验讲清你的设计

验收不是“能跑就行”，而是要让导师看到你的设计决策有依据。我一般会准备三组对比实验，每组只改一个变量，结果做成表格。

实验一：窗口数对等待时间的影响。固定客户数 200、到达率不变，窗口数取 1、2、3、4，记录平均等待时间和窗口利用率。预期结论：窗口增加，等待下降但利用率也下降，存在性价比拐点。这组实验证明你理解“资源与效率的权衡”。

实验二：优先级策略的影响。同一组客流，分别跑“纯 FIFO”和“VIP 优先”，对比普通客户和 VIP 客户的平均等待。预期结论：VIP 优先让 VIP 等待大幅下降，普通客户等待上升。这组实验证明优先级调度确实生效，且你能解释代价。

实验三：到达率对最大排队长度的影响。固定窗口数，到达率从低到高取三档，记录最大排队长度。预期结论：到达率超过服务能力后，排队长度快速增长。这组实验展示系统在压力下的行为，也顺带验证了链队列不会溢出。

答辩时的讲述顺序建议：先讲需求（银行为什么要模拟排队），再讲选型（为什么链队列、为什么多队列优先级），然后现场跑一组实验展示输出，最后主动说一个已知局限（比如绝对优先级的饿死问题）和改进方向。主动暴露局限比被问出来强得多，导师会认为你对自己的方案有清醒认识。

代码演示时，提前把参数校验和异常输入跑一遍：窗口数输 0、到达率输负数，展示程序给出友好提示而不是崩溃。这个细节很多同学忽略，但它是“工程完整性”的直接体现。

从那以后我每次带课程设计，都要求学生先把三组对比实验的表格模板画出来，再倒推需要哪些统计指标、代码里要埋哪些计数器——先想清楚怎么验收，写代码时就不会漏掉关键输出。希望帮到你。

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