【Stack】C++ stack的基本使用方法与经典例题

栈的定义

栈是一个后进先出表(LIFO,last in first out)

可以想象成一个弹夹

可以用数组手动实现，但这里主要介绍用STL的实现方式

C++ STL stack的基本使用方法

#include <stack> //头文件
stack<int> mystack; //声明
mystack.push(x); //压栈
mystack.pop(); //弹栈
mystack.top(); //访问栈顶元素
mystack.size(); //访问栈元素个数
mystack.empty(); //判断栈是否为空

C++ STL stack的使用注意事项

1.pop函数没有返回值，只会弹栈

2.top和pop函数在栈为空时是非法的

3.栈不能随机访问元素

经典例题

1.程序员输入问题

题目描述

程序员输入程序出现差错时，可以采取以下的补救措施：
1.按错了一个键时，可以补按一个退格符“#”，以表示前一个字符无效；
2.发现当前一行有错，可以按一个退行符“@”，以表示“@”与前一个换行符之间的字符全部无效。

分析

1.退格：直接pop

2.退行：手动清空栈

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, x;
string s;
stack<char> sk, ans;
signed main() {
	getline(cin, s);
	for(auto c : s)
		if(c == '#') sk.pop(); //退格
		else if(c != '@') sk.push(c); //压入一个字符
		else while(!sk.empty()) sk.pop(); //清空
	while(!sk.empty())
		ans.push(sk.top()), sk.pop();
	while(!ans.empty())
		cout << ans.top(), ans.pop();
    //将栈反向输出
	return 0;
}

2.括号匹配

题目描述

给定一个由 '(' 和 ')' 括号组成的字符串 S，我们需要添加最少的括号 '(' 或是 ')'，可以在任何位置，以使得到的括号字符串有效。
从形式上讲，只有满足下面几点之一，括号字符串才是有效的：
它是一个空字符串，或者它可以被写成 AB（A 与 B 连接），其中A 和 B 都是有效字符串，或者它可以被写作 (A)，其中 A 是有效字符串。
给定一个括号字符串，返回为使结果字符串有效而必须添加的最少括号数。

分析

这题比较简单，主要细节看代码

代码

#include <bits/stdc++.h>
using namespace std;
string s;
stack<int> sk;
int main() {
	cin >> s;
	for(int i = 0; s[i]; i++) {
		if(s[i] == '(') sk.push('(');
		if(s[i] == ')') {
			bool f = 1;
			if(!sk.empty())
				if(sk.top() == '(') f = 0, sk.pop();
			if(f) sk.push(')');
		}
	}
	cout << sk.size();
	return 0;
}

3.后缀表达式

题目描述

所谓后缀表达式是指这样的一个表达式：式中不再引用括号，运算符号放在两个运算对象之后，所有计算按运算符号出现的顺序，严格地由左而右新进行（不用考虑运算符的优先级）。

如：3*(5+2)+7对应的后缀表达式为："3 5 2 + * 7 +"。

现在给你一个只包含 + * 与一位正整数的后缀表达式串，请你求出该后缀表达式的值的个位。

分析

若字符为数字，则压栈

若字符为符号，则取出数字计算再压栈

代码

#include <bits/stdc++.h>
using namespace std;
string s;
stack<int> sk;
int main() {
	cin >> s;
	for(int i = 0; i < s.length(); i++) {
		char c = s[i];
		if(c >= '0' && c <= '9') sk.push(c - '0');
		if(c == '+') {
			int x = sk.top();
			sk.pop();
			int y = sk.top();
			sk.pop();
			sk.push((x + y) % 10);
		}
		if(c == '*') {
			int x = sk.top();
			sk.pop();
			int y = sk.top();
			sk.pop();
			sk.push((x * y) % 10);
		}
	}
	cout << sk.top() << endl;
	return 0;
}

最后

以上就是动听音响为你收集整理的【Stack】C++ stack的基本使用方法与经典例题的全部内容，希望文章能够帮你解决【Stack】C++ stack的基本使用方法与经典例题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。