当前位置：首页 > news >正文

实验3：栈、队列与递归

news 2026/6/22 23:12:41

集美大学课程实验报告-实验3：栈、队列与递归

项目名称	内容
课程名称	数据结构
班级	网安2511
学号	202521336001
实验项目名称	栈和队列
上机实践日期	2026.04.05
上机实践时间	2学时

一、目的（本次实验所涉及并要求掌握的知识点）

掌握STL中string的使用
熟练掌握STL中栈(stack)和队列(queue)的基本使用
掌握栈和队列的一些典型应用

二、实验内容与设计思想

题目1：栈的应用(符号配对)

函数相关伪代码

getline整行输入string类型的s
定义栈node
循环：
{char c=s[i]if (c找到'(','[','{'){node.push()}else if(c找到')',']','}'){判断：if(node.empty){栈内没有匹配的符号，输出no并跳出循环}取栈顶元素top，为找到配对,cout<<top并cout<<no若匹配，弹出栈顶元素node.pop()}
}
if(node.empty){全部匹配成功并弹出，cout<<yes;}else//失败{cout<<top<<endl;cout<<no;}

函数代码

#include <iostream>
#include <string>
#include <stack>
using namespace std;int main() {string s;getline(cin, s);stack<char> node;for (size_t i = 0; i < s.length(); i++) {char c = s[i];if (c == '(' || c == '[' || c == '{') {node.push(c);}else if (c == ')' || c == ']' || c == '}') {if (node.empty()) {cout << "no" << endl;return 0;}char top = node.top();node.pop();if ((c == ')' && top != '(') ||(c == ']' && top != '[') ||(c == '}' && top != '{')) {cout << top << endl;cout << "no" << endl;return 0;}}}if (node.empty()) {cout << "yes" << endl;} else {char top = node.top();cout << top << endl;cout << "no" << endl;}return 0;
}

题目2：队列的应用(银行业务队列)

函数相关伪代码

// 初始化两个队列，分别存储A窗口和B窗口的顾客
创建队列A  
创建队列B  
读取输入：第一个数为N，后面N个数为顾客编号序列  
遍历顾客编号序列：  如果编号为奇数，加入队列A  否则，加入队列B  初始化结果列表result  
循环直到A和B都为空：  // 处理A窗口的业务（速度是B的2倍，即每轮先处理A的两个顾客，再处理B的一个）  如果A不为空：  取出A的第一个顾客，加入result  如果A不为空：  取出A的第一个顾客，加入result  如果B不为空：  取出B的第一个顾客，加入result  // 当两个窗口同时处理完（A处理2个，B处理1个）时，A的优先级更高已在上面的顺序保证（先处理A的两个）  输出result中的顾客编号，用空格分隔（最后一个无多余空格）

函数代码

#include <iostream>
#include <queue>
#include <vector>using namespace std;int main() {int n;cin >> n;queue<int> queue_a, queue_b;for (int i = 0; i < n; i++) {int customer;cin >> customer;if (customer % 2 == 1) {queue_a.push(customer);  // 奇数去A窗口} else {queue_b.push(customer);  // 偶数去B窗口}}vector<int> result;while (!queue_a.empty() || !queue_b.empty()) {if (!queue_a.empty()) {result.push_back(queue_a.front());queue_a.pop();if (!queue_a.empty()) {result.push_back(queue_a.front());queue_a.pop();}}if (!queue_b.empty()) {result.push_back(queue_b.front());queue_b.pop();}}for (int i = 0; i < result.size(); i++) {if (i > 0) {cout << " ";}cout << result[i];}cout << endl;return 0;
}

三、实验使用环境（本次实验所使用的平台和相关软件）

操作系统：Windows 10 专业版
编程语言：C++
开发工具：Visual Studio 2022
编译器：VS2022

四、实验步骤和调试过程（实验步骤、测试数据设计、测试结果分析）

题目1：符号配对

本机运行截图

PTA提交截图

题目2：银行业务队列

本机运行截图

PTA提交截图

五、实验小结（实验中遇到的问题及解决过程、实验体会和收获）

遇到的问题及解决方法：

问题：程序崩溃找不到原因
- 解决方法：使用打断点进行调试的方法。
问题：未检查队列是否为空，直接调用 queue.front()或 queue.pop()
- 解决方法：在调用 front()/pop()前，必须通过 !queue.empty()判空；处理 A 窗口的“取2个元素”逻辑时，拆分为“先取1个（判空）→ 再取1个（再次判空）”。