本文共 4359 字，大约阅读时间需要 14 分钟。

此篇文章参考了啊哈！算法_

游戏介绍

有两个人在玩纸牌游戏，游戏规则：将一副扑克牌平均分成两份，每人拿一份。A先拿出手中的第一张扑克牌放在桌上，然后B也拿出手中的第一张扑克牌，并放在A刚打出的扑克牌的上面，就像这样两人交替出牌。出牌时，如果某人打出的牌与桌上某张牌的牌面相同，即可将两张相同的牌及其中间所夹的牌全部取走，并放到自己手中牌的末尾。当任意一人手中的牌全部出完时，游戏结束，对手获胜。

问题：加入游戏开始时，A手中有6张牌，顺序为 2 4 1 2 5 6，B手中也有6张牌，顺序为 3 1 3 5 6 4，最终谁会获胜呢？(假设此题中，A和B手中的牌的牌面只有1~9)。

算法思路分析

我们把A，B两个人分别出牌，赢牌的操作可以对应为队列的两个操作。出牌就是出队，赢牌就是入队。 而桌子就是一个栈，每打出一张牌放到桌上就相对于入栈。当有人赢牌的时候，依次将牌从桌上拿走，就相当于出栈。

赢牌的规则就是 如果某人打出的牌与桌上的某张牌相同，即可将两张牌以及中间所夹的牌全部取走。

我们用一个数组book 来记录桌上有哪些牌。
我们可以创建一个结构体用来实现队列，用head来存储对头，tail存储队尾（tail指向队尾的后一个元素）。

struct queue{       int data[1000];    int head;    int tail;};

创建一个结构体用来实现栈，其中用top存储栈顶，数组data用来存储栈中的元素。

struct stack{       int data[10];    int top;};

接下来我们需要定义两个队列变量q1,q2。q1用来模拟A手中的牌，q2模拟B手中的牌。定义一个栈变量 s 模拟桌上的牌。

 struct queue q1,q2;    struct stack s;

接下来初始化队列和栈。

//初始化队列q1,q2都为空，此时两人手中都没有牌    q1.head=q1.tail=1;    q2.head=q2.tail=1;        //初始化栈s为空，最开始的时候桌上也没有牌    s.top=0;

接下来需要读入A ,B 最初时手中的牌，分两次读入，每次读入6个数，分别插入q1,q2中。

  //先读入6张牌，放到A手上    for(i=1;i<=6;i++)    {           scanf(" %d",&q1.data[q1.tail];//读入一个数到队尾        q1.tail++;  //队尾后移    }     //读入6张牌，放到B手上       for(i=1;i<=6;i++)    {           scanf(" %d",&q2.data[q2.tail]);        q2.tail++;    } 

准备工作到此已经完成，游戏正式开始，A先开始出牌。

t=q1.data[q1.head];

用数组book来记录桌面上有哪些牌

for(i=0;i<10;i++)    {           book[i]=0;    }

接下来如果桌面上增加一张牌，就需要将其对应的book[i]设为1，用于标记，表示这个数字的牌桌面上已经有了。

代码实现

#include <stdio.h>#include <stdlib.h>#include<string.h>struct queue{       int data[100];    int head;    int tail;}; struct stack{       int data[100];    int top;};int main(){       struct queue q1;    struct queue q2;    struct stack s;    int n;    int i;    int t;    int book[10];    s.top =0;//队和栈初始化    q1.head=1;    q1.tail=1;    q2.head=1;    q2.tail=1;    printf("请输入牌的个数： ");    scanf("%d",&n);    for(i=0;i<10;i++)    {           book[i]=0;    }     for(i=1; i<=n; i++)    {           scanf("%d",&q1.data[q1.tail]);//q1的牌        q1.tail++;    }     for(i=1; i<=n; i++)//q2的牌    {           scanf("%d",&q2.data[q2.tail]);        q2.tail++;    }    while(q1.head<q1.tail && q2.head<q2.tail)    {           t = q1.data[q1.head];//出第一张牌         if(book[t]==0)        {               //q1这轮没有赢牌            q1.head++;            s.top++;            s.data[s.top]=t;//往栈里放牌            book[t]=1;//说明桌子上有刚才放的那张牌        }        else        {               //q1这轮赢牌            q1.head++;            q1.data[q1.tail]=t;//把刚出去的那张牌收回来并放在手里的牌尾            q1.tail++;            while(s.data[s.top]!=t)            {                   //收取两张相同牌之间的牌                book[s.data[s.top]]=0;//取消标记                q1.data[q1.tail] = s.data[s.top];                q1.tail++;                s.top--;            }            //收回牌面为t的牌            book[s.data[s.top]]=0;            q1.data[q1.tail ]=s.data[s.top];            q1.tail++;            s.top--;        }         if(q1.head==q1.tail)            break;//q1的牌已经打完，下面同理进行q2的操作          t = q2.data[q2.head];//出第一张牌         if(book[t]==0)        {               //q2这轮没有赢牌            q2.head++;            s.top++;            s.data[s.top]=t;//往栈里放牌            book[t]=1;//说明桌子上有刚才放的那张牌        }        else        {               //q2这轮赢牌            q2.head++;            q2.data[q2.tail]=t;//把刚出去的那张牌收回来并放在手里的牌尾            q2.tail++;            while(s.data[s.top]!=t)            {                   //收取两张相同牌之间的牌                book[s.data[s.top]]=0;//取消标记                q2.data[q2.tail] = s.data[s.top];                q2.tail++;                s.top--;            }            //收回牌面为t的牌            book[s.data[s.top]]=0;            q2.data[q2.tail ]=s.data[s.top];            q2.tail++;            s.top--;        }    }    if(q2.head ==q2.tail)    {           printf("q1赢了!\n");        printf("q1现在手中的牌是：  ");        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("q2赢了!\n");        printf("q2现在手中的牌是：  ");        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");    }     return 0; }