栈

栈是一种线性表，对它的插入和删除都只能够在表的同一端进行。这一端叫做“栈顶”，另一端则叫做“栈底”。
特性：先进后出
举例：交卷子；
栈的作用：保护现场
典型应用：递归
栈的实现：数组

出栈序列（例题）

栈是常用的一种数据结构，有n个元素在栈顶端一侧等待进栈，栈顶端另一侧是出栈序列。你已经知道栈的操作有两种：push和pop，前者是将一个元素进栈，后者是将栈顶元素弹出。现在要使用这两种操作，由一个操作序列可以得到一系列的输出序列。请你编程求出对于给定的n，计算并输出由操作数序列1,2,…,n，经过一系列操作可能得到的输出序列总数。

法一 回溯：（最容易想到）

void zhan(int top,int intop,int outtop)
{    
    if(outtop==n){ans+=1;return ;}//一个合法序列 
    if(top==0){
        zhan(top+1,intop-1,outtop);
        return;
    }//栈顶为空，则入栈 
    if(intop>0)zhan(top+1,intop-1,outtop);//入栈 
    zhan(top-1,intop,outtop+1);//出栈 
}
int main()
{
    cin>>n;
    zhan(0,n,0);
    cout<<ans<<endl;
    return 0;
}

法二 递推（强推！Catalan数原理，和栈没啥关系）卡特兰数

一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列?
分析
首先，我们设f(n)=序列个数为n的出栈序列种数。(我们假定，最后出栈的元素为k，显然，k取不同值时的情况是相互独立的，也就是求出每种k最后出栈的情况数后可用加法原则，由于k最后出栈，因此，在k入栈之前，比k小的值均出栈，此处情况有f(k-1)种，而之后比k大的值入栈，且都在k之前出栈，因此有f(n-k)种方式，由于比k小和比k大的值入栈出栈情况是相互独立的，此处可用乘法原则，f(n-k)*f(k-1)种，求和便是Catalan递归式。

首次出空之前第一个出栈的序数k将1~n的序列分成两个序列，其中一个是1~k-1，序列个数为k-1，另外一个是k+1~n，序列个数是n-k。

此时，我们若把k视为确定一个序数，那么根据乘法原理，f(n)的问题就等价于–序列个数为k-1的出栈序列种数乘以序列个数为n - k的出栈序列种数，即选择k这个序数的f(n)=f(k-1)×f(n-k)。而k可以选1到n，所以再根据加法原理，将k取不同值的序列种数相加，得到的总序列种数为:f(n)=f(0)f(n-1)+f(1)f(n-2)+……+f(n-1)f(0)。

看到此处，再看看卡特兰数的递推式，答案不言而喻，即为f(n)=h(n)= C(2n,n)/(n+1)= c(2n,n)-c(2n,n+1)(n=0，1，2，……)。

最后，令f(0)=1，f(1)=1。（来自360百科）

cin>>n;
f[0]=1;f[1]=1;//初始化
for(int i=2;i<=n;i++)//有i个数 
    for(int j=0;j<i;j++) f[i]+=f[j]*f[i-j-1];
cout<<f[N]<<endl;

栈的应用

括号匹配(小括号）

#include <iostream>
using namespace std;
int i,top;
char a[260];
bool nflag;
int main()
{
    cin>>a;
    while(a[i]!='@')
    {
        if(a[i]=='(') top++;
        if(a[i]==')') top--;
        i++;
    }
    if(top!=0) cout<<"NO"<<endl;
    else cout<<"YES"<<endl;
    return 0;
}

• 表达式求值（后缀）

#include <iostream>
using namespace std;
string s;
int i,len,t;
long long a[255],temp;
bool nflag;
int main()
{
    getline(cin,s);
    len=s.length();
    while(i<len-1)
    {
        temp=0;
        while(i<len-1&&s[i]>='0'&&s[i]<='9')
        {
            temp=temp*10+s[i++]-'0';
            nflag=1;
        }
        if(nflag>0)
        {
            a[++t]=temp;
            nflag=0;
        }
        switch(s[i])
        {
            case'+':a[--t]+=a[t+1]; break;
            case'-':a[--t]-=a[t+1]; break;
            case'*':a[--t]*=a[t+1]; break;
            case'/':a[--t]/=a[t+1]; break;
            default: break;
        }
        i++;
    }
    cout<<a[t]<<endl;
    return 0;
}

• 单调栈（！重点）

例题

矩形覆盖

分析：维护单调递减的栈（当两个高度相同的矩形，中间没有比他们低的矩形时最节约矩形）

• 若当前矩形高度小于栈顶矩形则出栈直到不满足；

• 之后仅当当前矩形高度不等于栈顶矩形则入栈；

• 答案是入过栈的矩形个数；

#include <iostream>
using namespace std;
int i,n,ans,h;
int f[100005]={-1};
int main()
{
    cin>>n;
    for(i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        while(x<f[h]) h--;
        if(x==f[h]) continue;
        if(x>f[h]){ans++; f[++h]=x;}
    }
    cout<<ans<<endl;
    return 0;
}