算法 纸牌问题

/*
纸牌问题--小猫钓鱼：
游戏规则：将一副扑克牌平均分成两份，每人拿一份。a先拿出第一张扑克放在桌上，然后b也拿出手中的第一张牌，放在a刚打出的牌上，就像这样两人交替出牌。出牌时，如果某人打出的牌与桌上的某张牌一样，即可将两张相同的牌及其中间所夹的牌全部取走，并以次放到自己手牌的牌尾，当任意一人的手牌出完时，游戏结束，对手获胜。a的手牌2，4，1，2，5，6； b的手牌3，1，3，5，6，4。请问 谁获胜？

*/

/*
 每个人都有出牌和赢牌两个操作，可以看成是一个队列。桌面上的牌可以看成一个栈。出牌head++，赢牌q[tail]=x,tail++,出栈top--，入栈top++，s[top]=x;
 */

-(void)test {
    
    int a[]={2,4,1,2,5,6};
    int b[]={3,1,3,5,6,4};
    

    // 队列 模拟手牌
    struct queue {
        int data[1000];
        int head;
        int tail;
    };
    
    // 栈 模拟桌上的牌
    struct stack {
        int data[10];
        int top;
    };
    
    struct queue q1,q2;
    struct stack s;
   
    // 初始化 队列q1 q2
    q1.head=1;
    q1.tail=1;
    q2.head=1;
    q2.tail=1;
    // 初始化 栈
    s.top = 0;
    
    // 读入a手牌
    for (NSInteger i=0; i<6; i++) {
        q1.data[q1.tail] = a[i];
        q1.tail ++ ;
    }
    
    // 读入b手牌
    for (NSInteger i=0; i<6; i++) {
        q2.data[q2.tail] = b[i];
        q2.tail ++ ;
    }
    
    // 模拟两人出牌 直到一人手里没牌 结束
    while (q1.head<q1.tail&&q2.head<q2.tail) {
        
        // a出牌
        int t = q1.data[q1.head];
        
        // 判断桌上有没有相同的牌
        int flag =0;
        // top=0 没牌 top=1 只有一张牌
        for (NSInteger i=1; i<=s.top; i++) {
            if (t==s.data[i]) {
                flag = 1;
                break;
            }
        }
        
        // flag为0 代表没有相同的牌
        if (flag==0) {
            q1.head ++; // 已经打出这张牌 出队 ++
            s.top ++;
            s.data[s.top] = t; // 这张牌放到桌上 入栈++
        }
        
        // flag为1 代表有相同的牌 可以赢牌
        if (flag==1) {
            q1.head ++ ; // 这张牌已经打出 出队 ++
            q1.data[q1.tail] = t; // 这轮赢牌，刚打出的牌加到牌尾
            q1.tail ++;
            // 把桌上所有的可赢的牌加到牌尾 从当前桌面上最顶部一张牌开始取直到取到相同的牌为止
            while (s.data[s.top]!=t) {
                q1.data[q1.tail] = s.data[s.top];
                q1.tail ++;
                s.top --;
            }
            
            // 把桌面上的相同的牌也取走
            q1.data[q1.tail] =s.data[s.top];
            q1.tail ++;
            s.top --;
            
            
        }
        
        
        // b出牌
        int t2 = q2.data[q2.head];
        
        // 判断桌上有没相同的牌
        int flag2 = 0;
        for (NSInteger i=1; i<s.top; i++) {
            if (t2==s.data[s.top]) {
                flag2 =1;
                break;
            }
        }
        
        // flag2 ==0 ，这轮输了
        if (flag2 == 0) {
            q2.head ++; // 已经打出的牌出队
            s.top ++;
            s.data[s.top] =t2; // 已经打出的牌 放到桌上 入栈
        }
        
        // flag2 == 1,这轮赢了
        if (flag2 == 1) {
            q2.head ++; // 已经打出的牌出队
            q2.data[q2.tail] = t2; // 这轮赢了 已经打出的手牌 放到牌尾
            q2.tail ++;
            
            // 把桌上所有的可赢的牌加到牌尾 从当前桌面上最顶部一张牌开始取直到取到相同的牌为止
            while (s.data[s.top]!=t2) {
                q2.data[q2.tail] = s.data[s.top];
                q2.tail++;
                s.top -- ;
            }
            
            // 把桌面上的相同的牌也取走
            q2.data[q2.tail] =s.data[s.top];
            q2.tail ++;
            s.top --;
            
        }
        
    }
    
    
    if (q1.head == q1.tail) {
        NSLog(@"a 输了");
        for (NSInteger i=1; i<q2.tail; i++) {
            NSLog(@"b当前手牌:%d",q2.data[i]);
        }
        if (s.top==0) {
            NSLog(@"当前桌面上没有牌");
        }else {
            for (NSInteger i=1; i<=s.top; i++) {
                NSLog(@"桌上的牌:%d",s.data[i]);
            }
        }
    }
    
    if (q2.head == q2.tail) {
        NSLog(@"b 输了");
        for (NSInteger i=1; i<q1.tail; i++) {
            NSLog(@"a当前手牌:%d",q1.data[i]);
        }
        if (s.top==0) {
            NSLog(@"当前桌面上没有牌");
        }else {
            for (NSInteger i=1; i<=s.top; i++) {
                NSLog(@"桌上的牌:%d",s.data[i]);
            }
        }
    }
    
}