STL详解（二） 栈容器Stack
一、Stack简介
stack 是容器适配器的一种。要使用 stack，必须包含头文件 <stack>。
stack就是“栈”。栈是一种后进先出的元素序列，访问和删除都只能对栈顶的元素（即最后一个被加入栈的元素）进行，并且元素也只能被添加到栈顶。栈内的元素不能访问。如果一定要访问栈内的元素，只能将其上方的元素全部从栈中删除，使之变成栈顶元素才可以。
容器适配器中的数据是以 LIFO 的方式组织的，这和自助餐馆中堆叠的盘子、箱子中的一堆书类似。下图展示了一个理论上的 stack 容器及其一些基本操作。只能访问 stack 顶部的元素；只有在移除 stack 顶部的元素后，才能访问下方的元素。
思考：１、如果进站的车厢序列为１２３，则可能的出站车厢序列是哪些？ 会有312吗？
２、如果进站的车厢序列为123456，问能否得到135426和435612的出站序列？
1.stack对象的默认构造
stack采用模板类实现， stack对象的默认构造形式： stack <T> stkT;
stack <int> stkInt; //一个存放int的stack容器。
stack <float> stkFloat; //一个存放float的stack容器。
stack <string> stkString; //一个存放string的stack容器。
//尖括号内还可以设置指针类型或自定义类型。
二、成员函数详解
１.stack的进栈与出栈方法：（push()与pop()）
- stack.push(elem); //往栈头添加元素
- stack.pop(); //从栈头移除第一个元素
#include<bits/stdc++.h>
using namespace std;
void objPlay2()
{ stack<int> stkInt;
stkInt.push(1); //放进去1
stkInt.push(3); //放进去3
stkInt.pop(); //弹出来一个元素
stkInt.push(5); //放进去5
stkInt.push(7); //放进去7
stkInt.push(9); //放进去9 此时元素就是1,5,7,9
stkInt.pop(); //弹出来一个元素
stkInt.pop();//弹出来一个元素 此时元素就是1,5
}
int main()
{
objPlay2();
return 0;
}
2.stack对象的拷贝构造与赋值
- stack(const stack &stk); //拷贝构造函数
- stack& operator=(const stack &stk); //重载等号操作符
#include<bits/stdc++.h>
using namespace std;
int main()
{ stack<int> stkIntA;
stkIntA.push(1);
stkIntA.push(3);
stkIntA.push(5);
stkIntA.push(7);
stkIntA.push(9);
stack<int> stkIntB(stkIntA); //拷贝构造
stack<int> stkIntC;
stkIntC = stkIntA; //赋值
}
3.stack的数据存取
- stack.top(); //返回最后一个压入栈元素
#include<bits/stdc++.h>
using namespace std;
int main()
{ stack<int> stkIntA;
stkIntA.push(1);
stkIntA.push(3);
stkIntA.push(5);
stkIntA.push(7);
stkIntA.push(9);
int iTop = stkIntA.top(); cout<<iTop; //获取栈顶元素，那就是9，top只是获取栈顶元素，pop是弹出栈顶元素
stkIntA.top() = 19; //19
iTop = stkIntA.top(); cout<<iTop;
}
４.stack的大小
- stack.empty(); //判断堆栈是否为空
- stack.size(); //返回堆栈的大小
#include<bits/stdc++.h>
using namespace std;
int main()
{ int iSize;
stack<int> stkIntA;
stkIntA.push(1);
stkIntA.push(3);
stkIntA.push(5);
stkIntA.push(7);
stkIntA.push(9);
if (!stkIntA.empty())
iSize = stkIntA.size();//5个元素
cout<<iSize;
}
三、stack的应用
1、括号的匹配
【问题描述】
栈在计算机科学领域有着广泛的应用。比如在编译和运行计算机程序的过程中，就需要用栈进行语法检查，如检查 begin 和 end、{ 和 }、（和）等是否匹配。
假设一个表达式只由小写英文字母、运算符（+，-，*，/）和左、右小括号构成，以“@”作为表达式的结束符。
请编程检查表达式中的左、右小括号是否匹配，若匹配，则返回“YES”；否则返回“NO”，不必关心表达式中的其他错误。
2、表达式括号匹配(stack)
【问题描述】
假设一个表达式有英文字母（小写）、运算符（+，—，*，/）和左右小（圆）括号构成，以“@”作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则返回“YES”；否则返回“NO”。表达式长度小于 255，左圆括号少于 20 个。
【输入文件】
输入文件 stack.in 包括一行数据，即表达式，
【输出文件】
输出文件 stack.out 包括一行，即“YES” 或“NO”。
【输入输出样例】
【样例输入 1 】
2*(x+y)/(1-x)@
【样例输出 1 】
YES
【样例输入 2 】
(25+x)*(a*(a+b+b)@
【样例输出 2 】
NO
3、字符串匹配。
字符串中只含有（），{}，[ ]，< >,判断输入的字符串中括号是否匹配。如果括号有互相包含的形式，从内到外必须是（），{}，[ ]，< >,例如：输入[（）]，输出ＹＥＳ，而输入（[ ]）、（[））都应该输出ＮＯ。
输入格式：
第一行１个整数n,表示以下有多少个由括号组成的字符串。
接下来的n行，每行都是一个由括号组成的长度不超过255的字符串。
输出格式：
输出n行，每行都是一个字符串“YES”或“ＮＯ”。
【输入样例】
5
{}{}<><>()()[][]
{{}}{{}}<<>><<>>(())(())[[]][[]]
{{}}{{}}<<>><<>>(())(())[[]][[]]
{<>}{[]}<<<>><<>>>((<>))(())[[(<>)]][[]]
><}{{[]}<<<>><<>>>((<>))(())[[(<>)]][[]]
【输出标例】
YES
YES
YES
YES
NO
4、表达式求值
【题目描述】
给定一个只包含加法和乘法的算术表达式，请编程计算表达式的值。
【输入格式】
输入仅有一行，为计算所需要的表达式，表达式中只包含数字、加法运算符“+”和乘法运算符“*”，且没有括号，所有参与运算的数字均为 0~231 -1 之间的整数。
输入数据保证这一行只有 0~9、+、* 这 12 种字符。
【输出格式】
输出只有一行，包含一个整数，表示这个表达式的值。
注意：当答案长度多于 4 位时，请只输出最后 4 位，前导 0 不输出。
【输入输出样例】
【样例解释】
样例 1 计算的结果为 8，直接输出 8。
样例 2 计算的结果为 1234567891，输出后 4 位，即 7891。
样例 3 计算的结果为 1000000004，输出后 4 位，即 4。
【数据规模】
对于 30% 的数据，0≤表达式中加法运算符和乘法运算符的总数≤100。
对于 80% 的数据，0≤表达式中加法运算符和乘法运算符的总数≤1000。
对于 100% 的数据，0≤表达式中加法运算符和乘法运算符的总数≤100000。
5、编程求一个后缀表达式的值
【问题描述】
从键盘读入一个后缀表达式（字符串），只含有0-9组成的运算数及加（+）、减（—）、乘（*）、除（/）四种运算符。每个运算数之间用一个空格隔开，不需要判断给你的表达式是否合法。以@作为结束标志。
【算法分析】
后缀表达式的处理过程很简单，过程如下：扫描后缀表达式，凡遇操作数则将之压进堆栈，遇运算符则从堆栈中弹出两个操作数进行该运算，将运算结果压栈，然后继续扫描，直到后缀表达式被扫描完毕为止，此时栈底元素即为该后缀表达式的值。
比如，16–9*(4+3)转换成后缀表达式为： 16 9 4 3 +*–，在字符数组A中的形式为：
栈中的变化情况：
思考：Ａ+Ｂ*（Ｃ－Ｄ）－Ｅ/F的后缀表达式是什么？
6 、中缀表达式值(expr)
【问题描述】
输入一个中缀表达式（由 0-9 组成的运算数、加+减—乘*除/四种运算符、左右小括号组成。注意“—”也可作为负数的标志，表达式以“@”作为结束符），判断表达式是否合法，如果不合法，请输出“NO”；否则请把表达式转换成后缀形式，再求出后缀表达式的值并输出。
注意：必须用栈操作，不能直接输出表达式的值。
【输入文件】
输入文件的第一行为一个以@结束的字符串。
【输出文件】
如果表达式不合法，请输出“NO”，要求大写。
如果表达式合法，请输出计算结果。
【输入样例】
1＋2×8―9
【输出样例】
8
7、计算(calc)
【问题描述】
小明在你的帮助下，破密了 Ferrari 设的密码门，正要往前走，突然又出现了一个密码门，门上有一个算式，其中只有“(”，“)”，“0-9”，“+”，“-”，“*”，“/”，“^”，求出的值就是密码。小明数学学得不好，还需你帮他的忙。(“/”用整数除法)
【输入】
输入文件 calc.in 共 1 行，为一个算式。
【输出】
输出文件 calc.out 共 1 行，就是密码。
【输入输出样例】
【输入样例】
1+(3+2)*(7^2+6*9)/(2)
【输出样例】
258
【限制】
100%的数据满足：算式长度<=30 其中所有数据在 2 31 -1 的范围内。
8、排队。
n个人排成一条直线（一排），给出队伍中每个人的身高，每个人只能看到站在他右边且个头比他小没有被其他人挡住的人。请求出所有人可以看到的人数之和。
输入格式：
第１行１个正整数Ｎ，１<=N<=80000。
下面的Ｎ行，每行给出一个正整数h!，表示第i个人的身高。１<=hi<=10的9次方。
输出格式：
一行一个数，表示所有人可以看到的人数之和。
输入样例：
6
10
3
7
4
12
2
输出样例：
５
9、车厢调度(train)
【问题描述】
有一个火车站，铁路如图所示，每辆火车从A 驶入，再从 B 方向驶出，同时它的车厢可以重新组合。假设从 A 方向驶来的火车有 n 节（n<=1000），分别按照顺序编号为 1，2，3，…，n。假定在进入车站前，每节车厢之间都不是连着的，并且它们可以自行移动到 B 处的铁轨上。另外假定车站 C 可以停放任意多节车厢。但是一旦进入车站 C，它就不能再回到 A 方向的铁轨上了，并且一旦当它进入 B 方向的铁轨，它就不能再回到车站 C。负责车厢调度的工作人员需要知道能否使它以 a1,a2,…,an 的顺序从 B 方向驶出，请来判断能否得到指定的车厢顺序。.
【输入】
输入文件的第一行为一个整数 n，其中 n<=1000，表示有 n 节车厢，第二行为 n 个数字，表示指定的车厢顺序。
【输出】
如果可以得到指定的车厢顺序，则输出一个字符串”YES”，否则输出”NO”（注意要大写，不包含引号）。
【输入样例】
5
5 4 3 2 1
【输出样例】
YES
10、火车进站出站问题。
给定一个正整数N代表火车数量，0<N<10，接下来输入火车入站的序列，一共N辆火车，每辆火车以数字1-9编号。要求输出火车出站的***。
解题思路：栈具有先进后出、后进先出的特点，因此，任何一个调度结果应该是1 ，2 ，3 ，4全排列中的一个元素。由于进栈的顺序是由小到大的，所以出栈序列应该满足以下条件：对于序列中的任何一个数其后面所有比它小的数应该是由大到小的，例如4321 是一个有效的出栈序列，1423不是一个有效的出栈结果（4 后面比它小的两个数 2 ，3 不是倒序）。据此，本题可以通过算法产生n 个数的全排列，然后将满足出栈规则的序列输出。
#include<bits/stdc++.h>
using namespace std;
bool Pop(vector<int> pushV,vector<int> popV) {
stack<int> s;
int j=0;
for(int i=0;i<pushV.size()&&j<popV.size();i++)
{ if(pushV[i]!=popV[j])
{ if(!s.empty())
{ if(s.top()!=popV[j])
s.push(pushV[i]);
else
s.pop();
}
else
s.push(pushV[i]);
}
else j++;
}
while(!s.empty())
{ if(s.top()==popV[j++])
s.pop();
else
return false;
}
return true;
}
int main()
{ int n;
cin>>n;
vector<int> v(n);
for(int i=0;i<n;i++)
cin>>v[i];
vector<int> vv=v;
do{
if(Pop(vv,v))
{ for(int i=0;i<n;i++)
{ if(i==n-1)
cout<<v[i]<<endl;
else
cout<<v[i]<<" ";
}
}
}while(next_permutation(v.begin(),v.end()));
return 0;
}依此递归定义，递归算法如下：
#include<bits/stdc++.h>
using namespace std;
int cont=1;
void print(int str[],int n);
void perm(int str[],int k,int n)
{ int i,temp;
if(k==n-1)print(str,n);//k和n-1相等，即一趟递归走完
else
{ for(i=k;i<n;i++)//把当前节点元素与后续节点元素交换
{ temp=str[k]; str[k]=str[i]; str[i]=temp;//交换
perm(str,k+1,n);//把下一个节点元素与后续节点元素交换
temp=str[i]; str[i]=str[k]; str[k]=temp;//恢复原状
}
}
}
/* 本函数判断整数序列 str[] 是否满足进出栈规则, 若满足则输出*/
void print(int str[],int n)
{ int i,j,k,l,m,flag=1,b[2];
for(i=0;i<n;i++) /* 对每个str[i] 判断其后比它小的数是否为降序序列*/
{ m=0;
for(j=i+1;j<n&&flag;j++)
{ if (str[i]>str[j])
{ if (m==0) b[m++]=str[j];//记录str[i]后比它小的数
else //如果之后出现的数比记录的数还大，改变标记变量
{ if (str[j]>b[0]) flag=0;
//否则记录这个更小的数
else b[0]=str[j];
}
}
}
}
if(flag) /* 满足出栈规则则输出 str[] 中的序列*/
{ printf(" %2d:",cont++); //输出序号
for(i=0;i<n;i++)
printf("%d",str[i]);//输出序列
printf("\n");
}
}
int main()
{ int str[100],n,i;
printf("input a int:"); /* 输出排列的元素个数*/
scanf("%d",&n);
for(i=0;i<n;i++) /* 初始化排列集合*/
str[i]=i+1; //第i个节点赋值为i+1
printf("input the result:\n");
perm(str,0,n); //调用递归
printf("\n");
return 0;
}
12、溶液模拟器
【问题分析】
小 Y 虽有很多溶液，但还是没有办法配成想要的溶液，因为万一倒错了就没有办法挽回了。他从网上下载了一个溶液配置模拟器：模拟器在计算机中构造一种虚拟溶液，然后可以虚拟地向当前虚拟溶液中加入一定浓度、一定质量的这种溶液，模拟器会快速地算出倒入后虚拟溶液的浓度和质量。
模拟器的使用步骤如下：
（1）为模拟器设置一个初始质量和浓度 V0 、C0 % （0≤C0 ≤100）。
（2）进行一系列操作，模拟器支持两种操作：一种是 P（v，c）操作，表示向当前的虚拟溶液中加入质量为 v、浓度为 c 的溶液；另一种是 Z 操作，即撤销上一步 P 操作。
【输入格式】
第 1 行两个整数 V0 、C0 。
第 2 行 1 个整数 n，n≤10000，表示操作数。
接下来的 n 行，每行一条操作，格式为：P_v_c 或 Z。其中“_”代表一个空格，当只剩初始溶液的时候，再撤销就没有用了。
任意时刻质量都不会超过 231 -1。
【输出格式】
输出 n 行，每行两个数 Vi 、Ci ，之间用一个空格隔开，其中 Vi 为整数，Ci 为实数（保留 5 位小数）。其中，第 i 行表示第 i 次操作以后的溶液质量和浓度。
【输入样例】
100 100
2
P 100 0
Z
【输出样例】
200 50.000 00
100 100.000 00
上一篇： 数据结构-007-队列、顺序队、循环队