stack为STL中的适配器容器,具有栈的结构特性。对于适配器容器,默认底层容器为deque,在创建stack对象时,也可以指定其他线性容器作为其底层容器。
基本操作:
#include<iostream>
#include<stack> //头文件
#include<vector>
#include<list>
using namespace std;
typedef int datatype;
constexpr auto N = 10;
int main()
{
stack<datatype>stk;//创建stack对象,底层容器为deque,栈中元素类型为datatype
stack < datatype, vector<datatype>>stk1;//创建stack对象,底层容器为vector
stack<datatype, list<datatype>>stk2;//创建stack对象,底层容器为list
//操作
//入栈
stk.push(3);
stk.push(5);
stk.push(2);
//栈中元素个数
cout << stk.size() << endl;
while (!stk.empty()) { //判断不为空
cout << stk.top() << endl; //获取栈顶元素
stk.pop(); //出栈
}
}
栈应用举例:
栈在计算机科学中具有广泛的应用。一个典型的应用是在编译系统中,当调用一个函数时,将函数的参数、地址等相关信息入栈,当函数执行完毕后再出栈。这里采用栈结构来存储函数信息的主要原因是当函数嵌套调用时,根据函数调用先后次序一次入展,当最底层的函数执行完毕后出栈,再调用当前栈顶的函数......直到所有函数都执行完毕。
1.括号匹配
【算法】检查字符串中的括号是否合法
功能:检查字符串stk中的括号是否合法,假设只检查字符串中的四类括号:(,),[,] 。
算法:遍历的时候进行检查,左符号入栈,并记录栈顶元素,当某一次循环时,发现字符可与栈顶元素匹配时(采用排除法的方式发现字符可匹配),将栈顶元素pop,直到循环到最后一个字符。若栈为空,合法;若栈非空,不合法。
#include<iostream>
#include<stack> //头文件
#include<vector>
#include<list>
using namespace std;
typedef int datatype;
constexpr auto N = 10;
bool check_brackets(string str) {
int i=0, sz = str.size();
stack<char>stk;
//遍历的时候进行匹配
for (i = 0; i < sz; i++) {
if (str[i] == '(' || str[i] == '[') //左括号入栈
stk.push(str[i]);
else {
if (str[i] != ')' && str[i] != ']') //跳过非括号字符
continue;
if (stk.empty()) //栈为空,不合法
return false;
char ch = stk.top(); //获取栈顶元素
if (str[i] == ')' && ch != '(' || str[i] == ']' && ch != '[') //栈顶元素与当前括号不匹配,不合法
return false;
stk.pop(); //出栈
}
}
if (!stk.empty()) return false; //栈非空,不合法
return true;
}
int main()
{
string s1="((56565))899(56)";
bool islegitimate =check_brackets(s1);
if (islegitimate)
cout << "合法" << endl;
else
cout << "不合法" << endl;
}
2.算术表达式求值
在算术表达式(假设运算符只有加减乘除)中,由于运算符的优先级不同,再加上括号可以改变运算次序,导致求带括号的算术表达式的值比较复杂。下面用双栈解决该问题。
功能:求带括号的四则混合运算式exp的计算结果。假设操作数都为整数,且括号只有两种:“(”和“)”,并假设算术表达式中的运算符和括号合法。
自己画出入栈出栈的顺序!
#include<iostream>
#include<stack> //头文件
using namespace std;
typedef int datatype;
constexpr auto N = 10;
//处理ops(运算数栈)栈顶op的运算结果:
//从栈opers(操作数栈)中取两个数v1,v,就是那个v op v1的结果并返回
double cal(stack<double>& opers, stack<char>& ops) {
double v=0, v1=0, ret=0;
v1 = opers.top(), opers.pop();//右操作数
v = opers.top(), opers.pop();//左操作数
char op = ops.top(); ops.pop();//运算符
switch (op){
case '+':
ret = v + v1; break;
case '-':
ret = v - v1; break;
case '*':
ret = v * v1; break;
case '/':
if (v1 == 0) exit(0);
ret = v / v1;
break;
default:
cout << "未知符号!" << endl;
break;
}
opers.push(ret); //计算结果入栈
}
double calculate(string exp) {
stack<double>opers; //操作数栈
stack<char>ops; //运算符栈
int i=0, sz = exp.size(), v = 0;
for (i = 0; i < sz; i++) {
if (isdigit(exp[i])) //exp[i]为数字,将其后连续数字组装为一个整数
{
v = exp[i] - '0';
while (++i < sz && isdigit(exp[i])) //将两位及以上的数字表达出来
v = v * 10 + exp[i] - '0';
opers.push(v); //将组装的整数入栈
--i;
}
else if (exp[i] == '(')//exp[i]为左括号,直接加入ops
ops.push(exp[i]);
else if (exp[i] == '*' || exp[i] == '/') //exp[i]为乘除,消除ops栈顶的乘除
{
while (!ops.empty() && (ops.top() == '*' || ops.top() == '/')) //连续两个乘除,先进行前一个的计算
cal(opers, ops);
ops.push(exp[i]);
}
else if (exp[i] == '+' || exp[i] == '-' || exp[i] == ')')//exp[i]为加减或右括号,消除加减乘除
{
while (!ops.empty() && ops.top() != '(') //栈顶若为( ,则无法进行计算,其他符号才能
cal(opers, ops);
if (exp[i] == ')') //当为)时,中间的运算符都已经pop出去了
ops.pop();
else
ops.push(exp[i]);
}
}
while (!ops.empty())
cal(opers, ops);
return opers.top();
}
int main()
{
string s1 = "7-((1+2)*4/5-6)";
cout<<calculate(s1);
}
单调栈:
如果栈中的元素适中严格单调,则称这种有特殊类型的栈为单调栈。从栈顶到栈底单调递增的单调栈为递增栈,反之递减栈。
单调栈对栈的入栈和出栈操作加了一些限制条件,以维护栈的单调性。假设所考虑的数据序列为数组a,在将a中的每一个元素加入单调栈(以递减栈为例)时,依次考虑a的每一个元素a[i],并只执行如下两种类型的操作:
(1)如果栈空或a[i]大于栈顶元素,则a[i]直接入栈。
(2)如果a[i]小于栈顶元素,则出栈,直到a[i]大于栈顶元素或栈空。然后将a[i]入栈。
限定栈只能执行这两类操作能够确保栈中元素递减。
使用单调栈可以处理如下问题:
(1)利用递减栈可以求a[i]左端比a[i]小且离a[i]最近的元素(简称左端第一个比a[i]小的元素);利用递增栈可以求a[i]左端第一个比a[i]大的元素。
(2)利用递减栈可以求 a[i]左端与a[i]相邻且连续比a[i]大的元素个数(简称a[i]左
邻比a[i]大的元素个数);利用递增栈可以求a[i]左邻比a[i]小的元素个数。
【例2-2】给定一个整型数组a[ ]={5,6,2,4,9,7,3},求解如下两个问题:
(1)求a的每一个元素a[i]左端比它小的数中离它最近的数,并输出,如果a[i]左端没有比它小的数,则输出-1。对于上述数组a,结果为{-1,5,-1,2,4,4,2}。
(2)求a的每一个元素a[i]左端比它大的数中与其相邻且连续的数的个数,并输出,如果a[i]的为最左元素或a[i-1]<a[i],则输出0。对于上述数组a,结果为:{0,0,2,0,0,1,3}。
#include<iostream>
#include<stack> //头文件
using namespace std;
typedef int datatype;
constexpr auto N = 10;
//求比他小的靠得最近的数,将一个个情况列出即可
void left_small(int a[], int n) {
stack<int>stk;//递减栈,元素为数组a的元素
for (int i = 0; i < n; i++) {
while (!stk.empty() && a[i] < stk.top())//a[i]小于栈顶元素,出栈
stk.pop();
if (stk.empty()) cout << -1 << " "; //栈为空,a[i]左端不存在比其小的数
else cout << stk.top() << " "; //栈不空,栈顶即为a[i]左端第一个比其小的数
stk.push(a[i]); //a[i]入栈
}
}
//输出数组a的每一个元素的左邻比其大的元素的个数,一定要先满足相邻,再连续
void left_bigger(int a[], int n)
{
stack<int>stk;//递减栈,元素为数组a的元素
for (int i = 0; i < n; i++) {
while (!stk.empty() && a[i] <= a[stk.top()]) //注意后面是下标入栈!!!
stk.pop();
if (stk.empty()) cout << i << " "; //栈为空,a[i]之前的元素都比a[i]大
else cout << i - stk.top() - 1 << " "; //栈不空,a的下标在区间(i,stk.top())中的元素都比a[i]大
stk.push(i);//下标入栈
}
}
int main()
{
int a[] = { 5,6,2,4,9,7,3 };
left_small(a, 7);
cout << endl;
left_bigger(a, 7);
}