poj1363 栈的简单应用 63ms

刘汝佳紫书原题

#include<cstdio>
#include<stack>
using namespace std;
//栈的简单应用
//两种情况A->C,C->B,
int main()
{
    int n,A,B;
    bool f = true;
    int rail[1005];
    stack<int>s;
    while(scanf("%d",&n),n)
    {
        while(scanf("%d",&rail[1]),rail[1])
        {
            A=B=1;//可以看成指向A,B的两个指针
            f = true;
            for(int i = 2; i<=n; ++i) scanf("%d",&rail[i]);
            while(B<=n)
            {
                //简化了，其实可以直接压栈然后判断，这样可以节省时间
                if(rail[B]==A) // 两序列元素相同，则A,B下标同时+1
                {
                    A++;
                    B++;
                }
                else if(!s.empty()&&s.top()==rail[B]) // 判断c就是(中转栈道)是否为空,不为空判断栈顶元素是否与rail[B]相同
                {
                    s.pop();
                    B++;
                }
                else if(A<=n) //判断是否1-n的下标都遍历了，遍历完了则不能压栈，只能出栈
                {
                    s.push(A++);
                }
                else //都不行则说明不满足
                {
                    f = false;
                    break;
                }
            }
            printf(f?"Yes\n":"No\n");
            while(!s.empty()) s.pop();
        }
        printf("\n");
    }
    return 0;
}