小猫钓鱼

	星期天小哼和小哈约在一起玩桌游,他们正在玩一个非常古怪的扑克游戏——“小猫钓鱼”。游戏的规则是这样的:将一副扑克牌平均分成两份,每人拿一份。小哼先拿出手中的第一张扑克牌放在桌上,然后小哈也拿出手中的第一张扑克牌,并放在小哼刚打出的扑克牌的上面,就像这样两人交替出牌。出牌时,如果某人打出的牌与桌上某张牌的牌面相同,即可将两张相同的牌及其中间所夹的牌全部取走,并依次放到自己手中牌的末尾。当任意一人手中的牌全部出完时,游戏结束,对手获胜。

假如游戏开始时,小哼手中有 6 张牌,顺序为 2 4 1 2 5 6,小哈手中也有 6 张牌,顺序为 3 1 3 5 6 4,最终谁会获胜呢?现在你可以拿出纸牌来试一试。接下来请你写一个程序来自动判断谁将获胜。这里我们做一个约定,小哼和小哈手中牌的牌面只有 1~9。

#include<stdio.h>
struct stack{
    int data[10];
    int top;
};
struct queue{
    int data[1000];
    int head;
    int tail;
};

int main(){
    struct queue q1, q2;
    struct stack s;
    int book[10];
    int i, t;

    //初始化队列
    q1.head=1; q1.tail=1;
    q2.head=1; q2.tail=1;
    //初始化stack
    s.top=0;
    //初始化用来标记的数组,用来标记哪些牌已经在桌上
    for (i = 1 ; i <= 9 ; i ++){
        book[i] = 0;
    }
    //依次向队列插入6个数
    //小哼
    for (i = 1 ; i <= 6; i ++) scanf("%d",&q1.data[q1.tail++]);
  
    //小哈
    for (i = 1 ; i <= 6; i ++) scanf("%d",&q2.data[q2.tail++]);
    //当队列不为空的时候执行循环
    while(q1.head < q1.tail && q2.head < q2.tail){
        t = q1.data[q1.head]; //小哼出一张牌
        //判断是否能赢牌
        if(book[t] == 0){ //表明桌面上没有这张牌
            //没赢
            q1.head++;
            s.top++;
            s.data[s.top] = t;
            book[t] = 1;
        } else {
            //赢了
            q1.head++;
            q1.data[q1.tail++] = t;
            //把桌上可以赢得牌依次放到手中牌的末尾
            while (s.data[s.top] != t){
                book[s.data[s.top]] = 0;
                q1.data[q1.tail++] = s.data[s.top--];
            }
        }
        
        //跟上面一样
        t = q2.data[q2.head];
        if(book[t] == 0){
            q2.head++;
            s.top++;
            s.data[s.top] = t;
            book[t] = 1;
        } else {
            q2.head++;
            q2.data[q2.tail++] = t;
            while (s.data[s.top] != t){
                book[s.data[s.top]] = 0;
                q2.data[q2.tail++] = s.data[s.top--];
            }
        }
        
        if(q2.head == q2.tail){
            printf("\n小哼win\n");
            printf("小哼当前手中的牌是");
            for (i=q1.head; i <= q1.tail-1;i++){
                printf(" %d",q1.data[i]);
            }
            if(s.top > 0){ //如果坐上有牌则依次输出桌上的牌
                printf("\n桌上的牌是");
                for(i = 1; i <= s.top; i ++) printf(" %d",s.data[i]);
            } else {
                printf("\n桌上已经没有牌了");
            }
        } else {
            printf("\n小哈win\n");
            printf("小哈当前手中的牌是");
            for (i= q2.head; i <= q2.tail-1; i++){
                printf(" %d",q2.data[i]);
            }
            if(s.top > 0){
                printf("\n桌上的牌是");
                for(i = 1; i <= s.top; i ++) printf(" %d",s.data[i]);
            } else {
                printf("\n桌上已经没有牌了");
            }

        }
        printf("\n");

    }
    return 0;
}

输入:

2 4 1 2 5 6
3 1 3 5 6 4

执行结果：