栈的模板类与基本应用

一、栈模板类的接口与实现

1.1接口如下：

在这里插入图片描述

1.2接口的数组实现：

原理：因为栈是一种规定了访问方式与存、取方式的线性数据结构，但是归根结底它仍然是一种线性结构，于是我们可以用一种我们所熟知的线性结构来表示它或者是派生它。
实现：
#include <iostream>
using namespace std;

const int maxn = 1e6 + 5;// 如果不用动态内存分配就只能开到 1e5
class Stack{
private: 
	int *data;// 存储栈中整型元素 
	int _top;
public:
	Stack();// 构造函数 
	bool _push(int e);
	bool _pop();
	int top_();
	bool _empty();
};

Stack::Stack(){
	_top = -1;
	data = new int[maxn];
}

bool Stack::_push(int e){
	if(_top == maxn - 1)
		return false;
	data[++_top] = e;
	return true;
}

bool Stack::_pop(){
	if(_top == -1)
		return false;
	_top--;
	return true;
}

bool Stack::_empty(){
	return -1 == _top;
}

int Stack::top_(){
	return data[_top];
} 

int main(){
	Stack s;// 用自己写的栈完成进制转换 
	int pre;
	cin >> pre;
	while(pre){
		s._push(pre % 2);
		pre /= 2;
	} 
	while(!s._empty()){
		cout << s.top_();
		s._pop();
	}
	return 0;
}
这里是用数组实现的，栈模板类的C++语言实现，用到了面向对象，下次给大家总结了向量和链表之后，再用向量派生的方法来实现栈模板吧

1.3提出问题：

① STL里使用栈模板类容器和手写栈的优劣比较：
STL的栈模板类容器：

使用了重载，可以容纳各种类型的元素入栈，如果是在处理需要把某个结构体入栈的时候，就只能选择使用C++自带的栈模板

手写栈模板类：

C++自带的栈模板存储能力有限，如果出现了栈溢出的现象，手工写栈就是一种解决问题的办法！

② 在上面我给出的一个栈模板类实现中，如果把maxn再扩大十倍，也会爆栈！请各位思考，明明是用数组来实现的，数组在全局变量中开到 1e6 的级别是不会爆炸的，那为何写入栈模板类就支撑不住了呢？
关于开到1e6爆栈的缘由：

全局变量的申请是用堆，那么讲道理，类里面申请空间应该也是堆，但是我们实验发现，类里面不能开大数组，这说明类里面用直接定义数组的方法开辟空间还是在申请栈空间、申请局部内存。但是据某位研究生大佬说，在Linux下可以设置栈无限大：ulimit -s ulimit。但是我们也可以用动态申请内存的方法：在类里面开：int *_data;然后在构造函数里：_data = new int[maxn];

二、栈的基本应用一：倒序输出

其实啊，上述的那个例子，进制转换就是倒序输出的一种
因为进制转换用的是：除K取余法，余数要从下网上输出就是新的进制数，这种后进先出的顺序让我们想到可以用栈去解决！

练习1 ：将一个十进制数，转换成任意进制的数，如果大于9，则用A、B、……代替。
#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;

int main(){
	long long n, m;
	stack<int>s;
	cin >> n >> m;
	while(n){
		s.push(n % m);
		n /= m;
	}
	while(!s.empty()){
		if(s.top() <= 9)
			cout << s.top();
		else
			cout << char(s.top() - 10 + 'A');
		s.pop();
	}
	return 0;
}
练习2 ：在这里插入图片描述

样例输入 & 输出：
在这里插入图片描述
附上参考代码：

#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;

int main(){
	stack<int>s1, s2;
	char opp;
	int x;
	while(cin >> opp){
		if(opp == '1'){
			cin >> x;
			s1.push(x);
			if(s2.empty() || x > s2.top())
				s2.push(x);
		}else if(opp == '2'){
			if(!s1.empty() && !s2.empty()){
				if(s1.top() == s2.top()){
					s1.pop();
					s2.pop();
				}else
					s1.pop();
			}else
				cout << "stack is emptied !" << endl;
		}else if(opp == '3') 
			if(!s1.empty() && !s2.empty())
				cout << s2.top() << endl;
			else
				cout << "stack is emptied !" << endl;
	}
	return 0;
}

三、栈的基本应用2：括号匹配

首先来看看一张括号匹配的图，咱们先一起理解一下：
在这里插入图片描述
那我们有哪些方法可以实现括号匹配呢？

一：用栈：

先给大家一张图便于思考：
在这里插入图片描述
参考代码如下：

#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;

stack <char> s;
string str;
bool check(){
	for(int i = 0;i < str.length();i++){
		if('(' == str[i])
			s.push(str[i]);
		else if(!s.empty())
			s.pop();
		else
			return false;
	}
	return s.empty();
}

int main(){
	cin >> str;
	if(check)
		cout << "YES";
	else
		cout << "NO";
	return 0;
}
反思：如果是多种括号的匹配问题呢？

可否设置多个栈？答案是没用的，多个栈和一个栈是一样的，会有这样的一个反例：[(])
如何解决这个问题呢？我们可以发现除了这种特例之外，其他的匹配问题和一种括号是一模一样的，所以我们可以专门针对这种问题进行特判，代码如下：

#include <iostream>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

stack<char>s;
string str;
bool check2(){
	for(int i = 0;i < str.length();i++){
		if('(' == str[i] || '[' == str[i] || '{' == str[i])
			s.push(str[i]);
		else if(')' == str[i] || ']' == str[i] || '}' == str[i]){
			bool book = true;
			if(')' == str[i] && ('[' ==  str[i - 1] || '{' == str[i - 1]))
				book = false;
			if(']' == str[i] && ('(' == str[i - 1] || '{' == str[i - 1]))
				book = false;
			if('}' == str[i] && ('(' == str[i - 1] || '{' == str[i - 1]))
				book = false;	
			if(s.empty() || !book)
				return false;
			else
				s.pop();
		}
	}
	return s.empty();
}

int main(){
	cin >> str;
	if(check2())
		cout << "YES";
	else
		cout << "NO";
	return 0;
}
二：用一个数字去模拟栈：只能解决一种括号的问题
算法思想：

我们可以把遇到左括号记作：+1，遇到右括号记作：-1

#include <iostream>
using namespace std;

int main(){
	int isRight = 0, book = 0; 
	char ch;
	while(1){
		cin >> ch;
		if(ch == '(')
			isRight++;
		if(ch == ')'){
			isRight--;
			if(isRight < 0)
				break;
		}
	}
	if(isRight)
		cout << "NO";
	else
		cout << "YES";
	return 0;
}

四、后缀表达式的计算

4.1 中缀表达式换算成后缀表达式

我们一般遇到的计算式，都是中缀表达式，比如：1 + 2 * 3 - 4就是一个很显然的中缀表达式
那么，中缀表达式的定义是什么呢？其实就是二叉树的中序遍历得到的节点序列
这里的节点，实际上有两种：①操作数节点，也就是被操作的对象；②操作符节点，也就是大家所熟知的加减乘除，现在我们不妨来用一个中缀表达式还原成一颗二叉树：

举个栗子：3 + 5*2/4 - 6/3

大伙还记得中序遍历吗？离散数学都还给李dong老师了吗？来来来，小良帮你复习一下下：
首先二叉树的中序遍历的顺序是：左 -> 根 -> 右
那么，较高级的运算，就必然是某个子树的根节点
还原如下：
在这里插入图片描述

手画比较丑，画错了记得留言告诉弱鸡小良，小良就马上改！

根据这幅图，我们来走一遍后序遍历：3524/*+63/-
那么如何用栈来实现逆波兰表达式的计算呢？

练习：后缀表达式求值

这个题的样例小良再次手绘模拟一下过程：

在这里插入图片描述
书写代码：

#include <iostream>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

string str;
stack<int>s;

int cal(){
	for(int i = 0;str[i] != '@';i++){
		if('.' == str[i]){
			int cnt = 0, k = 1;
			for(int j = i - 1;j >= 0 && str[j] >= '0' && str[j] <= '9';j--){
				cnt = cnt + (str[j] - '0')*k;
				k *= 10;
			}
			s.push(cnt);
			continue;
		}
		if('0' <= str[i] && str[i] <= '9')
			continue;
		int sum = s.top();
		s.pop();
		if('+' == str[i]){
			sum = s.top() + sum;
			s.pop();
			s.push(sum);
		}else if('-' == str[i]){
			sum = s.top() - sum;
			s.pop();
			s.push(sum);
		}else if('*' == str[i]){
			sum = s.top()*sum;
			s.pop();
			s.push(sum);
		}else if('/' == str[i]){
			sum = s.top()/sum;
			s.pop();
			s.push(sum);
		}
	}
	return s.top();
}

int main(){
	cin >> str;
	cout << cal();
	return 0;
}

再看一道题：

练习：计算中缀表达式的值
算法分析：

这个中缀表达式就需要两个栈：一个操作栈，一个操作数栈
然后，还有一件比较麻烦的事情，就是预处理优先级，因为每个运算的优先级不一样，比如乘除运算要高于加减运算，优先级高的，要先计算。

#include <iostream>
#include <stack>
#include <string>
#include <algorithm>
#define LL long long
using namespace std;

string str;
stack<LL>s_num;
stack<char>s_opp; 

int opp(char ch){
	if(ch == '+' || ch == '-')
		return 1;
	else if(ch == '*' || ch == '/')
		return 2;
}

LL cal(){
	int ans = 0;
	for(int i = 0;i <= str.length();i++){
		if(str[i] == ' ')
			continue;
		if(str[i] < '0' || str[i] > '9'){
			int cnt = 0, k = 1;
			for(int j = i - 1;j >= 0 && str[j] >= '0' && str[j] <= '9';j--){
				cnt += (str[j] - '0')*k;
				k *= 10;
			}
			s_num.push(cnt);
			if(s_opp.empty())
				s_opp.push(str[i]);
			else{
				char op = s_opp.top();
				if(opp(str[i]) <= opp(op)){
					int x = s_num.top();
					s_num.pop();
					int y = s_num.top();
					s_num.pop();
					if(op == '*')
						x = x * y;
					else
						x = x + y;
					s_num.push(x);
					s_opp.pop();// 排出已经处理过的操作符 
					s_opp.push(str[i]);
				}else
					s_opp.push(str[i]);
			}
		}
	}
while(!s_opp.empty() && s_opp.top() != '\0'){
		char ch = s_opp.top();
		int x = s_num.top();
		s_num.pop();
		int y = s_num.top();
		s_num.pop();
		if(ch == '+')
			x += y ;
		else
			x *= y ;
		s_num.push(x);
		s_opp.pop();
	}
	return s_num.top();
}

int main(){
	cin >> str;
	cout << cal();
	return 0;
}

上面这个代码其实是有问题的，不知为何处理不了操作数栈的栈底元素呢？还请大佬们多多指教！
等小良搞清楚了，再来更新本篇博客！

更新啦！更新啦！

上面中缀表达式求值的问题，小良同学后面写了一篇博客，是正确的代码，欢迎大家评论：

栈的综合应用：包括栈混洗和中缀表达式求值（全链式存储！）
# 算法
Logo
AI硬件创业社区

智能硬件社区聚焦AI智能硬件技术生态，汇聚嵌入式AI、物联网硬件开发者，打造交流分享平台，同步全国赛事资讯、开展 OPC 核心人才招募，助力技术落地与开发者成长。

更多推荐

cover

STM32 学习笔记 —— GPIO 入门与点亮 LED

avatar AI硬件创业社区

深入浅出容器技术：从cgroups、namespace到Docker

容器技术的核心在于资源隔离，而Linux的cgroups（控制组）和namespace（命名空间）正是实现这一目标的关键。Docker作为容器技术的代表，简化了应用的打包、分发和运行，但其底层依赖Linux的cgroups和namespace等机制实现资源隔离与限制。本文将带你深入浅出地探索容器技术的核心原理，从基础概念到Docker的实现，帮助你理解这一革命性技术背后的奥秘。从cgroups、n

avatar AI硬件创业社区
cover

STM32-Day10(中断-红外&旋转计次)

avatar AI硬件创业社区