集美大学课程实验报告-实验3—栈与队列
| 项目名称 | 内容 |
|---|---|
| 课程名称 | 数据结构 |
| 班级 | 网安2512 |
| 姓名 | cxy |
| 实验项目名称 | 实验3—栈与队列 |
| 上机实践日期 | 2026.4.2 |
| 上机实践时间 | 2学时 |
一、实验目的（本次实验所涉及并要求掌握的知识点）
-
掌握STL中string的使用
-
熟练掌握STL中栈(stack)和队列(queue)的基本使用
-
掌握栈和队列的一些典型应用
二、实验内容与设计思想
题目1：栈的应用（"数制转换"）。
设计思路：
- 采用除基取余法，将十进制数反复除以目标进制，得到的余数需逆序输出才是结果。（核心原理）
- 使用顺序栈存储余数，利用栈后进先出的特性，实现余数的自动逆序输出。（数据结构选择）
- 定义顺序栈结构，实现栈初始化、判空、入栈、出栈四个基础操作。
- ① 若待转换数为 0，直接输出 0；
② 循环计算余数并入栈，直到商为 0；
③ 依次出栈所有余数并输出，得到目标进制数。
Common.h代码截图
题目2：使用stack将以下递归程序转化为非递归程序
void test(int &sum)
{
int x;
cin>>x;
if (x==0) sum = 0;
else {
test(sum);
sum+=x;
}
cout<<sum;
}
设计思路：
- 设计目的：采用非递归方式，利用栈模拟递归调用，实现读取以0为结束符的整数，先输出0，再倒序累加并逐次输出和。
- 核心原理：借助栈后进先出的特性，存储输入的非 0 数字，模拟递归的回溯过程。
- 执行流程：读取非 0 数字压入栈中，遇到0时初始化累加和并输出0；依次弹栈数字进行累加，每累加一次输出当前结果。
- 算法复杂度：时间复杂度 O(n)，空间复杂度 O(n)。
Common.h代码截图
题目3：队列的应用（"舞伴问题"）
设计思路：
- 数据结构：使用两个循环队列，分别存放男士、女士舞者，利用队列先进先出的特性保证排队顺序。
- 核心流程
遍历所有舞者，男士入男队，女士入女队；
当两队都不为空时，依次从两队队头各出一人配对；
任意一队为空，配对结束。 - 功能实现：完成队列的入队、出队、判空、求长度基础操作，最后输出剩余人员。
Common.h代码截图
三、实验使用环境（本次实验所使用的平台和相关软件）
以下请根据实际情况编写
- 操作系统：Windows 11专业版
- 编程语言：C++
- 开发工具：Visual Studio 2026
四、实验步骤和调试过程
题目1
题目2
题目3
五、实验小结（实验中遇到的问题及解决过程、实验体会和收获）
遇到的问题及解决方法：
题目1
- 问题：输入负数时，N>0循环不执行，无输出
- 解决方法：先取绝对值转换，输出前添加负号
- 问题：N=0仅输出 0 无换行，与其他结果格式不一致。
- 解决方法：输出 0 后添加换行符
题目2
- 问题：使用else if，仅能输出一种性别的剩余人员，逻辑错误。
- 解决方法：改为两个独立if判断，分别输出男、女剩余人数。
- 问题：仅识别大写M/F，小写 / 其他字符直接丢弃，无异常提示。
- 解决方法：增加大小写兼容判断，非法性别给出输入错误提示。
题目3
- 问题：sum 未初始化为 0
- 解决方法：遇 0 时将 sum 置 0，保证计算正确
- 问题：未逐次输出累加和
- 解决方法：每弹栈累加一次，立即输出当前 sum
实验体会和收获：
- 理解了栈后进先出、队列先进先出的本质，明确了两种结构的适用场景
- 合理选择数据结构能高效解决实际问题，体会到算法与数据结构对程序优化的重要性。
六、附件（参考文献和相关资料）
以下请根据实际情况编写
- 实验3-栈与队列