编辑代码

/*
3.设计算法，判断输入序列12。。。n的任一排列p1p2…pn是否是栈的正确输出序列。
*/
#include<stdio.h>
typedef int SType;
#define SSize 200;

int In[200];//顺序常数组
int Out[200];//输入组
int Step[400];     //保存进出stack顺序
int count=0;

//出栈
int pop(SType *s,int top){
    if(top==-1){
        printf("empty stack\n");
        return -1;
    }
    printf("pop %d\n",s[top]);
    return --top;
}

//入栈
int push(SType *s,int top, SType ch){
    s[++top]=ch;
    printf("push %d\n",s[top]);
    return top;
}

bool Check(int n)
{
    SType S[SSize];//顺序常数组的栈
    SType T[SSize];//输入组的栈
    for(int i=n-1;i>=0;i--)//从尾到头入/输入组的栈
        push(T,Ttop,Out[i]); //T.push(Out[i]);
    for(int i=0;i<n;i++)
    {
        push(S,Stop,In[i]); //S.push(In[i]);//从头到尾入顺序常数组的栈
        Step[count++]=0;
        while(!S.empty()&&!T.empty()&&S.top()==T.top())//
        {
            Step[count++]=1;
            pop(S,Stop);//S.pop();
            pop(T,Ttop);//T.pop();
        }
    }
    return Stop//S.empty();
}

int main(){
    char s[100];
    int Stop=Ttop=-1,n;
    while(printf("n=")&&~scanf("%d",&n)){
        for(int i=0;i<n;i++)
        In[i]=i+1;
        for(int i=0;i<n;i++)
        scanf("%d",&n);


        bool res=Check(n);
        res?printf("empty"):printf("NOT empty");//cout<<(res?"empty":"NOT empty")<<endl;
        printf("\n");//cout<<("\n")<<endl;
        if(res)
            for(int i=0;i<count;i++)
                Step[i]?printf("OUT"):printf("IN");//cout<<(Step[i]?"OUT":"IN")<<endl;
        return 0;
    }
    
}