算法总结--栈

· · 个人记录

(｡･∀･)ﾉﾞ嗨飞竹小课堂第17课开课喽!
咳咳，今天我们讲栈！
(众所周知，飞竹是偏心的，所以本文飞竹只讲手写栈QWQ~
栈的操作过于简单，我就不重复了，我们直接来看套路们：

  1. 外星人弹吉他和小M照相 这两题就是典型的利用优先级来把这题的思路固定为栈的，前者的优先级为音段的大小，后者为三种颜色，所以我们只需合理使用 push 和 pop 就可以了，不过栈有个很坑的地方，请注意数组下限哦！~

  2. 验证栈序列 这种题就是把栈的原理拿出来做一道题目，这里飞竹用的是O(T 2 n)的写法，展示(本代码为手写栈，请谨慎使用QWQ

#include<bits/stdc++.h>
using namespace std;
int pushed[1000005],poped[1000005];
int a[1000005];
int top=0;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        top=0;
        int q=1;
        for(int i=1;i<=n;i++) cin>>pushed[i];
        for(int i=1;i<=n;i++) cin>>poped[i];
        for(int i=1;i<=n;i++)
        {
            a[++top]=pushed[i];
            while(a[top]==poped[q]&&q<=n&&top>0)
            {
                q++;
                top--;
            }
        }
        if(q==n+1)
        {
            cout<<"Yes"<<endl;
        }
        else
        {
            cout<<"No"<<endl;
        }
    }
    return 0;
}
  1. 括号1，括号2，括号3 这些题就是拿我们的板子验证栈序列改成的，如果是左括号，进栈，右括号，与栈内的左括号匹配。 只不过在细节上各有千秋罢了。 飞竹展示一下板子的验证栈序列：
#include<bits/stdc++.h>
using namespace std;
int top=0;
char a[1000005];
string s;
int ans=0;
int main()
{
    cin>>s;
    int len=s.size();
    for(int i=0;i<len;i++)
    {
        if(s[i]=='(') a[++top]='(';
        else
        {
            if(top>0)
            {
                top--;
                ans+=2;
            }
        }
    }
    cout<<ans;
    return 0;
}

那么今天的栈就结束啦，
ヾ(￣▽￣)Bye\~Bye~