大学课堂学习
一.目的
掌握STL中stack与queue的使用
string的使用
掌握栈与队列的应用
理解递归函数的编写
函调用与栈的关系
二.任务要求
1.栈的应用(以数值转换为例)
其代码
include
include
include
using namespace std;
int main() {
string s;
getline(cin, s); // 读取一行输入
stack
for (char c : s) {if (c == '(') {st.push(c); // 左括号入栈} else if (c == ')') { // 遇到右括号if (st.empty()) { // 栈空，无左括号匹配cout << "no" << endl;return 0;}char top = st.top();if (top == '(') { // 匹配成功st.pop();} else { // 不匹配，输出栈顶+nocout << top << endl;cout << "no" << endl;return 0;}}
}// 遍历结束，检查栈是否为空
if (st.empty()) {cout << "YES" << endl;
}
else {// 栈非空，输出剩余左括号+nocout << st.top() << endl;cout << "no" << endl;
}return 0;
}
2.递归编程编写
include
include
using namespace std;
// 栈帧：标记当前执行状态，存储x值
struct StackFrame {
int state; // 0: 未执行递归调用 1: 递归调用已返回
int x; // 存储当前读取的x
StackFrame(int s, int val) : state(s), x(val) {}
};
void test(int &sum) {
stack
int x;
// 初始入栈：模拟第一次调用test
st.emplace(0, 0);while (!st.empty()) {auto &frame = st.top();if (frame.state == 0) {// 状态0：执行递归调用前的逻辑（读x）cin >> x;frame.x = x;if (x == 0) {sum = 0;cout << sum;st.pop(); // 直接出栈，无递归} else {frame.state = 1; // 标记为“待执行返回后逻辑”st.emplace(0, 0); // 入栈模拟递归调用}} else {// 状态1：执行递归返回后的逻辑（sum += x，输出）sum += frame.x;cout << sum;st.pop();}
}
}
int main() {
int sum = 0;
test(sum);
return 0;
}
3.队列的应用(以银行业务队列简单模拟)
include
include
using namespace std;
int main() {
queue
int N, num;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> num;
if (num % 2 == 1)
qA.push(num);
else
qB.push(num);
}
bool first = true;
while (!qA.empty() || !qB.empty()) {
int cnt = 0;
while (!qA.empty() && cnt < 2) {
if (!first) cout << " ";
first = false;
cout << qA.front();
qA.pop();
cnt++;
}
if (!qB.empty())
{
if (!first) cout << " ";
first = false;
cout << qB.front();
qB.pop();
}
}
return 0;
}
4.走迷宫
include
include
include
include
using namespace std;
// 坐标结构体
struct Point {
int x, y;
Point(int x_ = 0, int y_ = 0) : x(x_), y(y_) {}
bool operator==(const Point& other) const {
return x == other.x && y == other.y;
}
};
// 方向数组：上、右、下、左
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
// 迷宫大小（对应你图中的8行9列）
const int ROW = 8;
const int COL = 9;
// 迷宫地图：1=墙(棕色)，0=通路(白色)
int maze[ROW][COL] = {
{1, 0, 0, 1, 0, 0, 1, 0, 1},
{1, 0, 1, 1, 0, 0, 1, 0, 1},
{1, 0, 0, 0, 0, 1, 1, 0, 1},
{1, 1, 1, 1, 0, 0, 0, 0, 1},
{1, 0, 0, 0, 1, 0, 0, 0, 1},
{1, 0, 1, 0, 0, 0, 1, 0, 1},
{1, 1, 1, 1, 0, 1, 1, 0, 1},
{1, 0, 0, 0, 0, 1, 0, 0, 1}
};
// 访问标记数组
bool visited[ROW][COL] = {false};
// 栈实现DFS迷宫求解
stack
stack
path.push(start);
visited[start.x][start.y] = true;
while (!path.empty()) {Point curr = path.top();// 到达终点if (curr == end) {return path;}bool hasNext = false;// 遍历四个方向for (int i = 0; i < 4; ++i) {int nx = curr.x + dx[i];int ny = curr.y + dy[i];// 检查边界、是否为墙、是否已访问if (nx >= 0 && nx < ROW && ny >= 0 && ny < COL && maze[nx][ny] == 0 && !visited[nx][ny]) {visited[nx][ny] = true;path.push(Point(nx, ny));hasNext = true;break;}}// 无可用方向，回溯（出栈）if (!hasNext) {path.pop();}
}return stack<Point>(); // 无通路，返回空栈
}
// 打印迷宫
void printMaze() {
cout << "迷宫地图（1=墙，0=通路）：" << endl;
for (int i = 0; i < ROW; ++i) {
for (int j = 0; j < COL; ++j) {
cout << maze[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
// 打印路径
void printPath(stack
if (path.empty()) {
cout << "无通路！" << endl;
return;
}
vector<Point> vec;
while (!path.empty()) {vec.push_back(path.top());path.pop();
}
reverse(vec.begin(), vec.end());cout << "找到通路，路径坐标（行,列，从0开始）：" << endl;
for (size_t i = 0; i < vec.size(); ++i) {cout << "(" << vec[i].x << "," << vec[i].y << ")";if (i != vec.size() - 1) cout << " → ";
}
cout << endl << endl;// 可视化路径（*代表路径）
cout << "路径可视化：" << endl;
vector<vector<char>> show(ROW, vector<char>(COL, '■')); // ■代表墙
for (int i = 0; i < ROW; ++i) {for (int j = 0; j < COL; ++j) {if (maze[i][j] == 0) show[i][j] = '□'; // □代表通路}
}
for (auto& p : vec) {show[p.x][p.y] = '*'; // *代表路径
}
for (int i = 0; i < ROW; ++i) {for (int j = 0; j < COL; ++j) {cout << setw(2) << show[i][j];}cout << endl;
}
}
int main() {
// 起点：(0,1)（对应你图中左上角入口）
// 终点：(7,7)（对应你图中右下角出口）
Point start(0, 1);
Point end(7, 7);
printMaze();
stack<Point> path = solveMaze(start, end);
printPath(path);return 0;
}
时间复杂度：O(ROW×COL)，每个格子最多访问一次
空间复杂度：O(ROW×COL)，栈最多存储所有通路格子
三. 实验使用环境
Visual Studio 2022
五、实验小结
学习搭子真的很重要，有意者私聊（qq 702599337）