stack 栈

其实今天我们主要讲的是搜索，但是留作业不知道怎么就突然全变成栈了。

其实栈和队列没什么区别，只是一个先进先出，一个先进后出。基本操作也是一样的。

栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。

向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

1. size()                                          返回实际个数
2. empty()                                       判断是否为空
3. push(item)                                 压栈
4. top()                                             返回栈顶元素
5. pop()                                            将栈顶元素删除
6. s1.swap(s2)                               将两个栈元素交互
7. s1 == s1                                      判断是否相等

手里有几个括号匹配的题，大家过目。

第一个，只有（）小括号的简化版
#include<iostream>
#include<vector>
#include<stack>
#include<cstdio>
#include<cstring>
using namespace std;
char a[255];
stack <char> st;
int ok = 1;
int main()
{
    gets(a);
    int l;
    l = strlen(a);
    for(int i = 0;i < l;i ++)
    {
        if(a[i] == '(' || a[i] == ')')
        {
            if(a[i] == '(')
            st.push('(');
            else
            {
                if(st.empty() == 0)
                {
                    if(st.top() == '(')
                    st.pop();
                    else
                    {
                        ok = 0;
                        break;
                    }
                }
                else
                {
                    ok = 0;
                    break;
                }
            }
            
        }
    }
    if(ok == 1 && st.empty() == 1)
    {
        cout<<"YES"<<endl;
    }
    else
    cout<<"NO"<<endl;
    return 0;
}

未完待续。。。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
using namespace std;
int a[10001] = {0},b[10001] = {0};
char s[10001];
void gsy(int a[])
{
    int i;//将括号转换为数字，以比较括号级别 
    for(i = 0;i < strlen(s);i++)
    {
        if(s[i] == '{') a[i + 1] = 1;
        if(s[i] == '[') a[i + 1] = 2;
        if(s[i] == '(') a[i + 1] = 3;
        if(s[i] == '<') a[i + 1] = 4;
        if(s[i] == '>') a[i + 1] = 5;
        if(s[i] == ')') a[i + 1] = 6;
        if(s[i] == ']') a[i + 1] = 7;
        if(s[i] == '}') a[i + 1] = 8;
    }
}
int main()
{
    int i,n,t = 0,m,j,k;
    cin>>n;
    for(i = 1;i <= strlen(s);i++)
    {
        scanf("%s",s);
        gsy(a);
        for(j = 1;j <= strlen(s);j++)
        {
            if(a[j] <= 4) //左括号 
            if(a[j] >= b[t])
            b[++t] = a[j];
            else break;
            if(a[j] >= 5)
            if(a[j] + b[t] == 9) t--;
            else t++;
        }
        if(t == 0)
        cout<<"YES"<<endl;
        else
        cout<<"NO"<<endl;
    }
    return 0;
}