**算法竞赛入门第三节笔记**

算法竞赛入门第三节笔记
栈（stack)
仅在表头进行插入和删除，先进后出，就类似于一个羽毛球筒，当把上面一个球放到筒里后，要拿下面的球，你就得把上面的球先拿走，只能往最上面的放球，也只能从最上面拿球
队列(queue)
只能在表的前端进行删除，在表的后端进行插入，先进先出，就像在食堂排队，最前面的一个人拿到饭离开，后来的人排到队尾（插队可耻hhh),先来的人拿到饭先走，即为先进先出
stack常用函数：
push()–向栈顶压入元素
pop()–弹出栈顶元素
top()–访问栈顶元素

queue常用函数：
front()–访问队首元素
back()–访问队尾元素
push()–向队尾插入元素
pop()–弹出队首元素
题目描述
给定牛牛一个后缀表达式s，计算它的结果，例如，1+1对应的后缀表达式为1#1#+，‘#’作为操作数的结束符号。
其中，表达式中只含有‘+’、’-‘、’*‘三种运算，不包含除法。
本题保证表达式一定合法，且计算过程和计算结果的绝对值一定不会超过10^{18}
示例1
输入：“1#1#+”
返回值：2
说明：1#1#+这个后缀表达式表示的式子是1+1，结果为2
示例2
输入："12#3#+15# * "
返回值：225
说明： 12#3#+15#*这个后缀表达式表示的式子是(12+3)*15，结果为225
备注
1≤表达式中操作数≤1e9
1≤表达式长度≤1e6
思路：用栈来存储数据，每次遇到数就压入栈中，遇到操作符就把栈顶的两个元素取出来运算
把字符串变数字：
先初始化为0，再利用一个循环，只要循环到数字，就进入一个for循环中，每次都由前面的结果乘以10再去加上下一个数字，直到不是数字。（有参考）

#include<bits/stdc++.h>
using namespace std;
stack<long long>a;
int main() {
 char str[1000];
 scanf("%s", str);
 long long int temp = 0;
 long long int num1,num2;
 long long int len = strlen(str);
 for (int i = 0; i < len; i++) {
  if (str[i] >= '0' && str[i] <= '9') {
   temp *= 10;
   temp += str[i]-'0';
  } else if (str[i] == '#') {
   a.push(temp);
   temp = 0;
  }
  else 
  { num1=a.top();
    a.pop();
    num2=a.top();
    a.pop();
    if(str[i]=='+')
    a.push(num1+num2);
    if(str[i]=='-')
    a.push(num2-num1);
    if(str[i]=='*')
    a.push(num1*num2);   
  }
 }
 printf("%lld",a.top());
}

好串
题目描述
题目传送门
牛牛喜欢跟字符串玩耍，他刚刚学会了一个新操作，将一个字符串x插入另一个字符串y中（包括放在开头和结尾）
牛牛认为如果一个串是好的当这个串能按照如下方法被构造出来：
一开始，有一个空串，然后执行0次或者若干次操作，每次操作将ab插入当前的字符串
根据上面的定义，ab, aabb, aababb都是好串，aab,ba,abbb并不是好串
现在给你一个字符串s，判断s是否是好串
输入描述:
输入一行包含一个字符串,长度不超过50
示例1
输入
ab
输出
Good
示例2
输入
aab
输出
Bad
示例3
输入
abaababababbaabbaaaabaababaabbabaaabbbbbbbb
输出
Bad
我的理解：有两种实现方法，一种是不用栈，此时我们可以转换一下思维，题目中的a,b可以想象成左括号与右括号，最终要达到左括号与右括号完全匹配，我们就称它为好串，这时我们就设一个计数器count，遇到左括号就，count++，遇到右括号就count–，需要注意的是我们遇到了右括号后，需要判断count是否大于0，如果count<0就证明之前没有左括号与之相配，如果存在了这样一个不合法的右括号，那这肯定不是一个好串了，falg标记，跳出循环，输出Bad即可。当循环结束，判断count是否为0，如果count等于0且flag值未变，证明所有的左括号都与右括号相匹配了，输出Good即可。
第二种实现方法就是采用栈，思想是一样的，就是可以练习一下入栈和出栈
第一种方法AC代码：

#include<bits/stdc++.h>
int main() {
 char str[100];
 scanf("%s", str);
 int count = 0;
 int flag = 1;
 int len = strlen(str);
 for (int i = 0; i < len; i++) {
 if (str[i] == 'a')
   count++;
  if (str[i] == 'b') {
   if (count > 0)
    count--;
    else {
    flag = 0;
    break;
       }
  }
 }
 if (count == 0 && flag)
  printf("Good");
 else
  printf("Bad");
}

第二种方法AC代码：

#include<bits/stdc++.h>
using namespace std;
stack<int>m;
int flag=1;
int main()
{
 char str[100];
 cin>>str;
 for(int i=0;i<strlen(str);i++)
 {
  if(str[i]=='a')
  m.push('a');
  else if(str[i]=='b')
  { if(m.empty())
    {
     flag=0;
     break;
    }
    else
    m.pop(); 
     }  
 }
 if(m.empty()&&flag==1)
 cout<<"Good"<<endl;
 else 
 cout<<"Bad"<<endl;
}