简介这是一份大二下数据结构课程设计“银行排队系统”的完整作业包面向计算机相关专业学生核心用栈与队列模拟银行服务流程重点实现VIP客户优先插入与普通客户先到先得。压缩包共8个文件约334KB包含C源码main.cpp、数据信息xinxi.txt、Code::Blocks工程文件shujujiegou.cbp及layout/depend辅助文件另附可直接运行的exe便于对照代码查看运行效果。源码中清晰体现栈的后进先出与队列的先进先出并涉及多窗口分配、实时队列显示和动态调整策略适合作为数据结构课程设计参考或复习栈队列应用。目前已有2865人浏览学习适合需要完成类似选题或想加深理解的同学。1. 数据结构课设里的银行排队系统栈不是用来排队的“大二下数据结构作业银行排队系统”乍看是个常规练习真做起来才发现它把全学期最难区分的两个数据结构——栈和队列——放进了同一个业务场景。排队叫号天然是队列的活先取号先服务可项目标题里偏偏带着“栈”于是第一批动手的同学全把等待区写成了栈后进先出网点当场乱套。正确分工是队列承载取号和叫号栈负责过号回溯与叫号历史回放二者通过同一个客户数据节点串起来。这篇方案用 C 语言给出一套最小可运行代码从结构体定义、多窗口调度到过号重排最后落到实验报告的参数验证。适合正在赶作业的大二学生也适合想用一个具体例子彻底分清栈和队列的初学者。2. 栈与队列的分工先看懂银行叫号机的业务约束2.1 取号、叫号、过号排队系统的三个基本动作先别急着写代码。作业翻车通常不是因为代码写不出来而是业务模型没拆清楚就动手。银行排队系统从用户视角看只有三个动作进门取号、听到叫号去窗口、过号之后重新排队。从系统视角看取号是把一个客户挂到等待区末尾叫号是从等待区头部取出一个客户并分配到空闲窗口过号则是把叫到却没来的人重新调度。三个动作的数据结构约束各不相同第一步就是把这些动作拆干净。等待区最核心的约束是公平性。客户按取号顺序被叫到窗口先到先服务对应数据结构的 FIFOFirst In First Out。满足这个要求的只有队列入队发生在队尾rear出队发生在队首front。谁把等待区写成栈谁就会得到“后进门先办事”的系统这在真实的银行场景里完全不可接受。作业答辩时老师最爱问“为什么等待区不能用栈”回答就是这一句业务约束决定数据结构而不是反过来。那“栈”到底在作业里干什么很多人卡在这个点上。常见做法是把它用在两个地方一是记录叫号历史支撑过号回溯和调试时的现场回放二是配合“合法出栈序列判定”这个经典考点验证一组叫号顺序能否由栈调度产生。前面是实际功能后面是课程考核点两个功能共用同一个栈结构不用另写第二套。业务模型拆到这里后续代码就顺了。队列负责“等待区”这个空间容器栈负责“时间上的后悔药”二者通过同一个 Customer 指针串联并不冲突。这也是这个作业最核心的架构判断先定数据结构再写业务动作。2.2 栈的三个正确定位事件回溯、撤销重排、出栈序列验证先说结论栈在这个作业里不是排队的容器是后悔药。三个用途对应三份代码逻辑。第一是事件回溯。每叫到一个号就把这个客户的信息压入叫号栈需要排查某个时间段窗口到底叫了哪些号把栈从顶往底一格格弹出来就能倒序还原现场。真实系统里这叫 backtrace 栈回溯操作日志排查里非常常见原理完全一致栈天然支持回到最近一次操作。第二是过号重排的撤销语义。客户被叫号却没出现系统判定他过号。如果直接把他重新塞回等待区队尾他在队列里会被后来者不断挤到后面形成饥饿更合理的做法是把状态改成“过号”记录压栈等正常客户服务完一轮后再按后过号先处理的顺序补叫。这个顺序是 LIFOLast In First Out只有栈能表达。第三是合法出栈序列判定。这是数据结构课必考点也是实验报告里值得写一页的内容给定一组到达顺序比如按 1、2、3、4 取号问叫号顺序 3、1、4、2 能不能由同一个栈产生。判定算法是维护一个入栈序列指针和一个栈依次把元素压栈每当栈顶等于出栈序列的当前元素就弹出全部走完后出栈序列也走完说明合法否则不合法。这个算法放银行场景里可以用来验证一条叫号链路是不是真的按“栈调度”产生防止自己把队列实现写成栈实现还没发现。栈的基本操作只有四个push 压入、pop 弹出、top 取栈顶、is_empty 判空。用带头节点的单链表实现这四件事足够直接结构体可以和后面的回溯栈完全复用。有些同学图省事直接开个数组模拟栈作业里完全够用但后续要扩展成过号多轮重排链表栈更好改不用关心扩容也不存在栈底没人管的边界问题。2.3 四种队列选型对比为什么多窗口场景选链队列等待区队列有四种常见实现方式先将优劣摊开来看实现方式实现难度空/满判定过号重排扩展多窗口适配顺序队列低头尾指针判空简单需搬移数据代价高一般循环队列中留一格或用计数器数据搬移少较好链队列中frontNULL 即空插入删除都是 O(1)好双端队列高依赖自己的标志位两端插删都灵活好但复杂我一般给作业选链队列理由有三。第一空判断只需 q-front NULL不用像循环队列那样纠结“少留一格”是不是浪费修改 bug 的复杂度低。第二过号重排时要把客户从叫号栈弹出并插回等待区链队列入队天然是 O(1)顺序队列得整体搬移一次模拟数据量一旦上来差别立竿见影。第三多窗口调度时一个队列要同时面对多个空闲窗口从队首取人链队列入队和出队互不干扰front 和 rear 各自独立答辩画图也好讲。顺序队列只有在“确定队列永远不会满”的场景才够用但银行等待区长度是随机的固定数组要么浪费内存要么溢出。循环队列比顺序队列强但实现时要在“牺牲一个存储单元”和“额外计数器”之间做选择作业时间紧的时候容易在那里翻车。双端队列对过号重排确实友好可以保持队首队尾双向操作但 C 语言要实现双端队列指针操作量直接翻倍对课程作业来说有点杀鸡用牛刀。3. C 语言落地最小可跑的银行排队系统队列调度与栈回溯3.1 客户、队列、窗口的结构体定义与初始化不给完整工程文件先给一套能直接抄进 main.c 的结构体骨架。结构体的设计决定后面所有代码的写法这一步省了后面全是补丁。// 客户结构体一次排队服务的最小数据单元 typedef struct Customer { int id; // 取号编号从 1 开始递增 int arrive_time; // 取号时刻分钟为单位 int service_time; // 预计服务时长分钟 int state; // 0-等待中 1-已叫号 2-过号 3-服务完成 } Customer; // 链式队列节点等待区的基本存储单元 typedef struct QueueNode { Customer *data; // 指向客户数据 struct QueueNode *next; // 后继指针 } QueueNode; // 链式队列front 负责出队rear 负责入队length 记录排队人数 typedef struct { QueueNode *front; QueueNode *rear; int length; } LinkedQueue; // 窗口结构体模拟一个银行柜员的忙闲状态 typedef struct { int id; // 窗口编号 int busy_until; // 该窗口下一次空闲的时刻 int total_served; // 累计服务客户数 } Window;Customer 里的 state 字段别省过号回溯、状态流转、实验报告里的统计都靠它arrive_time 要和主循环的时间变量对齐否则算平均等待时长全是负数。Window 里的 busy_until 最关键它表示窗口在哪个时刻恢复空闲主循环每分钟检查它就能决定要不要从等待区取人。初始化函数的写法很固定链队列的 front 和 rear 初始都指向 NULLlength 置 0窗口数组在 main 里循环初始化即可。void initQueue(LinkedQueue *q) { q-front NULL; q-rear NULL; q-length 0; } void initWindows(Window *windows, int count) { for (int i 0; i count; i) { windows[i].id i 1; windows[i].busy_until 0; windows[i].total_served 0; } }初始化是初学者第一个翻车点不把 front 置成 NULL 就直接 enqueue后面 q-front NULL 的判断读到野指针。C 语言里 malloc 出来的局部指针不会自动归零写链式结构要养成显式把指针字段置 NULL 的习惯这个习惯在后面的栈代码里同样重要。3.2 入队与出队取号和叫号到底谁动 rear、谁动 front链队列两个核心函数enqueue 对应“取号”dequeue 对应“叫号”。代码不长但边界条件必须成对看。// 取号把客户挂到队尾 void enqueue(LinkedQueue *q, Customer *c) { QueueNode *node (QueueNode *)malloc(sizeof(QueueNode)); node-data c; node-next NULL; if (q-rear NULL) { q-front node; // 首个节点front 和 rear 同时指向它 q-rear node; } else { q-rear-next node; // 原队尾的 next 指向新节点 q-rear node; // 队尾指针后移 } q-length; } // 叫号从队首取客户 Customer *dequeue(LinkedQueue *q) { if (q-front NULL) return NULL; QueueNode *tmp q-front; Customer *c tmp-data; q-front q-front-next; if (q-front NULL) { q-rear NULL; // 队列变空rear 必须复位 } free(tmp); q-length--; return c; }两个函数要放在一起读。enqueue 第一次插入时 front 和 rear 必须同时指向新节点否则后续 dequeue 拿到一个空队首dequeue 弹出最后一个节点后必须把 rear 置成 NULL否则 rear 变成悬空指针下一次 enqueue 写 q-rear-next 时就是非法内存访问。这两处边界条件就是链队列最常见的 bug数据结构考试也爱在这里出题。这里还有一个对后续章节至关重要的设计取舍dequeue 释放了节点内存但把客户数据指针返回给调用方。客户数据由谁 free取决于调用方还需不需要它。在银行排队系统里叫号记录要压栈客户数据不能跟着节点一起释放而是交给栈管理服务完成且回溯栈不再需要时才 free。这样的内存所有权约定能让队列、栈、主循环三方都清楚地知道“这块内存归谁管”。3.3 多窗口调度主循环三个参数决定系统表现队列和栈都就绪后用主循环把它们串起来。下面的代码完成了“每分钟检查所有窗口空闲窗口从等待区取人”的核心调度也是整个作业唯一需要每行读懂的片段。#include stdio.h #include stdlib.h #include time.h #define SIM_MINUTES 480 // 模拟时长8:00-16:00共480分钟 #define MAX_CUSTOMERS 1000 // 单日最大客户数 #define WINDOW_COUNT 3 // 窗口数量可调 // 客户到达每分钟30%概率到店 int customerArrives() { return (rand() % 100) 30; } // 随机服务时长5到20分钟 int randomServiceTime() { return 5 rand() % 16; } int main() { srand(42); // 固定种子实验可复现 LinkedQueue waitingQueue; initQueue(waitingQueue); Window windows[WINDOW_COUNT]; initWindows(windows, WINDOW_COUNT); StackNode *historyStack NULL; // 叫号历史栈后续实现 int nextId 1; int completed 0; int totalWait 0; for (int t 0; t SIM_MINUTES; t) { // 1. 客户到达取号入队 if (customerArrives() nextId MAX_CUSTOMERS) { Customer *c (Customer *)malloc(sizeof(Customer)); c-id nextId; c-arrive_time t; c-service_time randomServiceTime(); c-state 0; enqueue(waitingQueue, c); } // 2. 空闲窗口从队首取客户 for (int w 0; w WINDOW_COUNT; w) { if (windows[w].busy_until t waitingQueue.length 0) { Customer *c dequeue(waitingQueue); windows[w].busy_until t c-service_time; windows[w].total_served; c-state 1; totalWait (t - c-arrive_time); completed; pushHistory(historyStack, c); // 叫号记录压栈 } } } printf(已完成 %d 个客户平均等待 %.2f 分钟\n, completed, completed ? (double)totalWait / completed : 0); return 0; }三个参数对系统表现的影响可以从代码里直接读出来。WINDOW_COUNT 决定服务能力平均服务时长 12.5 分钟三个窗口一小时理论能处理约 14 人customerArrives 里 30% 的概率决定客流量平均一小时到店 18 人。这两个数字的比值超过 1意味着排队会持续积压模拟结果大概率是整个队列爆满。想看到“队伍能排完”的现象要把客流量降到平均一小时 12 人以下也就是把 30% 改成 20%或者把窗口数改成 4。服务时长写成 5 到 20 分钟均匀分布是作业里最省事的写法。想更接近真实业务可以改成指数分布C 语言里用 -log(1 - rand() / (double)RAND_MAX) * 均值 近似生成。不过对课程作业来说均匀分布已经够用老师验收时看的是队列和栈逻辑是否正确不是概率分布是否贴近真实客流。srand(42) 这一行尤其重要不固定种子每次运行结果都不一样实验报告里写平均等待 3.2 分钟就是一句无法复现的话这一步是答辩能否立得住的关键。3.4 过号回溯用栈保存叫号记录并按 backtrace 回放现场过号是银行排队最现实的一个场景叫到号了客户却在填单、去洗手间或者刷手机。要处理它得先把“最近被叫到的人”找回来这个语义天然是 LIFO所以栈在这时才真正入场。先看栈实现。// 栈节点data 和队列共用同一份 Customer typedef struct StackNode { Customer *data; struct StackNode *next; } StackNode; // 压栈新节点成为栈顶 void pushHistory(StackNode **top, Customer *c) { StackNode *node (StackNode *)malloc(sizeof(StackNode)); node-data c; node-next *top; *top node; } // 弹栈返回栈顶客户并释放栈节点 Customer *popHistory(StackNode **top) { if (*top NULL) return NULL; StackNode *tmp *top; Customer *c tmp-data; *top (*top)-next; free(tmp); return c; }这段代码里栈节点和队列节点各自指向同一份 Customer 内存没有复制数据所以同一客户在不同数据结构间流转时state 字段的修改是共享的。客户被叫号后压入 historyStack如果他在规定时间内没有出现在窗口就把他从栈顶弹出state 改为 2过号再 enqueue 放回等待区队尾。整个过程只涉及栈顶和队尾两个位置复杂度都是 O(1)这也是栈和队列配合的典型场景。这里也是 backtrace 栈回溯思想在课程作业里的应用调试时把 historyStack 从顶到底打印出来就能看到最近一连串叫号动作的倒序比打日志直观得多。出错的时候先从栈顶看最后一步发生了什么往往一两分钟就能定位问题。作业里常见的错误是过号客户只改 state 不压栈不出栈导致最后统计时“已叫号但服务完成数对不上”按“叫号即压栈、出栈即回溯”的约束走栈里剩多少条记录就代表还有多少客户没有最终结账数据永远能对上。4. 这个作业最常见的五个翻车问题现象、原因、排查与避坑代码跑通只是及格线下面这五个问题几乎每年都有人栽。每一条都按现象、原因、解法三步写照着排查能省下好几个晚上的重构时间。4.1 把等待区写成栈合法出栈序列判定不是用来解释排队的现象忙了一下午发现系统“后进先服务”了最后取号的客户最先被叫进窗口测试数据越跑越乱服务完成时间全对不上。原因把“栈”当成了排队的容器直接在等待区上调用 push 和 pop栈的 LIFO 特性天然和先到先服务冲突。合法出栈序列判定是用来验证“某个序列能否由栈产生”不是用来证明队列该用栈实现。解决等待区必须用队列栈只保存叫号历史也就是 3.4 节的 historyStack。如果老师点名要考合法出栈序列判定把它单独做成一个函数输入一组到达顺序和一组叫号顺序输出是否能由栈调度产生用它当验收代码题而不是把银行排队本身做成栈。这里有个小技巧调试时打印 dequeue 出队的 id 序列如果它不是按取号顺序递增的八成就是等待区用了栈。4.2 循环队列假溢出判满条件少留一格现象排队人数明明才几十个队列却报“已满”head 和 tail 指针追尾了。原因数组长度定为 N 时如果沿用 head tail 判空N 个元素全部塞满时 head 会再次追上 tail系统分不清空和满。这是循环队列的经典陷阱本质是“少留一格”还是“加计数器”的取舍没提前定。解决作业里建议直接用链队列没有判满问题。如果题目强制要求循环队列采用牺牲一个存储单元的方式队满条件写成 (rear 1) % MAX front数组长度定为 MAX实际最多存 MAX - 1 个客户。实验报告里说明用的是留格法老师不会继续深挖。还有一个更隐蔽的坑只在 enqueue 里判满、dequeue 里判空还不够主循环取队首前必须再查一次 length否则窗口空闲但队列为空时dequeue 返回 NULL 后空指针解引用直接崩。4.3 过号一律排到队尾引发饥饿现象客户过号后回到队尾排了一会儿又被叫号他又没赶上再被丢回队尾循环几次后他永远排在最后面直到下班也没服务上。原因叫号主循环每轮都从队首取人过号重排到队尾的人要等整条队清空才能再被叫到而新客户不断从队尾插入他实际上在往后退这就是过号重排引发的饥饿。解决给过号客户加一个 over_count 字段每过号一次加一主循环里做补偿每服务两个正常客户强制从过号栈弹一个人放回队首之后。另一个常见做法是直接设过号失效窗口叫号后 3 分钟内没到窗口号码作废不参与补叫。两种方案任选一种写进报告就能把“为什么过号不会无限排队”讲清楚。注意补偿逻辑要在窗口空闲时才触发不能为了补偿耽误正在服务的客户。4.4 随机数不固定种子实验报告数字无法复现现象同一份代码连续跑三次三次平均等待时间分别是 5.1、8.2、6.7 分钟图表没法解释答辩时老师一句“再跑一遍看看”就慌了。原因srand(time(NULL)) 按当前秒数初始化每次运行随机序列都不一样这本身不是 bug但让结果不可复现。解决调试和实验报告阶段固定 srand(42) 或任意常量只有做演示动画时才放开种子。换一组 WINDOW_COUNT 和 arrivalRate 做对比时固定种子保证变量唯一改一个参数看清一个参数的影响这是参数扫描的第一步也是课程报告最扎实的写法。具体落地时把 srand 放在 main 第一行别放在循环里否则每轮重新播种会让随机序列周期性重复。4.5 链队列内存泄漏free 的顺序比想象更严格现象模拟十分钟内存占用正常模拟一整天内存涨了十几兆关掉程序才回落。原因dequeue 释放了节点内存但客户数据指针没有释放压栈后如果永远不弹栈栈节点也越来越多main 结束又没有统一清理全部内存泄漏。解决主循环结束后写一个清理函数先把栈里剩余节点弹空并释放 Customer再把队列里剩余节点逐个 free注意先保存 next 指针再释放当前节点。数据结构作业里内存泄漏扣分不算狠但这个问题是后续面试白板题的高频考点值得一次写对每个 malloc 都要想清楚“谁在什么时候 free”。如果不确定可以用 valgrind 跑一遍模拟看到 definitely lost 就是漏了 free看到 still reachable 则是 main 退出前没清理。5. 把作业升级成可验证的小实验固定种子跑参数扫描代码能跑只是第一步能让老师一眼看出你理解了数据结构靠的是最后一组对比。固定 srand(42)把 WINDOW_COUNT 从 1 改到 4每个配置跑一遍 480 分钟的模拟记录完成客户数和平均等待。跑出来的趋势稳定窗口从 1 加到 2平均等待时间会下降一大截从 3 加到 4下降幅度明显收窄这就是俗称的边际收益递减。把这条曲线写进实验报告比贴十页代码更有说服力。跑参数扫描时可以把主循环里的窗口循环再包一层写成外层遍历窗口数的三重循环避免手动改宏定义重编译四次。窗口数据、客户数据、栈数据每组跑完都要清理并重置否则上一轮的剩余客户会污染下一轮。这个细节就是 4.5 节内存泄漏的反面验证清理函数写对参数扫描才能连跑多组。还有一个验证角度单独写一个合法出栈序列判定函数用几组用例做单元测试。输入 push 序列 1、2、3判定 pop 序列 3、2、1 合法3、1、2 不合法1、3、2 合法2、3、1 合法2、1、3 合法。这样既覆盖了课程核心考点也让过号重排的栈操作有了独立于主循环的验证入口答辩里被追问时直接拿这段测试用例说话。我当年交这类作业时吃过一次亏代码正确但实验报告里只有一张运行截图没有参数对比老师问“你在什么条件下测的”答不上来。后来每次写数据结构课程作业都先确保固定种子、再跑参数扫描。这半年攒下来的习惯是功能跑通是及格线能复现、能解释、能对比才是真正吃透。这个思路在后续写栈和队列相关代码时会一直有用希望帮到你。本文还有配套的精品资源点击获取