没错又是我来了（上一篇DFS还没写好就先来写队列与栈了哈哈哈哈
是很简单的内容呢 （比DFS简单到哪里去了
先来认识一下栈
什么是栈？
度娘是这样说的：
栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
看不太懂 对吧 我也看不懂（划掉
老师是怎么讲的嘞？
是只在表的一端进行插入和删除运算的线性表
可能单看看不懂 那我们举个栗子
（偷图王者
想要取出收纳箱A
先要取出C 再取出B 最后得到A
那么栈的工作原理我们基本了解啦
趁热打铁再继续认识一下
那么栈的工作原理我们基本了解啦
趁热打铁再继续认识一下栈的一些概念 吧~
栈的一些概念 ：
继续沿用刚刚那个栗子
借助一下前面的图理解一下：
刚刚将C B A取出的过程 就叫出栈
将 A B C 依此放入的过程 就叫入栈
栈的运用实现语句（结合数组
先要自己定义一个数组s 和一个top(top值随意 但要自己在后面使用的时候记得
左边是常用的 （右边我还没咋用过
栈的运用与相关练习题
1-栈练习 1
考察知识点 入栈 出栈 访问栈顶元素
AC代码
#include<bits/stdc++.h>
using namespace std;
int a[10000001],top=1;
int main()
{
int q,n,m;
cin>>q;
for(int i=1;i<=q;i++)
{
cin>>n;
if(n==1)
{
cin>>m;
a[++top]=m;
}
if(n==2)
{
top--;
if(top<1)
{
cout<<"impossible!";
return 0;
}
}
}
if(top<=1)cout<<"impossible!";
else cout<<a[top];
}
2-栈练习 2
说多了都是泪 因为没好好读题踩坑了好几次
所以先提一下容易踩坑的点
不保证栈空时不会出栈
若最终栈空，或栈空时有出栈操作，输出”impossible!”
考察知识点 入栈 出栈 访问栈顶元素 在计算过程中判断判断栈空
（为什么字体突然变得这么小了
AC代码
#include<bits/stdc++.h>
#include<stack>
using namespace std;
long long s[1000001];
int a[100000],b[100000]={0};
int main()
{
long long n,top=0;
int ss=1;
cin>>n;
long long k=1;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]==1)
{
cin>>b[k];
s[++top]=b[k];
k++;
}
if(a[i]==2&&top<=0)
{
cout<<"impossible!";
ss=0;
break;
}
if(a[i]==2&&top>=0)
{
top--;
}
}
if(top>=0&&ss!=0)
{
cout<<s[top];
}
if(top<=0&&ss!=0)
cout<<"impossible!";
}
3-栈练习 1
没什么好说的 坑不多 考察知识点比起第一个只增加了在过程中随时访问栈顶元素
AC代码
#include<bits/stdc++.h>
#include<stack>
using namespace std;
long long s[1000001];
int a[100000],b[100000]={0};
int main()
{
long long n,top=0;
int ss=1;
cin>>n;
long long k=1;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]==1)
{
cin>>b[k];
s[++top]=b[k];
k++;
}
if(a[i]==2)
{
top--;
}
if(a[i]==3)
{
cout<<s[top]<<endl;
}
}
}
好了 我相信你已经能熟练运用栈了
那么我们来实战演练一下
4-括号匹配
分析
我觉得老师讲的挺好的 所以直接搬上来了（其实是我懒
AC代码
#include<bits/stdc++.h>
#include<stack>
using namespace std;
int main()
{
char a[260],s[260];
scanf("%s",a);
int len=strlen(a);
int i=0,top=0,flag=1;
while(i<len&&flag!=0)
{
if(a[i]=='['||a[i]=='(')
{
s[++top]=a[i];
}
if(a[i]==']')
{
if(s[top]=='[') top--;
else flag=0;
}
if( a[i]==')')
{
if(s[top]=='(') top--;
else flag=0;
}
i++;
}
if(flag==1&&top==0) cout<<"OK";
else cout<<"Wrong";
}
5-后缀表达式
不知道什么是后缀表达式的友们可以去看看这篇博客（大白话 通俗易懂
链接在这儿
AC代码
#include<bits/stdc++.h>
using namespace std;
int s[260];
int top=0;
int main()
{
char a[260];
cin.getline(a,260);
int i=0,x=0,t1,t2;
while(a[i]!='@')
{
if(a[i]>='0' && a[i]<='9') {
x=0;
while(a[i]>='0' && a[i]<='9')
{
x=x*10+a[i]-'0';
i++;
}
s[++top]=x;
}
if(a[i]=='+')
{
t1=s[top--];
t2=s[top--];
s[++top]=t1+t2;
}
else if(a[i]=='*')
{
t1=s[top--];
t2=s[top--];
s[++top]=t1*t2;
}
else if(a[i]=='-')
{
t2=s[top--];
t1=s[top--];
s[++top]=t1-t2;
}
else if(a[i]=='/')
{
t2=s[top--];
t1=s[top--];
s[++top]=t1/t2;
}
i++;
}
cout<<s[top];
return 0;
}
中缀表达式我还没研究完 后面研究完了我再单独发一篇题解（其实是还没写
6-山峰
分析
当新一座山峰小于前面的山峰时 则存入s数组
大于时清空栈内小于新山峰的元素
等于时无需存入s数组 但能看到的山峰将和上一次一样
AC代码
#include<bits/stdc++.h>
#include<stack>
using namespace std;
int n,a[150000],ans,s[150000],top=1;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
s[1]=a[1];
for(int i=2;i<=n;i++)
{
ans+=top;
if(s[top]>a[i]) s[++top]=a[i];
else {
while(s[top]<=a[i]&&top>=1)
{
top--;
}
s[++top]=a[i];
}
}
printf("%d",ans);
return 0;
}
好了这篇学习思路差不多就这样了（毁灭吧我累了（吐血身亡
