12.14

数据结构实验1三、7-2 队列应用 (蓝桥杯)

1. 需求分析
   （1）功能需求
   模拟 CLZ 银行两个排队窗口（VIP 窗口、普通窗口）的操作；
   支持 4 种操作：VIP 窗口入队、VIP 窗口出队、普通窗口入队、普通窗口出队；
   执行 M 次操作后，输出两个窗口队列的姓名（从头到尾）。
   （2）输入输出
   输入：M（操作次数，1≤M≤1000）+ M 行操作指令；
   输出：先输出 VIP 窗口队列姓名（空格分隔），再输出普通窗口队列姓名（空格分隔）。
   （3）性能要求
   时间复杂度 O (M)（每个操作 O (1)），空间复杂度 O (M)（存储队列元素）。
2. 总体设计
   （1）核心思路
   采用链式队列实现 VIP 窗口和普通窗口的排队逻辑（链式结构避免数组容量限制）；
   解析每个操作指令，执行对应入队 / 出队操作；
   操作执行完毕后，遍历两个队列输出姓名。
   （2）队列设计
   每个队列节点存储用户姓名，队列结构包含头指针、尾指针，支持入队（尾插）、出队（头删）、遍历输出操作。
3. 详细设计
   （1）数据结构定义
   c
   运行

define NAME_LEN 20 // 姓名最大长度

// 队列节点
typedef struct QNode {
char name[NAME_LEN];
struct QNode *next;
} QNode;
// 链式队列
typedef struct {
QNode *front; // 队头指针
QNode *rear; // 队尾指针
} LinkQueue;
（2）核心函数设计
函数名 函数原型 功能描述 参数说明 返回值
initQueue void initQueue(LinkQueue *q) 初始化队列 q：队列指针 无
isEmptyQueue int isEmptyQueue(LinkQueue *q) 判断队列是否空 q：队列指针 1（空）/0（非空）
enQueue int enQueue(LinkQueue *q, char *name) 入队（尾插） q：队列指针，name：用户姓名 0（成功）/1（失败）
deQueue int deQueue(LinkQueue *q) 出队（头删） q：队列指针 0（成功）/1（失败，队空）
printQueue void printQueue(LinkQueue *q) 遍历输出队列姓名 q：队列指针 无
freeQueue void freeQueue(LinkQueue *q) 释放队列内存 q：队列指针 无
parseOp void parseOp(char *op, LinkQueue *vipQ, LinkQueue *normalQ) 解析操作指令并执行 op：操作字符串，vipQ：VIP 队列，normalQ：普通队列 无
（3）核心逻辑
初始化队列：初始化 VIP 队列和普通队列；
读取操作：读取 M 次操作，逐行解析指令：
“IN name V”：调用enQueue将 name 加入 VIP 队列；
“OUT V”：调用deQueue弹出 VIP 队列队头；
“IN name N”：调用enQueue将 name 加入普通队列；
“OUT N”：调用deQueue弹出普通队列队头；
输出结果：先调用printQueue输出 VIP 队列，再输出普通队列；
内存释放：释放两个队列的所有节点。
4. 测试说明
测试场景 输入 预期输出
基础操作 5
IN Tom V
IN Lily N
OUT V
IN Jack V
OUT N VIP 队列：Jack
普通队列：（空）
空队列出队 2
OUT V
IN Amy N VIP 队列：（空）
普通队列：Amy
多次入队出队 6
IN A V
IN B V
IN C N
OUT V
IN D N
OUT N VIP 队列：B
普通队列：D