2019-04-25 考研--栈和队列

bool check(char *A)
{
    int p=0;
    Stack s;
    char x;
    
    while(A[p]!='\0')
    {
        if(A[p]=='(' || A[p]=='{' || A[p]=='[')
            Push(s,A[p]);
        else
        {
            if(IsEmpty(s)) return false;
            Pop(s,x);
            if(A[p]==')' && x!='(') return false;
            if(A[p]=='}' && x!='{') return false;
            if(A[p]==']' && x!='[') return false;
        }
        p++;    
    }   
    return IsEmpty(s);
} 

void manage(char box[],int n)
{
    Stack s;
    char x;
    for(int i=0;i<n;i++)
    {
        if(box[i]=='S')
        {
            Push(s,box[i]); printf("入栈");
            Pop(s,x);   printf("出栈"); 
        }
        else
        {
            Push(s,box[i]); printf("入栈");   
        }   
    }
    while(!IsEmpty(s))
    {
        Pop(s,x);
        printf("出栈");   
    } 
}


int calculate(int n,int x)
{
    Stack s;
    Init(s);
    for(int i=n;i>=0;i--)
    {
        if(i==0) Push(1);
        else if(i==1) Push(2*x);
        else Push(0); 
    }
    
    int tmp=2
    while(true)
    {
        int op1,op2,op3;
        Pop(s,op1);
        Pop(s,op2); 
        Pop(s,op3);
        op3=2*x*op1-2*(tmp-1)*op2;
        if(IsEmpty(s)) return op3;
        Push(op3);
        Push(op2);
        
        tmp++;
    }
    return 0;   
} 


标准答案过程：
double p(int n,double x)
{
    struct stack{
        int no;
        double val;
    }st[MaxSize];
    int top=-1,i;
    double fv1=1,fv2=2*x;
    for(i=n;i>=2;i--)
    {
        top++;
        st[top].no=i;   
    } 
    while(top>=0)
    {
        st[top].val=2*x*fv2-2*(st[top].no-1)*fv1;
        fv1=fv2;
        fv2=st[top].val;
        top--;
    }
    if(n==0) return 1;
    return fv2;
} 


Queue q1,q2;//q1是客车，q2是货车
int num1,num2;//记录客车，货车的数量 
typedef struct{
    int type;//type=1表示客车，2表示货车 
}Car;

void Come(Car car,Queue& q1,Queue& q2) //处理新来的车辆 
{
    if(car.type==1) { Push(q1,car); num1++; }
    if(car.type==2) { Push(q2,car); num2++; }
    transport(q1,q2);//每当来车的时候，看看能不能过江（满10可以过江） 
} 

bool transport(Queue& q1,Queue& q2)
{
    if(num1+num2<10) return false;//不足10个
    if(num1>=8 && num2>=2)
    {
        num1-=8; num2-=2;
        for(int i=1;i<=4;i++) DeQueue(q1); Dequeue(q2);
        for(int i=1;i<=4;i++) DeQueue(q1); Dequeue(q2);
        return true;    
    } 
    if(num1<4)
    {
        for(int i=1;i<=num1;i++) DeQueue(q1);
        for(int i=1;i<=10-num1;i++) DeQueue(q2);
        num2-=10-num1;
        num1=0;
        return true;
    }
    if(num2==0)
    {
        for(int i=1;i<=10;i++) DeQueue(q1);
        num1-=10;
        return true; 
    }
    return false;
}