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

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

news 2026/6/5 15:46:58

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

项目名称	内容
课程名称	数据结构
班级	网安 2512
学号	202521336054
实验项目名称	栈和队列的使用
上机实践日期	4月2日
上机实践时间	2学时

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

掌握栈的“后进先出”特性,掌握队列的“先进先出”特性
理解递归与栈的关系,并掌握用栈将递归转化为非递归的基本方法
掌握 C++ 中 stack 与 queue 的基本操作

二、实验内容与设计思想

题目1：栈的应用

函数相关伪代码

函数 ismatch(a, b):如果 (a=='(' 且 b==')') 或 (a=='[' 且 b==']') 或 (a=='{' 且 b=='}'):返回 真否则:返回 假主函数:初始化一个空栈 st读入一行字符串 line对于 line 中的每个字符 c:如果 c 是 '(' 或 '[' 或 '{':把 c 压入栈 st否则如果 c 是 ')' 或 ']' 或 '}':如果 栈 st 是空的:输出 "no"程序结束否则:获取栈顶元素 top = st.top()如果 ismatch(top, c) 为真:弹出栈顶元素否则:输出 top输出换行输出 "no"程序结束如果 栈 st 是空的:输出 "yes"否则:输出栈顶元素输出换行输出 "no"

函数代码

//DD符号配对,记住"" 字符串字面量,''才是字符
#include<iostream>
#include<stack>using namespace std;bool ismatch(char a,char b);int main(){stack<char>st;string line;getline(cin,line);for(char c:line){if(c=='('||c=='['||c=='{'){st.push(c);//1.1}else if(c==')'||c==']'||c=='}'){if(st.empty()){//2.1记得考虑如果为空,则就只有右符号,铁定不行cout<<"no";//此时no不是单个字符要用""return 0;}else{if(ismatch(st.top(),c)){st.pop();//2.2.1将存放的括号因匹配而出栈}else{//2.2.2此时就直接匹配失败结束掉cout<<st.top()<<endl<<"no";return 0;}}}}//3.1,3.2还要考虑,是否真的栈内有左符号的情况if(st.empty()){cout<<"yes";//3.1直接成功,没有残留的左符号}else{cout<<st.top()<<endl<<"no";//3.2,有残留的左符号}return 0;
}
bool ismatch(char a,char b){return((a=='('&&b==')')||(a=='{'&&b=='}')||(a=='['&&b==']'));
}

题目2：递归程序编写

函数相关伪代码

主函数:初始化一个空栈 st整数 sum// 第一阶段：读入直到遇到 0循环:读入 x如果 x == 0:sum = 0输出 sum跳出循环否则:把 x 压入栈 st// 第二阶段：回溯累加当 栈 st 非空时:sum = sum + 栈顶元素(st)弹出栈顶元素输出 sum

函数代码

#include<iostream>
#include<stack>
using namespace std;
int main(){stack<int>st;int sum;while(1){int x;cin>>x;if(x==0){sum = 0;cout<<sum;//基准条件输出,必须需要break;}else{st.push(x);}}while(!st.empty()){//初始就入一个0的话没入栈不影响sum = sum +st.top();//栈用top,队列用frontcout<<sum;st.pop();}return 0;
}

题目3：队列的应用

函数相关伪代码

主函数:初始化两个队列 A、B读入 N// 分配顾客循环 i = 1 到 N:读入 id如果 id 是奇数:id 入队 A否则:id 入队 Bfirst = true// 输出顺序当 队列 A 非空 或 队列 B 非空时:如果 队列 A 非空:如果 first 为真:first = false否则:输出一个空格输出 A 的队首元素A 出队如果 队列 A 非空:输出一个空格输出 A 的队首元素A 出队如果 队列 B 非空:如果 first 为真:first = false否则:输出一个空格输出 B 的队首元素B 出队

函数代码

//DD队列的应用
#include<iostream>
#include<queue>
using namespace std;int main(){queue<int>A,B;int N;cin>>N;for(int i=1;i<=N;i++){int id;cin>>id;if(id%2==1){A.push(id);}else{B.push(id);}}bool first = true;while(!A.empty()||!B.empty()){//记住这个if(!A.empty()){if(first){first = false;}else{cout<<" ";}cout<<A.front();A.pop();}if(!A.empty()){cout<<" "<<A.front();//<<别少写A.pop();}if(!B.empty()){if(first){first = false;}else{cout<<" ";}cout<<B.front();B.pop();}}return 0;
}