2020-2021学年信息学奥赛资料 第二十课 栈（适用于高中）课件（12张PPT）

第二十课 栈

目 标
01、理解栈的概念及其基本操作
02、学会使用栈解决一些实际问题。
栈也是一种操作（或者说运算）受到限制的特殊线性表。其插入和删除操作都限制在表的一端进行，这一端被称为“栈顶（top）”，相对的另一端称为“栈底（bottom）”。插入操作称为“进栈（PUSH）”或者“压栈”，删除操作称为“出栈（POP）”。栈的特点是“先进后出（FILO，First In Last Out）”
1. 栈的基本操作
（1） 初始化
（2） 判空
（3） 求栈中实际元素的个数
（4） 进栈（压栈）
（5） 出栈
（6） 取栈顶元素
2. 栈的应用举例
例1、程序员输入问题
【问题描述】
程序员输入程序出现差错时，可以采取以下的补救措施：按错了一个键时，可以补按一个退格符“#”，以表示前一个字符无效；发现当前一行有错，可以按一个退行符“@”，以表示“@”与前一个换行符之间的字符全部无效。
【输入格式】
输入一行字符，个数不超过 100。
【输出格式】
输出一行字符，表示实际有效字符。
【输入样例】
sdfosif@for（ii#=1，#；i<.#=8；i+++#）；
【输出样例】
for（i=1；i<=8；i++）；
【问题分析】
通过栈的操作，模拟这一过程：
1、逐行处理，处理完一行后输出结果、栈重新置空。
2、对于每行，逐个字符处理：
①既不是退格符“＃”，也不是退行符“＠”，则将该字符压栈；
②是退格符“＃”，则出栈；③是退行符“＠”，就把栈置空。
#include
using namespace std;
int main(){
freopen( “ editor.in “ , “ r “ ,stdin);
freopen( “ editor.out “ , “ w “ ,stdout);
char s[110];
int top = 0;
string str;
while(getline(cin,str)){
for(int i = 0; i < str.size(); ++i){
switch(str[i]){
case ’ # ’ ：top--; break;
case ’ @ ’ ：top=0; break;
default：top++; s[top] = str[i];
} }
for(int i = 1; i <= top; i++) cout << s[i];
cout << endl;
}
return 0;
}
例2、溶液模拟器
【问题描述】
小谢虽然有很多溶液，但是还是没有办法配成想要的溶液，因为万一倒错了就没有办法挽回了。因此，小谢到网上下载了一个溶液配置模拟器。模拟器在计算机中构造一种虚拟溶液，然后可以虚拟地向当前虚拟溶液中加入一定浓度、一定体积的这种溶液，模拟器会快速地算出倒入后虚拟溶液的浓度和体积。当然，如果倒错了可以撤销。
模拟器的使用步骤如下：
1）为模拟器设置一个初始体积和浓度 V0、C0%。
2）进行一系列操作，模拟器支持两种操作：
P(v,c)操作：表示向当前的虚拟溶液中加入体积为 v 浓度为 c 的溶液；
Z 操作：撤销上一步的 P 操作。
【输入格式】
第一行两个整数，表示 V0 和 C0，0≤C0≤100；
第二行一个整数 n，表示操作数，n≤10000；
接下来 n 行，每行一条操作，格式为：P_v_c 或 Z。
其中 _ 代表一个空格，当只剩初始溶液的时候，再撤销就没有用了。
任意时刻质量不会超过 2^31 -1。
【输出格式】
n 行，每行两个数 Vi，Ci，其中 Vi 为整数，Ci 为实数（保留 5 位小数）。
其中，第 i 行表示第 i 次操作以后的溶液体积和浓度。
【输入样例】
100 100
2
P 100 0
Z
【输出样例】
200 50.00000
100 100.00000
【问题分析】
使用栈来模拟实现：
1） 读入撤销时，栈顶元素出栈。
2） 读入溶液时，把新的溶液的体积和浓度压栈。
3） 每次操作完，输出栈顶的体积和浓度。
#include
using namespace std;
const int N = 10010;
struct node{
int w;
double c;
}a[N];
int main(){
freopen( “ simulator.in ” , ” r ” ,stdin);
freopen( “ simulator.out ” , ” w ” ,stdout);
int v,n,c,top = 1;
cin >> v >> c >> n;
a[top].w = v,a[top].c = c; // 将初始溶液入栈

接上面程序
while(n--){
char ch;
cin >> ch;
if(ch == ‘ Z ’ && top > 1) top--; // 出栈
if(ch == ‘ P ’ ){
cin >> v >> c;
top++;
a[top].w = a[top-1].w + v; // 将新溶液的质量入栈
a[top].c = (a[top-1].w * a[top-1].c + v * c)/(double)a[top].w;
// 将新溶液的浓度入栈
}
cout << a[top].w << “ “ ;
cout << fixed << setprecision(5) << a[top].c << endl;
}
return 0;
}