循环队列与事件驱动模拟：银行排队系统平均等待时间计算

简介：数据结构课程中的银行排队系统作业包，面向正在学习队列、准备完成期末项目或课程设计的学生，重点解决普通用户与VIP用户分流及优先级服务的模拟问题。压缩包共9个文件，约1.03MB，以cpp源代码、txt数据与说明、exe可执行程序及Code::Blocks工程文件为主，另含编译产生的对象文件与依赖、布局配置，便于直接运行和二次修改。目前已有3369人学习或下载，适合作为队列章节的参考案例。项目围绕队列先进先出特性展开，包含VIP队列优先检查、普通队列兜底的服务流程，并涉及文件读取用户信息、STL queue的入队出队操作以及循环与条件判断的控制逻辑。读者可据此理解多队列设计与优先级处理，借助可执行程序和样例数据快速验证运行结果，也能在工程配置与源码结构中梳理从需求到实现的完整思路。

1. 从「平均等待时间」看银行排队系统：拉开分数的地方不在队列函数

「数据结构期末作业」里，银行排队系统这道题的失分点，往往不在队列函数，而在最后那个平均等待时间。绝大多数人卡在写完了入队出队、跑起来却算出 0.00 或者一个越跑越大的数字。这道题真正的考点是把「客户到达—排队—办理—离开」这条时间线，拆成四个时间量、一张按时间排序的事件表、一次从头到尾的遍历。队列只是容器，时间账才是答案。

拿分的顺序很清楚：先证明确实使用了队列这种结构，顺序存储和链式存储都行，但判空判满要写对；再证明确实实现了事件驱动而不是按单位时间空转；最后让统计量对得上——客户数、总等待时间、平均等待时间、最大等待时间，四个数互相自洽。适合已经学过栈和队列、要交课程设计或做大作业的人，也适合正在补队列这一章、想用一个完整案例把零散知识点串起来的人。下面按考点→真题→答题思路→失分点推。

2. 队列基础考点：循环队列的三个公式与链队列的两处指针

2.1 判空与判满：三种方案，卷面默认只认第一种

顺序循环队列的存储结构通常是data[MaxSize]加两个整型游标，front指向队头元素，rear指向队尾元素的下一个位置。问题出在这里：队空时front == rear，如果队满也用同一个条件，两种情况分不开。三种解法必须张口就来。

考试和答辩默认第一种，原因是它不动任何额外变量，纯靠指针关系判断。答题时第一句就把方案点明——「采用牺牲一个存储单元的方案，队满条件为(rear+1)%M==front」，阅卷的人不用往下猜，判定分先拿到手。如果题目明确要求「不能浪费存储空间」，才换 size 或 tag 方案，并且要把维护逻辑补全，否则判满条件写对了、size 忘了加减，一样扣。

还有一处容易含糊：rear到底指向队尾元素还是它的下一个位置。两种约定都有人用，但公式完全不同。指向「下一个位置」时判满才是(rear+1)%M==front；如果rear指向队尾元素本身，判满就变成(rear+2)%M==front，元素个数也变成(rear-front+M)%M+1。答卷上必须把约定写死，别一半按前一种、一半按后一种，自己把自己绕进去。

2.2 元素个数、入队、出队：三个必须能默写的公式

元素个数是最高频的一个小计算题，公式是(rear - front + M) % M。这里的+M不是装饰：C 语言里负数取模结果仍是负数，当rear < front（指针已经绕过一圈）时，直接写(rear-front)%M会算出负值。这一步是历年卷面上最常见的丢分动作，写代码时加，写解析时也要说明为什么加。

#include <stdio.h> #define MAXSIZE 10 /* 数组容量，实际最多存 MAXSIZE-1 个元素 */ typedef struct { int data[MAXSIZE]; int front; /* 队头元素下标 */ int rear; /* 队尾元素的下一个位置 */ } SqQueue; /* 初始化：两个游标归零，不置 -1，配合取模运算 */ void InitQueue(SqQueue *q) { q->front = q->rear = 0; } /* 队空：两游标重合 */ int QueueEmpty(SqQueue *q) { return q->front == q->rear; } /* 队满：rear 再走一步就撞上 front，牺牲一个单元 */ int QueueFull(SqQueue *q) { return (q->rear + 1) % MAXSIZE == q->front; } /* 元素个数：加 MAXSIZE 防止负数取模 */ int QueueLength(SqQueue *q) { return (q->rear - q->front + MAXSIZE) % MAXSIZE; } int EnQueue(SqQueue *q, int x) { if (QueueFull(q)) return 0; /* 满则失败，返回 0 而不是直接退出 */ q->data[q->rear] = x; /* 先放元素 */ q->rear = (q->rear + 1) % MAXSIZE; /* 再移动游标，顺序不能反 */ return 1; } int DeQueue(SqQueue *q, int *x) { if (QueueEmpty(q)) return 0; *x = q->data[q->front]; /* 先取元素 */ q->front = (q->front + 1) % MAXSIZE; /* 再移动游标 */ return 1; }

参数层面的关键是MAXSIZE决定了可存容量是MAXSIZE-1；想看「指针绕回」的行为，把MAXSIZE改成 5，连续入队 4 个再出队 2 个，rear会落到比front小的位置，这时元素个数公式里不+MAXSIZE立刻出负数。返回值用 0/1 而不是exit()，是为了让上层模拟程序能判断失败、继续跑事件循环，答辩被问「队满了作业怎么办」，答「银行系统里对应的是限流或提示取号失败，所以入队失败必须能被上层感知」，比答「直接退出程序」高一个档次。

2.3 真题演练：四道基础题的标准写法

第一题，容量MAXSIZE=10，front=3，rear=8，求元素个数。代入公式(8-3+10)%10 = 5。不要在图上去数格子，绕圈之后越数越乱。

第二题，MAXSIZE=10，front=3，队列中有 9 个元素，求rear。反解公式：rear = (front + 9) % 10 = 2。这题考的是你敢不敢让rear落在front前面，以及能不能发现此时(rear+1)%10 == front恰好成立——说明这两个公式是自洽的。

第三题，链队列只有头结点和唯一一个数据结点，执行一次出队后，front和rear分别指向哪里。答案是都指向头结点，front == rear回到空队状态。多数人只写「front 后移」，漏掉rear回退，队列就「断链」了：rear还指着已经被free掉的结点，下一次入队往野指针上挂，程序直接崩。

第四题，判断「循环队列满时，rear的下一个位置就是front」。正确，这句话就是判满条件的文字版，答题时把公式和这句话一起写，属于稳拿分的组合。

这四类题的答题模板可以固定成三步：先写存储结构的定义与front/rear的指向约定，再写判空判满条件，最后才写操作和计算。顺序反了，判分点就散了。

3. 离散事件模拟：事件表、四个时间量与一份能跑的骨架

3.1 为什么必须用事件驱动，而不是按单位时间轮询

最直觉的写法是让时间从 0 开始每秒加一，每一秒扫一遍队列。这种写法能跑出结果，但有两个硬伤：一是当到达间隔和服务时长都是几十个单位时，绝大多数时间片里什么都没发生，白扫；二是「同一秒内两个客户到达」这种并发情况处理起来含糊，容易偏一整个单位。

事件驱动的思路反过来：只在「有事发生」的时刻才醒来，中间的时间直接跳过去。所有将来要发生的事挂在一条事件表上，按发生时刻升序排列。循环里永远只取表头最早的那个事件，处理完再决定要不要往表里插入新事件。时间不是走出来的，是被事件推着跳的。

这样做的代价是必须维护事件表的有序性。事件表用单链表最合适：插入要找位置，链表插入 O(1) 只花在找位置上，不用像数组那样整体挪动。这一点答辩被问到「为什么事件表用链表不用数组」时，要能答出「插入频繁、删除永远在表头、不需要随机访问」——三个理由对上三个操作特征。

3.2 事件表的两类事件与四个时间量

银行排队里只有两种事件：到达（客户进门取号）和离开（窗口空出来）。每个事件记两个字段就够：发生时刻、事件类型。事件表的插入函数按occurTime升序找位置，越早的排越前。

时间账目一共四个量，缺一不可：

• 到达时刻arriveTime：客户进门的时刻，入队时就存在队列数据域里，别另开数组，队列本身就是等待队列。
• 开始办理时刻startTime：该客户前面的人全部办完的时刻。单窗口时它就是上一位的离开时刻；多窗口时是某个窗口空出来的时刻。
• 办理时长duration：随机生成，客户之间相互独立。
• 离开时刻leaveTime = startTime + duration。

等待时间是startTime - arriveTime，不是leaveTime - arriveTime。后者是逗留时间，多算了一段自己的办理时长。这个区别在卷面上值一道简答题，在代码里值一次全盘返工。四个量之间的关系最好在草稿纸上画一条时间轴：到达点、开始点、离开点，三个点两段长度，等待时间永远只取左边那段。

同一时刻如果有多个事件，处理顺序要在注释里写清楚，别留给阅卷的人猜。常见约定是先处理离开、再处理到达，因为离开会立刻腾出窗口，紧接着到达的客户能直接办理，不会被人为地多算一个单位的等待。

3.3 随机参数怎么设：ρ 小于 1 是这份作业的底线

到达间隔和办理时长都要随机生成。教材里用泊松到达，间隔服从指数分布，写法是interval = -mean * ln(u)，u取 (0,1) 之间的随机数；期末作业里通常允许简化成均匀分布，用rand()%范围 + 下界生成。两种都能得分，但要在报告里说明用的是哪一种。

真正决定作业成败的是一个比值：ρ = 平均办理时长 / 平均到达间隔。它衡量「服务能力」和「客户涌入速度」的关系。ρ 小于 1，队列迟早会回到空闲，系统稳定，平均等待时间收敛到一个固定值；ρ 大于等于 1，队列长度无界增长，平均等待时间随着营业时长线性上涨，跑 8 小时和跑 80 小时能差十倍。

很多人跑出「等待时间一分钟」这种离谱数字，第一反应是代码有 bug，其实是参数选崩了。比如到达间隔取 1 到 5（平均 3）、办理时长取 3 到 10（平均 6.5），ρ 约等于 2.17，这是典型的过载系统。正确的改法是把办理时长压到 1 到 4（平均 2.5），ρ 约等于 0.83，队列才会稳。答辩时主动说出这个比值，并且说出「ρ 大于 1 时系统不稳定，平均等待时间无稳态值」，属于加分表述，因为它证明你懂数字背后的含义，不只是会跑程序。

3.4 完整骨架：从入队到平均等待时间

下面的骨架是单窗口版本，跑通之后再扩成多窗口。随机函数单独抽出来，方便答辩时改参数重跑对比。

#include <stdio.h> #include <stdlib.h> #include <time.h> #define MAXSIZE 200 typedef struct { int data[MAXSIZE]; /* 存客户的到达时刻 */ int front, rear; } SqQueue; void InitQueue(SqQueue *q) { q->front = q->rear = 0; } int QueueEmpty(SqQueue *q) { return q->front == q->rear; } int QueueFull(SqQueue *q) { return (q->rear + 1) % MAXSIZE == q->front; } int EnQueue(SqQueue *q, int x) { if (QueueFull(q)) return 0; q->data[q->rear] = x; q->rear = (q->rear + 1) % MAXSIZE; return 1; } int DeQueue(SqQueue *q, int *x) { if (QueueEmpty(q)) return 0; *x = q->data[q->front]; q->front = (q->front + 1) % MAXSIZE; return 1; } /* 到达间隔 1~5，平均 3；办理时长 1~4，平均 2.5 */ int RandomInterval(void) { return rand() % 5 + 1; } int RandomDuration(void) { return rand() % 4 + 1; } /* 事件表：按 occurTime 升序的单链表 */ typedef struct EventNode { int occurTime; /* 事件发生时刻 */ int nType; /* 0 到达，1 离开 */ struct EventNode *next; } EventNode, *EventList; typedef struct { EventList head; /* 带头结点的有序单链表 */ } EvTable; void InitEventTable(EvTable *t) { t->head = (EventList)malloc(sizeof(EventNode)); t->head->next = NULL; } /* 按时间升序插入，插入位置在第一个严格大于它的结点之前 */ void OrderInsert(EvTable *t, int time, int type) { EventNode *p = t->head; while (p->next != NULL && p->next->occurTime < time) p = p->next; EventNode *s = (EventNode)malloc(sizeof(EventNode)); s->occurTime = time; s->nType = type; s->next = p->next; p->next = s; } /* 取表头事件，返回 0 表示事件表已空 */ int DelFirst(EvTable *t, int *time, int *type) { EventNode *p = t->head->next; if (p == NULL) return 0; t->head->next = p->next; *time = p->occurTime; *type = p->nType; free(p); return 1; } int main(void) { srand((unsigned)time(NULL)); SqQueue q; InitQueue(&q); EvTable ev; InitEventTable(&ev); const int closeTime = 480; /* 营业 480 个时间单位，关门后不再放人进 */ OrderInsert(&ev, 0, 0); /* 第一位客户在 0 时刻到达 */ int totalWait = 0, customerNum = 0, maxWait = 0; int now, type; while (DelFirst(&ev, &now, &type)) { if (type == 0) { /* 到达事件 */ customerNum++; EnQueue(&q, now); /* 队列里只存到达时刻 */ int nextArrive = now + RandomInterval(); if (nextArrive < closeTime) { /* 关门后不再生成到达事件 */ OrderInsert(&ev, nextArrive, 0); } /* 若当前无人办理，立刻产生一条离开事件，避免队列假死 */ if (QueueEmpty(&q) == 1 && customerNum == 1) { OrderInsert(&ev, now + RandomDuration(), 1); } } else { /* 离开事件 */ if (!QueueEmpty(&q)) { int arriveTime; DeQueue(&q, &arriveTime); int wait = now - arriveTime; /* 该客户从此刻开始办理 */ totalWait += wait; if (wait > maxWait) maxWait = wait; OrderInsert(&ev, now + RandomDuration(), 1); } } } printf("客户数=%d 平均等待=%.2f 最大等待=%d 队列剩余=%d\n", customerNum, (double)totalWait / customerNum, maxWait, (q.rear - q.front + MAXSIZE) % MAXSIZE); return 0; }

这段代码有三处需要能讲出理由。第一，队列的数据域存的是到达时刻而不是客户编号，因为后面计算等待时间只用到到达时刻，存编号还得再开一张表查，属于多余结构。第二，nextArrive < closeTime这个判断是边界：关门前最后一刻进来的客户仍然要服务完，人不再进来但事件表里已有的离开事件必须继续消化，否则统计出来的客户数偏少。第三，循环的终止条件写的是事件表取空，不是时间到达closeTime，因为关门时队列里可能还排着人，这批人的等待时间也要算进去，否则平均等待会被系统性低估。

扩成多窗口的改法：维护一个空闲窗口计数idleWin，到达事件里若idleWin > 0就减少一个并直接生成离开事件；离开事件里若队列非空，出队一位并把窗口继续占用，否则idleWin加一。窗口数改成 3 之后重跑，平均等待应明显下降，这个对比实验本身就是报告里最有说服力的一张表。

4. 高频真题：两个栈、两种队列与答辩三问

4.1 两个栈模拟队列：倒一次，均摊 O(1)

题目要求用两个栈实现队列的入队和出队。设入栈s1、出栈s2，规则只有两条：入队一律压s1；出队时若s2为空，就把s1里的元素一次性全部弹出并压入s2，再从s2弹栈顶。

/* 入队：直接压 s1，O(1) */ void EnQueue(Stack *s1, int x) { Push(s1, x); } /* 出队：s2 空才倒，且必须一次倒完，均摊 O(1) */ int DeQueue(Stack *s1, Stack *s2, int *x) { if (StackEmpty(s2)) { while (!StackEmpty(s1)) { int t; Pop(s1, &t); /* 弹出最早压入的 */ Push(s2, t); /* 压进 s2 后变成栈顶，顺序正好反过来 */ } } if (StackEmpty(s2)) return 0; /* 两个栈都空，队列为空 */ return Pop(s2, x); /* 从 s2 取，就是队头 */ }

关键在两处。一是「只有s2空了才倒」，如果每次出队都倒一遍，顺序会乱，复杂度和正确性一起崩。二是「一次倒完」，倒一半停下，s1里剩下的老元素会被后来者压在上面，出队顺序就反了。复杂度分析要答出「单次出队最坏 O(n)，但每个元素最多被搬两次，均摊下来是 O(1)」，只答 O(n) 会丢一半分。

4.2 循环队列和链队列怎么选：四种场景对号入座

这道选择题几乎每年都会换皮出现，答案取决于容量是否可预估、是否允许浪费空间。

答这类题的模板是先给结论，再给两条理由，最后补一个反例。比如「选链队列，因为客户数不可预估，顺序队列一旦溢出就必须扩容或丢弃请求；反过来说，如果题目限定了每日取号上限，顺序循环队列更省内存」。

4.3 答辩三问：为什么用队列、为什么用链队列、复杂度怎么算

第一问「为什么用队列而不是数组」。队列的语义是先进先出，恰好等于「先来的先办理」，这个语义本身就是业务规则；顺序表实现 FIFO 需要自己维护头尾下标并处理搬移，本质上是手写了一个更差的循环队列。答的时候要点出「数据结构的语义和业务规则对齐」，别只说「老师要求用队列」。

第二问「为什么事件表用链表」。三个操作特征对应三个理由：插入频繁且位置不定、删除永远在表头、不需要按下标随机访问。链表插入只改两个指针，数组插入要整体后移。

第三问「时间复杂度」。单次模拟里，每个客户产生一条到达事件、一条离开事件，共 2n 条；每条事件插入有序链表要顺序查找位置，最坏 O(n)。总计 O(n²)。如果答辩想加一句「用最小堆代替有序链表，插入降到 O(log n)，整体 O(n log n)」，但要补一句「本作业客户规模在千级，链表足够，堆属于后续优化」，不要为了炫技改结构反而引入 bug。

4.4 变体题：VIP 优先窗口与最短队列派发

题目加一句「设置一个 VIP 窗口，VIP 客户优先办理」，处理方式有两种。第一种是双队列：普通队列和 VIP 队列分开，出队时先看 VIP 队列是否为空，不空就优先出，空了再出普通队列。这种写法改动最小，判空条件要写两遍，容易漏。第二种是优先队列，给每个客户带上优先级，用一个堆维护，出队永远取优先级最高的。答辩被问区别，答「双队列实现简单但只支持两级，堆支持任意多级但代码量大，作业里客户只有两类，双队列足够」。

「多个普通窗口，新来的客户排到最短的队列」也常考。做法是维护一个长度数组，到达时遍历一遍找最小值，复杂度 O(k)，k 为窗口数。要注意的是，最短队列策略的平均等待通常优于固定派发，但客户可能刚排到最短队列，旁边那个窗口就办完了，所以仿真结果要跑多次取平均，单次结果波动很大。

5. 失分点：五个地方一写就扣分

5.1 把平均等待时间算成了平均逗留时间

错在哪：统计时写成leaveTime - arriveTime，把客户自己办理业务的那段时间也算进去了。为什么错：等待时间是「排队等了多久」，逗留时间是「从进门到出门总共多久」，两者差一个duration。银行关心的服务体验是前者。怎么答对：先把四个时间量在轴上标清，等待时间只取「开始办理时刻减到达时刻」，代码里出队那一刻的now就是startTime，别等到离开事件里回头算。

5.2 循环队列判满条件抄成rear == front

错在哪：判空判满写成同一个条件，队满时程序认为队空，继续入队覆盖数据，跑出来的客户数永远偏少。为什么错：脑子里记的是「两个指针撞上就是满了」，忘了撞上有两种含义。怎么答对：答题第一句点明方案——牺牲一个单元，判满(rear+1)%M==front，判空front==rear，并且补一句「若改用 size 计数，则判满为 size==M」。把方案和公式绑在一起记，不要只记公式。

5.3 链队列出队最后一个结点后rear没回退

错在哪：front后移了，rear还指着已经free掉的结点，下一次入队往野指针上挂next，程序偶尔能跑、偶尔崩。为什么错：平时只写出队中间结点的路径，没单独测「队列只剩一个元素」这个边界。怎么答对：出队函数里加一句if (q->rear == p) q->rear = q->front;，并且在报告里明确写出「队列只有一个元素时出队，front 与 rear 同时回到头结点」。这条边界既能防崩，也是答辩必问点。

5.4 随机参数让 ρ 大于 1，结果越跑越大

错在哪：到达间隔平均 3、办理时长平均 6.5，ρ 约 2.17，排队长度随时间线性上涨，平均等待时间跑出几十甚至几百。为什么错：把随机函数当成随便填的数字，没有先算服务强度。怎么答对：动手之前先算 ρ，保证小于 1，比如间隔 1~5、时长 1~4，ρ 约 0.83。答辩时主动说明「ρ≥1 时系统不稳定，不存在稳态平均等待」，这句话能把一个 bug 变成一个知识点。

5.5 关门时刻的边界处理错，客户数少算

错在哪：循环条件写成「时间超过关门时间就退出」，队列里还排着的人被直接丢弃，平均等待被系统性低估。为什么错：把「不再进人」误当成「不再办事」。怎么答对：循环终止条件只认「事件表为空」，关门只用来阻止生成新的到达事件。同时统计一下退出时队列剩余人数，如果剩余很多，说明参数设置有问题，要么是 ρ 太接近 1，要么是营业时长太短。

6. 交卷前走完这三步：让作业能跑，也能被追问

从空白文件到能交的作业，我的顺序是固定的三步。第一步只写数据结构，队列和事件表各自单独测一遍，用小MAXSIZE把指针绕回、队满、出队最后一个元素三种情况各跑一次，打印front、rear确认符合预期。这一步看着慢，但它把后面所有排错的范围都缩小了。

第二步接上事件循环，但先关掉随机数，用手工固定的到达序列和服务时长跑一遍，拿计算器手算平均等待，对不上就停下查。手算的那一组数据要留在报告里，它是你唯一能证明「程序算对了」的证据。第三步才打开随机数，跑五组不同参数，把客户数、平均等待、最大等待、队列剩余四项填进一张表。

表格里任何一项打不了勾，就不算写完。尤其是参数合理性和边界处理这两行，它们是区分「能跑」和「答得对」的分界线。

从那以后我每次交这类模拟作业，都会先在纸上把四个时间量和 ρ 算清楚，再动手写代码，最后强制走一遍上面那张表——六项全勾上才交。这套流程救过我不止一次，包括那次差点把等待时间写成逗留时间、被自己手算的那组数据当场抓出来的经历。希望帮到你。

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