集美大学课程实验报告-实验3：栈、队列与递归
| 项目名称 | 内容 |
|---|---|
| 课程名称 | 数据结构 |
| 班级 | 网安2512 |
| 学号 | 202521336042 |
| 实验项目名称 | 实验3.栈和队列 |
| 上机实践日期 | 2026.4.2 |
| 上机实践时间 | 2学时 |
一、目的（本次实验所涉及并要求掌握的知识点）
1.掌握STL中栈和队列的基本存储结构
2.掌握STL中string的使用
3.熟练掌握栈(stack)和队列(queue)的基本使用
4.掌握栈和队列的一些典型应用
二、实验内容与设计思想
题目1：符号配对
主要内容
编写程序检查 C 语言源程序中的四类符号是否正确配对
函数相关伪代码
初始化栈 stack
遍历每一行输入，直到读到一行只有 "."：遍历该行每个字符 c：如果 c 是 '/' 且下一个是 '*'：将 "/*" 入栈，跳过下一个字符如果 c 是 '*' 且下一个是 '/'：{如果栈为空：记录错误：缺少左符号，是 */如果栈顶不是 /*：记录错误：栈顶与 */ 不匹配结束}否则出栈跳过下一个字符如果 c 是 ( [ { 之一：将 c 入栈如果 c 是 ) ] } 之一：{如果栈为空：记录错误：缺少左符号，是 c结束取出栈顶 top如果 top 和 c 不匹配：记录错误：top 缺少右符号结束}否则出栈
遍历结束后：如果栈不为空：输出 NO，栈顶-?如果没有错误：输出 YES否则：输出 NO，按错误类型输出
函数代码
while (getline(cin, line)) {if (line == ".") break;int n = line.size();for (int i = 0; i < n; ++i) {if (err) break;if (i < n-1 && line[i] == '/' && line[i+1] == '*') {st.push("/*");i++;}else if (i < n-1 && line[i] == '*' && line[i+1] == '/') {if (st.empty()) {err = true;firstErr = "?-*/";} else if (st.top() != "/*") {err = true;firstErr = st.top() + "-?";} else {st.pop();}i++;}else if (line[i] == '(' || line[i] == '[' || line[i] == '{') {st.push(string(1, line[i]));}else if (line[i] == ')' || line[i] == ']' || line[i] == '}') {char c = line[i];if (st.empty()) {err = true;firstErr = "?-" + string(1, c);} else {string top = st.top();bool match = (top == "(" && c == ')') ||(top == "[" && c == ']') ||(top == "{" && c == '}');if (!match) {err = true;firstErr = top + "-?";} else {st.pop();}}}}}if (!err) {if (!st.empty()) {err = true;firstErr = st.top() + "-?";}}
函数的时间复杂度、空间复杂度
时间复杂度：O(n);空间复杂度：O(n)
题目2：使用stack将以下递归程序转化为非递归程序
主要内容
利用stack把递归程序转换为非递归程序
函数相关伪代码
函数 test_nonrecursive()初始化栈S；循环读入x；if（ x != 0）x入栈;else跳出循环;sum = 0;当栈不为空时:取出栈顶 xsum = sum + x输出 sum
函数代码
#include <iostream>
#include <stack>
using namespace std;void test_nonrecursive() {stack<int> st;int x;while (cin >> x) {if (x == 0) break;st.push(x);}int sum = 0;while (!st.empty()) {int top_x = st.top();st.pop();sum += top_x;cout << sum;}
}int main() {test_nonrecursive();return 0;
}
函数的时间复杂度、空间复杂度
时间复杂度：O(n);空间复杂度：O(n)
题目3：银行业务队列简单模拟
主要内容
奇数顾客 → A窗口,偶数顾客 → B窗口,按业务完成顺序输出顾客编号。同时完成时，A 优先。
函数相关伪代码
输入 n 和 n 个顾客编号创建队列 A, Bfor 每个顾客编号 x:if x 是奇数:入队 A;else:入队 Bwhile A 不为空 或 B 不为空:if A 不为空:输出 A 队首，出队 Aif A 不为空:输出 A 队首，出队 Aif B 不为空:输出 B 队首，出队 B
函数代码
bool first = true;
while (!A.empty() || !B.empty())
{if (!A.empty()){if (!first) cout << " ";cout << A.front(); A.pop();first = false;}if (!A.empty()){if (!first) cout << " ";cout << A.front(); A.pop();first = false;}if (!B.empty()){if (!first) cout << " ";cout << B.front(); B.pop();first = false;}
}
函数的时间复杂度、空间复杂度
时间复杂度：O(n);空间复杂度：O(n)
三、实验使用环境（本次实验所使用的平台和相关软件）
以下请根据实际情况编写
- 操作系统：Windows10专业版
- 编程语言：C++
- 开发工具：Visual Studio Community 2026
- 编译器：Markdown
四、实验步骤和调试过程（实验步骤、测试数据设计、测试结果分析）
题目1：符号配对
Visual Studio运行截图
PTA截图
题目2：使用stack将以下递归程序转化为非递归程序
Visual Studio运行截图
运行截图
题目3：银行业务队列简单模拟
Visual Studio运行截图
PTA截图
五、实验小结（实验中遇到的问题及解决过程、实验体会和收获）
遇到的问题及解决方法：
- 问题：栈 / 队列判空判满条件写错
- 解决方法：对照课本结构定义，重新确认栈顶指针、队头队尾指针的初始值和变化规则。
- 问题：递归函数死循环
- 解决方法：给递归加上正确的递归出口（如 n=0 或 n=1 返回 1）。
实验体会和收获：
- 掌握了栈的基本操作入栈、出栈，并能完成数制转换。
- 掌握了递归的编写思路，理解递归调用过程。
六、附件（参考文献和相关资料）
以下请根据实际情况编写
- C++ Primer
- 实验3-栈与队列
- 相关博客文章