目标
实现一个"超市收银"离散模拟系统：N 个收银台各有一条顾客队列，顾客到达后选择一条队列排队，收银员按 FIFO（First In First Out，先进先出） 依次服务。本 Lab 是队列这一节的大综合，要求你把队列、实体建模、选队策略、离散时间推进与统计五个工程能力整合进同一个系统。
容器范围
与 Lab 02-11（可撤销浏览器 = 纯栈）、Lab 02-13（停车场管理 = 栈 + 队列联动）并列，本 Lab 只使用队列（必要时可用数组或链表实现），不使用栈、优先队列、树或哈希表，确保考察点落在队列上。
背景阐述
你为一家超市开发收银排队系统。顾客陆续到店结账，每个人都想挑"队伍最短"的收银台排队；收银员则按先来后到依次服务。你要回答一个实际问题：选最短队到底能把平均等待时间压到多低？如果换成"选预计最快完成的队"，会不会更好？
前置知识
- 第 2.2 节队列的 ADT（Abstract Data Type，抽象数据类型）、FIFO 语义、循环队列实现；
- 第 1 章线性表（用于理解队列底层实现）；
- 基本的 C++ 类与对象（
struct/ 类、std::vector）。
建议用时
300～420 分钟（5～7 小时），建议分 3 次提交：先搭队列 + 实体，再做时间步模拟，最后做统计与选队策略对比。
数据结构与模块总览
| 模块 | 数据结构 | 作用 |
|---|---|---|
| 收银台 | Queue<Customer> × N | 每个收银台一条顾客队列，FIFO |
| 顾客 | struct Customer | 编号、到达时刻、服务时长、入队时刻 |
| 收银台状态 | struct Lane | 含服务中顾客的队列 + 队头剩余服务时间 + 已服务人数 + 忙碌计时 |
| 模拟器 | class Supermarket | 驱动时间步、选队、统计 |
关键约束：队列请你自己实现（复用 2.2 的循环队列），暴露 push / pop / front / size / is_empty / is_full 等接口，不要直接用 std::queue。先把输入读入 std::vector<Customer>，再把顾客总数 C 作为每条队列的有效容量上界，保证合法输入不会因容量不足而丢失顾客。若复用 2.2 的“空出一个槽位”实现，底层必须分配 C + 1 个物理槽位；无顾客时仍至少分配 2 个物理槽位。不能把有效容量 C 误传成物理槽位数。
顾客与状态机
每个顾客经历：
ARRIVED（到达）→ 选最短队入队 → WAITING（排队）→ 收银台服务 → DEPARTED（离开）任务
模块一：实体与队列（必做）
实现 Customer、Lane、Queue<Customer> 三个结构。顾客至少含：id（编号）、arrive_time（到达时刻）、service_time（服务时长，≥1）。
模块二：选队策略（必做，核心）
实现 choose_lane()，从 N 个收银台中选一条队列给新到顾客：
- 策略 A（基础）：选
size()最小的队列；队列包含正在服务的队头顾客。若多条并列最小，选编号最小的收银台（保证结果确定、可复现）。 - 策略 B（加分）：选总剩余工作量最小的队列，即“队头剩余服务时间 + 所有等待顾客的服务时长之和”最小。建议在
Lane中增量维护pending_work，入队时加上新顾客的service_time，每完成一个服务时间单位减 1，从而让选队仍为O(N)。
模块三：时间步模拟（必做）
用离散时间步驱动。模拟从时刻 t = 0 开始，每一步处理半开区间 [t, t+1)，循环直到所有顾客都离开：
- 处理到达：把
arrive_time == t的顾客按输入顺序逐个选队并入队；选队时队列包含正在服务的队头顾客； - 启动服务：若某收银台空闲且队列非空，让队头顾客在时刻
t开始服务，并记录start_time = t； - 执行一个时间单位：每个忙碌收银台在
[t, t+1)内完成一个服务单位，remaining_service与pending_work各减 1，忙碌时间加 1； - 若
remaining_service变为 0，则记录depart_time = t + 1，弹出队头并把收银台标记为空闲；下一位顾客最早在下一步开始服务； t加 1，进入下一步。
PROP性质 · 统一时间边界
这个顺序允许时刻 t 到达且遇到空闲收银台的顾客立即在 [t, t+1) 接受服务。所有时间采用同一口径：等待时间 = start_time - arrive_time，逗留时间 = depart_time - arrive_time。
模块四：统计输出（必做）
结束时输出：
- 总顾客数、总等待时间、平均等待时间、平均逗留时间；
- 每个收银台的服务人数、忙碌率（忙碌时间 / 模拟总时间）、最大队列长度；模拟总时间定义为最后一位顾客的
depart_time（模拟固定从 0 开始）； - 全局最大队列长度。
输入输出格式（命令行）
第一行：N（收银台数量，N ≥ 1）
接下来每行：<arrive_time> <service_time>（两个整数，按到达时刻非递减），直到 EOF约定：
arrive_time非递减（若乱序，报错或先排序，二选一并说明）；service_time ≥ 1。
示例输入
2
0 3
0 2
1 1
2 4按上述时间口径，各顾客的关键时刻为：
| 顾客 | 收银台 | 开始服务 | 离开 | 等待 | 逗留 |
|---|---|---|---|---|---|
| 1 | #1 | 0 | 3 | 0 | 3 |
| 2 | #2 | 0 | 2 | 0 | 2 |
| 3 | #1 | 3 | 4 | 2 | 3 |
| 4 | #2 | 2 | 6 | 0 | 4 |
示例输出
===== 模拟结束 =====
总顾客数: 4
总等待时间: 2
平均等待时间: 0.50
总逗留时间: 12
平均逗留时间: 3.00
收银台 #1: 服务 2 人, 忙碌率 66.67%, 最大队列 2
收银台 #2: 服务 2 人, 忙碌率 100.00%, 最大队列 1
全局最大队列长度: 2错误样例测试（必须通过）
程序不得崩溃，必须给出明确错误信息：
| # | 错误场景 | 输入 | 预期行为 |
|---|---|---|---|
| 1 | 收银台数非法 | 0 或 -1 | 提示"收银台数必须 ≥1"，退出 |
| 2 | 服务时长非法 | 3 0 | 提示"服务时长必须 ≥1"，跳过或退出 |
| 3 | 到达时刻乱序 | 5 2 后 3 1 | 提示"到达时刻必须非递减"（或先排序，二选一说明） |
| 4 | 无顾客 | 只有 2 一行 | 输出全 0 统计，不崩溃 |
| 5 | 单个收银台 + 大量顾客 | N=1，连续 100 个顾客 | 正常排队处理，统计正确 |
| 6 | 同一时刻大量到达 | 同一 arrive_time 连来 10 个 | 依次入队，选队正确，不丢人 |
| 7 | 非整数输入 | abc 3 | 提示"输入格式错误"，跳过 |
提示点与易错点
- 统一时间边界：时刻
t先接收到达者，再启动空闲队头，随后执行区间[t, t+1)的服务；完成者在t+1离开。不要混用“时刻”和“时间区间”，否则等待、逗留和忙碌率会同时相差 1。 - 选最短队的确定性：并列最短时必须固定选编号最小的，否则随机化会导致测试结果不可复现。
- 等待 vs 逗留：
等待时间 = 开始服务时刻 − 到达时刻；逗留时间 = 离开时刻 − 到达时刻。别混。 - 忙碌率口径：
忙碌率 = 该收银台执行服务的区间数 / 最后离开时刻。无顾客时总时间为 0，各收银台忙碌率约定为 0，而不是执行除零。 - 空队列取队头：服务前先判断
is_empty()，空队列直接跳过，否则解引用空队头崩溃。 - 队列为何是 FIFO：收银必须"先来先服务"。如果换成栈（后到先服务），公平性被破坏——想一想这是为什么，这正好对照 Lab 02-11 里栈的用武之地。
复杂度分析要求
- 一次
choose_lane()（策略 A）的时间复杂度？与 N 的关系？ - 一个时间步处理全部收银台的时间复杂度？
- 若顾客总数为 C、模拟总步数为 T，整体复杂度？
- 若
Lane增量维护pending_work，策略 B 与策略 A 的渐进复杂度是否相同？如果每次临时遍历队列求和，额外代价又是什么？为什么策略 B 可能缩短平均等待时间？
提交物
- 完整源码，建议目录
labs/chapter-02/project/P-02-02-supermarket-checkout/：queue.h（自实现循环队列）supermarket.h/supermarket.cpp（实体 + 模拟器 + 统计）main.cpp（命令行驱动）
- 运行结果：覆盖示例、错误样例测试表 7 条、验收清单全部场景。
- 设计说明（500～800 字），覆盖"复杂度分析要求"的 4 个问题。
- 单元测试：选队、入队、服务、统计各至少一组正常 + 一组边界用例。
验收标准
加分项（任选 ≥ 1）
- 策略 B 对比：实现"选预计最早完成"，用同一组输入对比两种策略的平均等待时间，给出结论。
- 离散事件驱动：把时间步模拟升级为事件驱动（跳到下一个事件时刻），观察性能差异。
- 多类型顾客：普通顾客 / 会员顾客分队列，会员优先服务。
- 可视化：每个时间步输出一张 ASCII 队列示意图，肉眼核对排队与服务过程。
延伸思考
- 为什么收银必须用队列而不是栈？给出一个具体反例。
- 如果顾客"选最短队"本身也要排队（看到最短队后跑过去要时间），模型该怎么改？这还只是队列吗？
- 真实超市常用"单队列 + 叫号"（所有顾客排一条队，哪个收银台空了就叫下一个）。对比"多队列选最短队"，哪种平均等待更短？为什么？（这指向排队论里 M/M/1 与 M/M/N 的经典结论，可作为查资料加分）