双栈模拟队列：C语言实现银行排队系统全解析

简介大二下数据结构课程设计——银行排队系统项目包面向正在学习栈、队列等线性结构的学生解决如何用数据结构模拟银行多窗口排队、VIP优先服务等实际问题。项目基于C实现包含主要源码、可执行程序、工程配置文件及说明文档压缩包共8个文件体积约334KB轻量易用。已有2865人浏览学习适合用于课程作业参考或课后练习。内容紧密结合课堂理论普通客户按到达顺序进入队列先进先出VIP客户通过栈的压入/弹出操作优先插队服务还可模拟多窗口分行处理动态调整服务策略。通过阅读源码和运行程序可以直观看到队列FIFO与栈LIFO在实际场景中的配合使用并进一步理解如何用程序实现数据结构的业务逻辑。资源文件类型以cpp、txt为主附带exe可执行文件与cbp工程文件便于直接运行和二次修改。1. 银行排队系统用栈实现先破掉“该用队列”的直觉大二下的数据结构作业“银行排队系统”乍看起来很矛盾排队明明是天经地义的先进先出题目却点名要你写“排队系统栈”。很多人第一版代码就是把客户挨个 push 进一个栈运行起来才发现最后取号的客户反而第一个被叫号当场翻车。问题不在栈写得不好而在模型没翻转栈是后进先出队列是先进先出两者在逻辑上是逆序关系。这道作业真正要练的是能不能用两个栈把 LIFO 硬掰成 FIFO。这篇笔记按建模、实现、避坑、验证的顺序展开最后给一个答辩时能多讲三分钟的封装写法。适合正在赶这份作业的在校生也适合复习栈和队列考点的考研人照着敲一遍。2. 把 LIFO 掰成 FIFO栈排队系统的模型翻转2.1 作业里“排队系统栈”到底在说什么“排队系统栈”不是一种新数据结构而是“用栈实现的排队系统”的缩写本质是数据结构的组合应用。老师给这道题的目的不是让你调库而是逼你回答一个问题容器本身不支持先进先出怎么用一组操作还原出先进先出的语义栈对外只暴露三个能力压入、弹出、看栈顶。这三个能力在时间轴上天生只回放最近的事件。想让历史事件按原顺序回放唯一办法是把已经逆序的数据再压进第二个栈里从头再来一遍。两次“后进先出”叠加等于一次“先进先出”逆序的逆序是原顺序。这就是双栈模拟队列的全部原理也是这道作业最核心的建模结论。一个容易混淆的点是银行叫号顺序是 FIFO但柜台客户的“办理顺序”并不严格要求 FIFO。如果作业没有额外说明默认要求就是先到先服务。所以不要为了迎合栈而把出队顺序改成后到先服务那是未完成建模不是设计方案。2.2 双栈模拟队列倒一次就是排队两个栈分别叫 inStack 和 outStack业务上可以理解为“新客户暂存区”和“叫号待发区”。入队永远只压 inStack出队之前先检查 outStack如果 outStack 为空就把 inStack 里的元素全部弹出并按弹出顺序压进 outStack。这个动作叫“倒栈”。倒完栈后从 outStack 栈顶弹出第一个客户就是整个队列里最早来的那一位。这里两条规则缺一不可第一倒栈必须“全部倒完”不能倒一半就出队第二必须等 outStack 空了才能再倒。举一个最小例子客户 1、2、3 依次入队倒栈后 outStack 里从栈顶到栈底依次是 1、2、3。弹出 1 是第一个客户。这时来了一位新客户 4入队压进 inStack。下一次叫号时 outStack 还没空直接从 outStack 弹出 2顺序依然正确。等到 outStack 空了而 inStack 里有 4下一次叫号前才会把 4 单独倒过来。整个过程任意时刻出队顺序都与入队顺序一致。从抽象层面看双栈模拟队列就是把“排队”拆成两段操作先进来的人先进暂存区等到真正要叫号时再整体翻转到待发区。两次翻转抵消了栈的逆序特性对外表现和一个真正的队列完全一样。2.3 容量、窗口数与初始参数怎么定实现前先定几个参数这部分也直接对应实验报告里的“需求分析”。参数常见取值说明MAX_SIZE100单个顺序栈的容量队列最多同时在等 MAX_SIZE 位客户窗口数1队列只管叫号分配窗口的逻辑可留到扩展编号起点1id_counter 从 1 递增便于手工核对数据文件queue_log.txt退出前导出当前等待队列MAX_SIZE 设成 100 对绝大多数课程评测足够。两个栈分别占 MAX_SIZE 个元素空间可能出现一个栈满载、另一个栈全空的极端情况所以队列的实际容量上限是 MAX_SIZE而不是两个栈容量之和。窗口数在基础版本里可以不接入调度逻辑service 函数里打印“请 xx 号客户到 xx 号窗口”即可。如果要做得更完整再加一个窗口状态数组有空闲窗口才叫号。注意MAX_SIZE 不要拍脑袋写 1000。顺序栈是连续内存数组开得越大出队倒栈时的数据搬运量也越大对课程演示没有帮助。3. 用C语言跑通银行排队系统结构体、双栈与菜单3.1 结构体设计与栈的基本操作代码采用静态数组顺序栈不用链栈。原因很简单作业规模小顺序栈能少写内存管理代码避免在课设里引入 malloc 和 free 的隐患。链栈可以在实验报告“改进方向”里提一句但主程序跑通为王。#include stdio.h #include stdlib.h #include string.h #define MAX_SIZE 100 // 单个栈容量也是队列容量上限 #define MAX_NAME 20 // 客户姓名长度上限 typedef struct { int id; // 取号编号从 1 递增 char name[MAX_NAME]; // 客户姓名 int service_time; // 预计办理时长单位分钟 } Customer; typedef struct { Customer data[MAX_SIZE]; int top; // 栈顶下标-1 表示空栈 } Stack; void initStack(Stack* s) { s-top -1; } int isStackEmpty(Stack* s) { return s-top -1; } int isStackFull(Stack* s) { return s-top MAX_SIZE - 1; } void push(Stack* s, Customer c) { if (isStackFull(s)) { printf(暂存区已满无法入队\n); return; } s-data[(s-top)] c; } Customer pop(Stack* s) { Customer fail; fail.id -1; fail.name[0] \0; fail.service_time -1; if (isStackEmpty(s)) { printf(暂存区为空弹出失败\n); return fail; } return s-data[(s-top)--]; } Customer peek(Stack* s) { Customer fail; fail.id -1; fail.name[0] \0; fail.service_time -1; if (isStackEmpty(s)) { return fail; } return s-data[s-top]; }结构体里把客户建模为编号、姓名、办理时长三个字段。id 必须独立于数组下标因为在双栈搬运过程中数组下标一直在变只有 id 能稳定标识一位客户。pop 失败时返回 id 为 -1 的哨兵 Customer主程序判断 id 小于 0 就能识别失败比只打印一条错误信息更可靠。3.2 入队出队与叫号核心业务函数有了栈的基本操作再封装队列层。队列层对外只暴露四个函数初始化、入队、出队、统计人数。这一层是和栈的唯一接触面。typedef struct { Stack inStack; // 新客户先进这里 Stack outStack; // 叫号时从这里出 } Queue; void initQueue(Queue* q) { initStack((q-inStack)); initStack((q-outStack)); } void enqueue(Queue* q, Customer c) { push((q-inStack), c); } // 核心只有 outStack 为空才把 inStack 整体倒过来 Customer dequeue(Queue* q) { if (isStackEmpty((q-outStack))) { while (!isStackEmpty((q-inStack))) { push((q-outStack), pop((q-inStack))); } } return pop((q-outStack)); } int countQueue(Queue* q) { return q-inStack.top 1 q-outStack.top 1; } void service(Queue* q) { if (isStackEmpty((q-inStack)) isStackEmpty((q-outStack))) { printf(当前没有等待客户\n); return; } Customer c dequeue(q); if (c.id -1) { printf(出队失败请检查栈状态\n); return; } printf(请 %d 号客户到窗口办理预计时长 %d 分钟\n, c.id, c.service_time); }dequeue 是整个系统的核心顺序不能反先判 outStack 空不空空了才倒栈倒栈要一次倒完。如果把“倒栈”放到 enqueue 里做新客户入队时会反复搬运数据顺序虽然对但每次入队都是 O(n) 操作作业避坑时会被老师追问复杂度。现在这样设计每个客户最多被压两次、弹两次dequeue 均摊 O(1)。service 的职责是判断队列是否真空再安全调用 dequeue。3.3 总控菜单与文件导出主程序做一个循环菜单。菜单不追求花哨但每个分支都要能独立运行退出前自动保存等待队列到文件方便实验报告直接贴截图。void saveQueue(Queue* q, const char* filename) { FILE* fp fopen(filename, w); if (fp NULL) { printf(文件打开失败\n); return; } fprintf(fp, Bank Queue Log \n); // 出队顺序outStack 从栈顶到栈底然后 inStack 从栈底到栈顶 for (int i q-outStack.top; i 0; i--) { fprintf(fp, %d %s %d\n, q-outStack.data[i].id, q-outStack.data[i].name, q-outStack.data[i].service_time); } for (int i 0; i q-inStack.top; i) { fprintf(fp, %d %s %d\n, q-inStack.data[i].id, q-inStack.data[i].name, q-inStack.data[i].service_time); } fclose(fp); printf(排队记录已保存到 %s\n, filename); } int main() { Queue bankQueue; initQueue(bankQueue); int choice 0; int idCounter 1; while (1) { printf(\n 银行排队系统(双栈版) \n); printf(1. 客户取号入队\n); printf(2. 叫号办理\n); printf(3. 查看队首\n); printf(4. 显示等待人数\n); printf(5. 保存排队记录\n); printf(6. 退出并保存\n); printf(请选择: ); if (scanf(%d, choice) ! 1) { break; } switch (choice) { case 1: { Customer c; c.id idCounter; printf(请输入姓名: ); scanf(%s, c.name); printf(请输入办理时长(分钟): ); scanf(%d, c.service_time); enqueue(bankQueue, c); printf(%d 号客户入队成功\n, c.id); break; } case 2: service(bankQueue); break; case 3: { Customer c; if (!isStackEmpty(bankQueue.outStack)) { c peek(bankQueue.outStack); } else if (!isStackEmpty(bankQueue.inStack)) { c bankQueue.inStack.data[0]; } else { printf(队列为空\n); break; } printf(队首客户: %d号 %s 时长%d分钟\n, c.id, c.name, c.service_time); break; } case 4: printf(当前等待客户总数: %d\n, countQueue(bankQueue)); break; case 5: saveQueue(bankQueue, queue_log.txt); break; case 6: saveQueue(bankQueue, queue_log.txt); printf(已保存并退出\n); return 0; default: printf(无效选择请重新输入\n); } } return 0; }case 3 的队首查找逻辑最容易写错单独解释一下如果 outStack 非空栈顶就是下一个被叫号的人如果 outStack 空而 inStack 非空inStack 最底部才是一开始就排队的客户所以取 data[0]。两个都空才是队列为空。这段代码里两个栈的 top 同时参与计算手工推一遍就明白为什么顺序是“out 顶到底 in 底到顶”。文件导出的顺序和队首逻辑一致保证日志读回来就是实际叫号顺序。4. 银行排队系统避坑记录5个让作业翻车的细节4.1 单栈直接出队最后一个变成第一个现象客户 1、2、3 依次取号第一次叫号直接叫了 3 号。原因单栈 LIFOpop 一定拿最后 push 的元素。这是全作业最常见的翻车现场。解决不要想着“再遍历一遍找到第一个”而是老老实实用双栈。先建模再写代码这一段血泪经验值一个通宵。简单的判别方法写完后跑三组入队出队看输出顺序是不是 1、2、3。4.2 使用 Visual Studio 时 scanf 编译报 C4996现象代码在 Dev-C 里好好的放到 Visual Studio 编译直接报错error C4996: scanf: This function or variable may be unsafe。原因VS 默认禁用 scanf 系列函数要求替换成 scanf_s。解决在源文件最顶部、所有 #include 之前加一行#define _CRT_SECURE_NO_WARNINGS。不要改用 scanf_s因为 scanf_s 是 VS 特有的老师用 gcc 环境评阅时反而编译失败。Dev-C、Code::Blocks 没有这个问题。注意#define _CRT_SECURE_NO_WARNINGS必须出现在所有头文件之前放在#include stdio.h后面仍然报错。4.3 中文字符串写进文件变成乱码现象printf 输出中文正常用记事本打开 queue_log.txt 却是一堆乱码。原因Dev-C 等老环境默认用 GBK 保存源码printf 写出的也是 GBK 字节电脑默认按 UTF-8 打开文本文件时就会乱码。解决文件内容头一行用英文比如 “ Bank Queue Log ”客户姓名本身如果是中文截图贴进实验报告即可。不要在程序里折腾编码转换C 语言课程作业不值得为编码花时间。4.4 空队列时叫号程序读栈底垃圾数据现象没有任何客户时按“叫号办理”程序不提示“没有客户”反而打印出一串负数 id偶尔直接崩溃。原因service 里只判断了 outStack 空没判断 inStack 也空dequeue 返回的哨兵 Customer 没有在 service 里处理。解决dequeue 返回后必须检查 c.id -1另外查看队首的分支也要先判断两个栈都空。这种问题最难排查表面看“能跑”实际结果全错。如果已经崩了用 gdb 跑一次backtrace看调用栈就能发现是哪个函数没做空判断——栈回溯比 printf 大法高效得多。4.5 链栈的 malloc 不释放或者重复 free现象抄了网上的链栈模板跑完服务台数据显示内存泄漏手动加 free 后又出现“double free”崩溃。原因链栈每个节点都是 malloc 出来的退出前必须逐个释放但释放逻辑写错同一个节点被 free 两次就是未定义行为表现非常玄学。解决课程作业直接用静态数组顺序栈一个 free 都不用写。如果坚持用链栈写一个 destroyStack在主函数 return 前调用一次并保证任何分支都只调用一次。5. 从能跑到能答辩排队系统的验证用例与实验报告5.1 手工验证用例四组操作覆盖全部边界程序写完只能算能跑交之前必须做顺序验证。下面的用例拿笔照样推一遍再对照程序输出。操作序列期望输出验证点enq(1), enq(2), deq1基础 FIFO 顺序enq(1), deq, enq(2), deq1 然后 2第一批倒栈后第二批顺序不被打乱enq(1), enq(2), deq, enq(3), deq, deq1、2、3outStack 非空时新客户不提前enq(1), enq(2), enq(3), deq, deq, deq1、2、3整批倒栈一次完整输出第一组验证最基础的双栈翻转。第二组验证“倒一半再来新客户”不会插队。第三组是最容易出问题的场景outStack 里还有 2新来的 3 只进 inStack必须等 outStack 空了再倒。第四组验证连续出队时只倒一次栈后续都直接弹出。5.2 合法出栈序列判定一道跟本题强相关栈算法题答辩时老师喜欢顺着栈往下追问给定入栈序列 1 到 n怎么判断一个输出序列是合法的出栈序列这是数据结构题库里的常客也直接检验你对栈行为的理解。判定的经典思路是模拟用一个辅助栈遍历目标输出序列如果栈顶不是当前目标就从入栈序列里继续压入如果入栈序列全部压完栈顶还不是目标说明该序列不合法。// 判断长度为 n 的出栈序列是否合法 // out 数组存放待判定序列入栈序列为 1..n int isValidPopSequence(int out[], int n) { int aux[n]; // 辅助栈 int top -1; int in 1; // 下一个待压入的元素 for (int i 0; i n; i) { // 栈顶不是目标时继续压入 while (in n (top -1 || aux[top] ! out[i])) { aux[top] in; } if (top -1 || aux[top] ! out[i]) { return 0; // 入栈序列全部用完还没匹配上 } top--; // 匹配成功弹出 } return 1; }参数 n 是序列长度out 是待判定的出栈序列。函数返回 1 表示合法序列。例如输入序列 1、2、3输出序列 3、1、2 会返回 0因为 3 弹出后栈里只剩下 21 在更底下拿不到 1。这个结论可以写进实验报告的“算法扩展”一节能明显提升报告层次。5.3 数据结构实验报告的四块内容实验报告不是代码粘贴。按下面的结构写老师想扣分都难找理由。第一块是问题建模把“先到先服务”抽象成先进先出队列再把队列用两个栈实现画一个数据流向示意outStack 和 inStack 的关系一句话讲清。第二块是结构设计给出 Customer、Stack、Queue 三个结构体定义配上核心函数列表和复杂度分析。出队最坏 O(n)均摊 O(1)入队 O(1)这点必须写。第三块是测试结果直接放 5.1 的四组用例输出截图再放 queue_log.txt 的截图。第四块是结果分析写“用队列实现排队只需要五分钟用栈实现让我理解了抽象层级”这是真实的作业体会比空喊“通过本次实验我收获很多”有用得多。6. 一个更稳的封装双栈队列接口与答辩加分写法到这一步双栈逻辑已经能跑。如果想在答辩时多讲三分钟把队列层再往抽象提一级对外只暴露 QueueInit、QueuePush、QueuePop、QueueEmpty 四个接口主程序完全不知道内部有栈的存在。typedef struct { Stack inStack; Stack outStack; } Queue; void QueueInit(Queue* q) { initStack((q-inStack)); initStack((q-outStack)); } void QueuePush(Queue* q, Customer c) { push((q-inStack), c); } Customer QueuePop(Queue* q) { if (isStackEmpty((q-outStack))) { while (!isStackEmpty((q-inStack))) { push((q-outStack), pop((q-inStack))); } } return pop((q-outStack)); } int QueueEmpty(Queue* q) { return isStackEmpty((q-inStack)) isStackEmpty((q-outStack)); }这样封装之后main 函数调用的只有“入队”“出队”“判空”和调用标准库里的队列没有区别。答辩时就能自然讲出抽象数据类型的概念上层只关心干什么不关心怎么存。把 Queue 类型单独放到 queue.h 里Stack 的相关实现放在 stack.c就是一个标准的分层设计。我当时做这道题时就栽在“直接存取栈顶”这个动作上。老师问为什么 case 3 要分别看 outStack 和 inStack我支支吾吾半天。后来把队列操作全部封装起来对外只留四个接口内部怎么折腾都不影响上层逻辑才真正想明白这道题在教什么。这个封装习惯后来写 Linux 驱动和设备驱动时一直在用数据结构作业其实是在给工程基本功打底。希望这篇笔记能让你少走一点我当时走过的弯路也希望你能在答辩时把双栈翻转讲得比当年的我更清楚——希望帮到你。本文还有配套的精品资源点击获取