栈与队列实战：停车场管理系统数据结构设计详解

简介数据结构大作业停车场管理程序是一份适合高校计算机专业学生参考的课程设计资源围绕停车场车辆进出、车位查询与状态更新等场景综合运用数组、链表、栈、队列、哈希表及二叉树等结构。资源包内共42个文件以cpp源代码、Visual Studio工程文件sln/vcxproj及编译生成的exe、pdb调试信息为主整体压缩包约15.07MB便于直接打开工程查看与运行。已有447人学习下载。这份资料既展示了栈后进先出处理出入场、队列模拟排队等具体实现也包含单链表、循环双链表等多个模块代码可帮助读者理解数据结构如何落地为实际管理逻辑并在调试记录中借鉴常见问题处理方法。通过学习该程序学生能够巩固课堂理论提升项目拆分与代码组织能力也可在此基础上扩展停车场计费、车位引导等功能。1. 需求分析与整体设计思路1.1 停车场业务场景里的数据结构影子我当年第一次看到“停车场管理程序”这个题目第一反应是这不就是一个简单的进进出出的管理吗真正动手才会发现停车场这个场景简直是给栈和队列量身定做的教学案例。题目通常描述成这个样子停车场有一条狭窄的通道最多同时停 N 辆车只能从一端进入、从另一端出去。通道里如果停满了后来的车必须在门外的便道上排队等待等停车场里有车走了便道上的第一辆车才能进入停车场。你仔细想想这个“只能从一端进出”的通道不就是先进后出FILO的结构吗栈。门外那条“先来后到”的便道不就是先进先出FIFO的结构吗队列。再加上车辆进出要收费需要记录入场时间、出场时间、停车时长这又涉及时间处理和计费逻辑。所以这个项目表面上是个管理系统实际上是在让你用代码去模拟两种经典数据结构的协同工作。这也是为什么几乎所有数据结构教材、几乎所有学校的课程设计都会选这道题。它不是让你背栈和队列的定义而是让你在真实场景里用它们。1.2 为什么选栈和队列而不是数组直接硬写有人可能会问我直接用数组加一个状态标记或者用链表随便搞也能实现“停车”和“等待”啊为什么非要用栈和队列说实话对于只有几辆车的小停车场你用数组写也能跑通。但数据结构大作业考察的重点不是“能不能跑”而是“建模是否合理”。用栈来管理停车场本质上是利用了“后进先出”的天然约束——通道里最后进来的车必须最先出去。如果你用数组自由操作就很容易写出“随便找个空位停进去”的逻辑那就和真实停车场的物理约束相违背了。队列那边同理。便道上的车按到达顺序排队先到的车先进停车场这是公平性要求也是业务规则。你用一个普通链表当然也能实现排队但队列这个抽象把“队头出、队尾入”的规则定死了代码结构更清晰出错的概率也更低。所以这道题用栈和队列不是为了炫技而是数据结构和实际业务规则一一对应的自然结果。你在答辩的时候把这个逻辑讲清楚老师通常会比较满意。1.3 模块划分从输入到输出的完整路径动手写代码之前我强烈建议你先画一下程序的模块划分别上来就写 main 函数。停车场管理程序至少应该包含以下几块车辆到达处理判断停车场是否已满不满则入栈满了则入队等待。车辆离开处理找到目标车在栈中的位置把上面的车临时挪走辅助栈目标车出栈并计费再把临时挪走的车挪回来最后从等待队列中放一辆车进来。计费模块根据入场时间和出场时间计算时长按时长收费。显示模块查看停车场当前状态和便道等待状态。这个划分本质上是“一个入口分而治之”。主程序只负责读取指令、解析指令具体逻辑分派给对应函数处理。后面调试的时候你会发现模块化做得越干净定位 bug 越快。当年我就是因为把所有逻辑都堆在 main 里调试到凌晨两点才找到问题。2. 数据结构设计与核心选型2.1 车辆结点信息的设计无论栈还是队列最基本的数据单元是“车辆结点”。我见过很多同学在这里上来就只存一个车牌号到写计费时发现时间信息没地方放又回来改结构体浪费了不少时间。一个设计良好的车辆结点至少应该包含这些信息车牌号字符串或整数建议用字符串兼容性更好有些学校的题目会要求模拟“京A12345”这种格式。入场时间结构体或时间戳记录车辆进入停车场的时刻用于计费。出场时间车辆离开时填充用于计算停车时长。位置信息可选记录车辆在栈中的位置方便显示和查找。C 语言里的结构体可以这样定义typedef struct { char plate[16]; struct tm enter_time; // 入场时间 struct tm leave_time; // 出场时间 int position; // 在停车场内的位置1表示最里面 } CarInfo;如果你觉得 struct tm 操作太麻烦也可以用 time_t 时间戳自 1970 年 1 月 1 日以来的秒数计费时直接做减法得到秒数再换算成小时更简单。课程设计里最怕的就是时间计算出错用 time_t 可以少写很多换算代码。2.2 停车场栈顺序栈还是链栈停车场内部既然是一个栈那实现方式就有两种选择顺序栈数组模拟和链栈链表模拟。我建议优先用顺序栈原因有两个第一停车场容量固定通常题目会给定 N顺序栈天然符合“有限车位”这个业务约束。数组满了就是停车场满了逻辑很直接。第二顺序栈支持随机访问虽然栈理论上只能从栈顶操作但在车辆离开时我们需要在栈中间找到目标车这时顺序栈的数组下标就能派上用场。定义可以长这样#define MAX_CAPACITY 5 // 停车场最大容量 typedef struct { CarInfo data[MAX_CAPACITY]; int top; // 栈顶指针-1表示空栈 } ParkingStack;当然如果老师要求必须用链式结构你也可以实现链栈。链栈的优势是不会溢出只要内存够但“容量满”的判断需要额外用一个计数器稍微繁琐一点。答辩时能说清楚选择的理由就行。2.3 便道队列链队列更稳便道等待区的队列我建议用链队列实现。因为便道理论上长度不限谁也不知道高峰期会有多少车等着顺序队列在数组满之后还要处理“假溢出”问题纯属给自己找麻烦。链队列定义typedef struct QNode { CarInfo data; struct QNode *next; } QNode; typedef struct { QNode *front; // 队头指针 QNode *rear; // 队尾指针 } LinkQueue;链队列的入队操作就是尾插出队操作就是头删代码量不大但很考察链表基本功。你写完之后如果发现队头队尾指针总是指错说明你对链表指针的理解还需要加强。2.4 辅助栈这个题目的隐藏考点停车场程序里最精妙的地方也是很多同学卡壳的地方是车辆离开时如何处理挡路的车。假设停车场里从里到外停着三辆车A最里面、B中间、C最外面。现在 B 要离开但 B 外面还有 C 挡着怎么办真实场景里C 必须暂时挪出去等 B 开走了C 再倒回来。在程序里这个“暂时挪出去”的行为就是把 C 从停车栈里弹出放到一个临时栈里暂存等 B 出栈后再从临时栈里弹出来重新压回停车栈。这个临时栈就是“辅助栈”。它实现了“把栈顶之外的元素临时移走再按原顺序恢复”的功能。这个操作在数据结构里非常经典很多教材会把它叫做“栈的逆序辅助”或者“暂存栈”。你必须理解这一步的代码逻辑因为这是整个程序的灵魂。每一辆车离开时可能都要经历“弹出挡路车→目标车出栈→压回挡路车→放入等待车”这个流程复杂度为 O(n)但思路必须清晰。3. 关键模块实现与代码细节3.1 车辆到达入栈还是入队就在一念之间车辆到达的处理逻辑是整个程序的入口判断条件很简单停车场满没满。伪代码如下void arrive(LinkQueue *waitQ, ParkingStack *parkStack, CarInfo car) { if (parkStack-top MAX_CAPACITY - 1) { // 停车场未满入栈 parkStack-top; car.position parkStack-top; // 记录位置 parkStack-data[parkStack-top] car; printf(车辆 %s 进入停车场位置 %d\n, car.plate, car.position); } else { // 停车场已满入队等待 enqueue(waitQ, car); printf(停车场已满车辆 %s 进入便道等待\n, car.plate); } }这里有一个小细节车辆入队等待时入场时间应该记录到什么时刻如果是等待的时间那不公平因为等待不算停车。建议在入栈时再记录正式入场时间入队时只记录到达时间用于排队顺序计费时以入栈时间为准。这个规则可以在答辩时主动说明表明你考虑到了业务细节。3.2 车辆离开三步走一步都不能少车辆离开是最容易写崩的地方逻辑顺序很重要。我当年写的时候把“检查目标车是否在栈里”这个步骤放错了位置导致找不到车时直接把栈顶弹出了数据全乱了。后来反复调试才理顺。正确的三步如下第一步遍历停车栈找到目标车的位置 index。从栈底开始找模拟从最里面往外找找到就记录位置。第二步把 index 之上的所有车辆弹出压入辅助栈 tempStack。第三步目标车出栈计算停车费用。第四步把辅助栈中的车辆依次弹出重新压回停车栈。第五步从等待队列中出队一辆车调用入栈逻辑。关键代码如下void depart(ParkingStack *parkStack, ParkingStack *tempStack, LinkQueue *waitQ, char *plate) { int index -1; for (int i 0; i parkStack-top; i) { if (strcmp(parkStack-data[i].plate, plate) 0) { index i; break; } } if (index -1) { printf(未找到车辆 %s请核对车牌号\n, plate); return; } // 把 index 之上的车移到临时栈 while (parkStack-top index) { push(tempStack, pop(parkStack)); } // 目标车出栈并计费 CarInfo leavingCar pop(parkStack); leavingCar.leave_time getCurrentTime(); double fee calculateFee(leavingCar); printf(车辆 %s 停车时长 %.2f 小时费用 %.2f 元\n, leavingCar.plate, leavingCar.leave_time - leavingCar.enter_time, fee); parkStack-top--; // 把临时栈的车移回停车栈 while (!isEmpty(tempStack)) { CarInfo tmp pop(tempStack); tmp.position parkStack-top 1; push(parkStack, tmp); } // 从等待队列放入新车 if (!isEmptyQueue(waitQ)) { CarInfo newCar dequeue(waitQ); newCar.enter_time getCurrentTime(); push(parkStack, newCar); printf(便道车辆 %s 进入停车场\n, newCar.plate); } }这里最需要注意的就是 position 的更新。每次从临时栈弹回停车栈车辆的位置都可能发生变化因为目标车走了后面的车整体往前挪了一位必须重新赋值。很多同学在这里漏掉导致显示的车位信息是错的答辩时一眼就露馅。3.3 计费逻辑时间差换算不简单计费模块看起来最简单其实最容易出边界问题。尤其是跨小时、跨分钟的计算四舍五入规则不同结果能差出不少钱。我建议的计费规则是停车时长按小时计算不足一小时按一小时计。那么费用的计算就是double calculateFee(time_t enter, time_t leave) { double hours difftime(leave, enter) / 3600.0; int billableHours (int)ceil(hours); // 向上取整 double unitPrice 5.0; // 每小时5元 return billableHours * unitPrice; }说到 ceil你必须 include math.h并且编译时链接数学库-lm。很多同学用的 IDE 默认不链接数学库编译报错 undefined reference to ceil然后在群里求半天其实就是少了一个链接参数。另外如果你用 struct tm 表示时间需要先用 mktime() 把 struct tm 转成 time_t再参与运算。直接对 struct tm 做差值是编译不过去的我在初学时就犯过这个错。提示测试计费逻辑时一定要测跨小时边界的情况。比如入场 9:58出场 10:01实际时间差 3 分钟。如果向上取整就是 1 小时如果直接 unsigned 取整就是 0 小时。两种规则都能说得通但你必须明确写注释说明自己的规则不要模棱两可。3.4 命令行交互设计给用户一个简单的入口程序不能只有逻辑没有交互。一个简单又实用的命令行菜单长这样 停车场管理系统 命令格式 A 车牌号 车辆到达 D 车牌号 车辆离开 S 查看停车场状态 E 退出系统 请输入指令主程序用 while(1) 循环读取命令用第一个字符区分不同操作。注意缓冲区问题使用 scanf 读取字符后要清掉多余的换行符否则下一次 getchar 会读到残留的 \n导致命令解析错误。如果你有精力还可以支持文件读写把车位信息保存到文件里下次启动时加载。这是很多课程设计加分的点后面我会单独讲。4. 常见问题与调试经验实录4.1 车辆位置信息错乱症状显示停车场状态时位置编号对不上比如 1 号位是 B 车2 号位是 A 车明显顺序不对。原因车辆离开后把辅助栈的车压回停车栈时没有重新计算 position 字段。解决每次 pop 辅助栈压入停车栈时强制更新 position 为当前位置。可以用 parkStack-top 1 作为新位置压栈之后 top 自增刚好对应。这个 bug 非常隐蔽因为程序不会崩溃只有输出看起来不对劲。建议你在测试时做一张纸手动模拟整个过程把每一步的栈状态画出来对照程序的输出查找问题会快很多。4.2 找不到目标车时误弹栈顶症状输入一个不存在的车牌号程序没有提示“找不到”反而把最外面的车“赶走”了。原因遍历查找目标车时用的是 while (parkStack-top 0) 之类的无条件循环没找到也继续弹栈。解决先通过循环定位目标车的下标如果找不到直接 return不做任何弹栈操作。记住查找和弹出是两件独立的事情不要把它们搅在一起。我把这个 bug 写在这里是因为它太典型了。每年都有同学因为这个问题扣分基本都是同一个原因。4.3 时间差计算错误尤其是跨天场景症状如果车辆早上 8 点入场次日 9 点出场计算出来的费用不对。原因可能你只存储了小时和分钟没有存储日期。只存“8:00”和“次日 9:00”的话程序分不清这个 9 点是当天还是第二天。解决一定要存储完整的日期时间信息。用 struct tm 天然包含年月日时分秒用 time_t 是绝对秒数两种方案都能解决跨天问题。千万不要自创一个只存时分秒的“时间结构体”你会被跨天问题折磨死。测试时故意做一个跨天用例入场 23:50出场 00:10看费用是否按 1 小时计算。这一步跑通了时间模块基本就稳了。4.4 命令行缓冲残留导致的死循环症状输入命令后程序突然不响应或者跳过第一次执行直接循环第二次。原因scanf 读取字符后缓冲区里还有换行符 \n下一次 scanf 或 getchar 读到的是换行而不是有效命令。解决每次 scanf 后用 while (getchar() ! \n); 清空缓冲区或者统一用 fgets 读取整行再解析。我个人推荐 fgets因为它的行为更可控也方便处理车牌号里的空格虽然车牌号一般没有空格。4.5 文件存档与读档如果你的题目没有明确要求这属于加分功能。实现思路很简单退出程序前把停车栈和等待队列中的数据遍历写入文件。启动程序时依次读取文件重新构造栈和队列。这里有个坑写文件时顺序反了会导致恢复的车辆顺序和实际不符。因为栈是后进先出写文件应该从栈底写到栈顶也就是从小下标到大下标读的时候才能按顺序压栈恢复。队列则是从队头写到队尾。想清楚这两个顺序代码其实很好写。5. 测试用例设计和答辩心得5.1 一组能覆盖全部逻辑的测试用例我不建议你随便输入一堆车牌号就算测完。真正高质量的测试要有明确的覆盖目标。下面这组用例是我当年反复用的基本上能把所有分支走一遍序号操作预期结果1A 京A0001入 1 号车位2A 京A0002入 2 号车位3A 京A0003入 3 号车位4A 京A0004入 4 号车位5A 京A0005入 5 号车位停车场满6A 京A0006进入便道等待7D 京A0003弹出 00030004/0005 依次移动便道 0006 入场8D 京A9999提示“未找到车辆”9D 京A0001直接弹出无需移动其他车辆10S显示当前停车栈和队列状态这套用例覆盖了栈满、队列等待、中间出车、队首出车、栈顶出车、查找失败、状态显示七种情况。你要是能把这套用例全部跑通、输出正确程序基本就稳了。5.2 答辩时可以重点讲的两个亮点答辩的时候很多同学只会演示“能跑”但拿不到好分数。我给你指两个加分方向第一个是辅助栈的设计。你可以主动向老师解释车辆离开时用辅助栈暂存挡路的车这个思路体现了“空间换时间”还是“时间换空间”答案是用 O(n) 的辅助空间换取了逻辑的清晰性避免了非顺序移动带来的混乱。这种主动的分析比被动回答问题要好得多。第二个是计费规则的边界处理。你可以说明为什么要向上取整不足一小时按一小时收费这符合真实停车场的习惯。同时说明自己用了 ceil注意到了浮点数精度问题。老师能看出你思考过细节而不是写完了事。5.3 把这个项目扩展成简历项目如果你觉得自己时间充裕这个项目可以继续扩展性价比很高加一个图形界面简单用 EasyX 或 Qt 做一个可视化停车场让车辆进出过程动态展示出来。加一个文件记录功能每次车辆进出都写日志可以实现“历史记录查询”。如果你学了数据库把数据存到 SQLite 里就成了一个真正的管理信息系统了。这些扩展不用太复杂哪怕只做一个小功能简历上写“在数据结构课程项目中实现了基于栈与队列的停车场管理并扩展了日志持久化功能”都比只写“实现了停车场管理”强很多。我在实际做这个项目的时候最大的感受是栈和队列不是花两天背出来的而是花两个晚上一点点调试调出来的。哪一个 bug 让你对着屏幕发呆最久你就把哪一个数据结构理解得最透。停车场这个题目恰恰给你安排了足够多的“发呆时刻”所以恭喜你选了一个特别经典、也特别值得认真对待的题目。做完之后你会发现再遇到“用栈模拟递归”“队列实现 BFS”之类的题目思路会顺畅很多因为你已经知道数据结构不是一堆概念的堆砌而是描述现实业务规则的一门语言。本文还有配套的精品资源点击获取