目录介绍：一、栈与队列的定义二、纸牌游戏的规则三、算法分析与实现四、算法优化

前面学习了栈和队列的基本原理，先回忆一下它们的作用：栈主要是解决子程序的调用和返回；而列队主要是解决先来先服务的问题。现在应用栈与队列的原理来解决现实中基本的案例。

一、栈与队列的定义

栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相反，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

队列（queue）是一种先进先出的线性表，简称FIFO。在表一端（表尾）插入，在另一端（表头）删除。表的插入操作称为入队，表的取出操作称为出队。

二、纸牌游戏的规则

记得小时候，我们很喜欢玩一种古老的游戏--小猫钓鱼，它的规则是：

将一副扑克牌平均分成两份，每人拿一份。A先拿出手中的第一张扑克牌放在桌上，然后B也拿出手中的第一张扑克牌，并放在A刚打出的扑克牌的上面。

出牌时，如果某人打出的牌与桌上某张牌的牌面相同，即可将两张相同的牌及其中间所夹的牌全部取走，并依次放在自己手中牌的末尾。当任何一人手中的牌全部出完时，游戏结束，对手获胜。

假如游戏开始时，A手中有6张牌，顺序为 2 4 1 2 5 6，B手中也有6张牌，顺序为 3 1 3 5 6 4，最终谁会获胜呢？

这里我们分析一下游戏有几种操作：分别是出牌和赢牌，用队列来模拟：出牌就是出队，而赢牌就是入队，不管是A或是B都是同样的操作。而桌子就相当是一个栈，每打出一张牌放到桌子上就相当于入栈，当有人赢牌时，取走桌面的牌，就相当出栈。

三、算法分析与实现

根据以上分析，我们需要创建两个队列，一个栈来模拟整个游戏，首先创建一个队列结构来实现出牌及赢牌情况：

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

head 用来存储队头，tail 用来存储队尾。数组 data 用来存储队列中的元素，大小可以设置得更大一些，以防数组越界。

再创建一个结构体来实现栈，相当于放牌的桌子：

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

top 用来存储栈顶，数组 data 用来存储栈中的元素，大小设置为10，因为这里假设只有9种不同的牌面，所以数组大小设置为10。

假设用q1来模拟A手中的牌，q2用来模拟B手中的牌，同时定义一变量s来放置桌面上的牌，定义以下：

struct queue q1,q2;struct stack s;

接着来初始化一下队列和栈：

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

然后读入A和B最初时手中的牌，分两次读入，分别插入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先出牌：

temp=q1.data[q1.head];

A打出第一张牌，也就是q1的队首，先将这张牌存放在临时变量temp中，判断桌上的牌与 temp 有没有相同的，枚举桌上的每一张牌与 temp 进行比对：

flag=0;for(i=1;i<=top;i++){	if(temp==s[i]){		flag=1;		break;	}}

如果 flag 的值为 0 就说明A没能赢得桌上的牌，将打出的牌留在桌上。

if(flag==0){	//A 此轮没有赢牌	q1.head++;	//A已经打出一张牌，所以要把打出的牌出队 	s.top++;	s.data[s.top]=temp; 	//再把打出的牌放到桌上，即入栈 }

如果 flag 的值为 1，就表明 A 可以赢得桌上的牌,注意：首先把刚才打出的牌先放到手中牌的末尾，再把将赢得的牌依次放入 A 的手中。

if(flag==1){	//A 此轮可以赢牌	q1.head++;	// A 已经打出一张牌，所以要把打出的牌出队	q1.data[q1.tail]=temp;	//因为此轮可以赢牌，所以紧接着把刚才打出的牌又放到手中牌的末尾	q1.tail++;	while(s.data[s.top]!=temp)	//把桌上可以赢得的牌（从当前桌面最顶部的一张牌开始取，直到取到与打出的牌相同为止	//依次放到手中牌的末尾	{		q1.data[q1.tail]=s.data[s.top];		//依次放入队尾		q1.tail++;		s.top--;		//栈中少了一张牌，所以栈顶要减 1 	 } } 

A出牌的所有步骤模拟完了，B的出牌结果也是这样，接下来要判断游戏怎么结束？两个人中只要一个人的牌出完了，游戏也就结束了。因此，需要在模拟两人出牌代码的外面加一个while循环来判断。

while(q1.head<q1.tail && q2.head<q2.tail)

最后一步，打印出谁最终赢得了游戏，以及游戏结束后获胜者手中的牌和桌上的牌。假如A获胜了那么B的手中一定是没有牌了（队列q2 为空）。

if(q2.head==q2.tail){	printf("A赢了\n");	printf("A当前手中的牌是")；	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桌上已经没有牌了");   }

四、算法优化

在上面算法分析中，判断能否赢牌，是通过枚举桌上每一张牌来实现的，即用了一个for循环来依次判断桌上的每一张牌是否与打出的牌相同。其实这个步骤还可以优化，就是用一个数组来记录桌上有哪些牌，因为牌面有9种，就是1-9，因此：int book[10]。

刚开始桌面上一张牌也没有，所以book[1]-book[10]都初始化为0：

for(i=1;i<=9;i++) book[i]=0;

接着，如果桌面增加一张牌面为“3”的牌，那就需要将book[3]设置为1,表示桌面已经有“3”的这张牌。如果这张“3”的牌被拿走，book[3]重新设置为0。

if(book[temp]==0)		//表明桌上没有牌面为 temp 的牌		{			//A 此轮没有赢牌			q1.head++;			//A 已经打出一张牌，所以要把打出的牌出队 			s.top++;			s.data[s.top]=t;			//再把打出的牌放到桌上，即入栈			book[temp]=1;			//标记桌上现在已经有牌面为 t 的牌 		} 

小猫钓鱼游戏算法讨论这里，具体实现方法都说完了，下面给合完整代码：

#include <stdio.h>struct queue{    int data[1000];    int head;    int tail;};struct stack{    int data[10];    int top;};int main(){    struct queue q1,q2;    struct stack s;    int book[10];    int i,temp;    //初始化队列    q1.head=1;    q1.tail=1;    q2.head=1;    q2.tail=1;    //初始化栈    s.top=0;    //初始化用来标记的数组，用来标记哪些牌已经在桌上    for(i=1;i<=9;i++)        book[i]=0;    //依次向队列插入6个数    // A手上的6张牌    for(i=1;i<=6;i++){        scanf("%d",&q1.data[q1.tail]);        q1.tail++;    }    //B手上的6张牌    for(i=1;i<=6;i++){        scanf("%d",&q2.data[q2.tail]);        q2.tail++;    }    while(q1.head<q1.tail && q2.head<q2.tail)        //当队列 q1和 q2都不为空的时候执行循环    {        temp=q1.data[q1.head];        // A出一张牌        //判断A当前打出的牌是否能赢牌        if(book[temp]==0)            //表明桌上没有牌面为 temp 的牌        {            //A此轮没有赢牌            q1.head++;            //A 已经打出一张牌，所以要把打出的牌出队            s.top++;            s.data[s.top]=temp;            //再把打出的牌放到桌上，即入栈            book[temp]=1;            //标记桌上现在已经有牌面为 t 的牌        }        else        {            q1.head++;            q1.data[q1.tail]=temp;            q1.tail++;            while(s.data[s.top]!=temp){                book[s.data[s.top]]=0;                q1.data[q1.tail]=s.data[s.top];                q1.tail++;                s.top--;            }        }        temp=q2.data[q2.head];        if(book[temp]==0){            q2.head++;            s.top++;            s.data[s.top]=temp;            book[temp]=1;        }        else{            q2.head++;            q2.data[q2.tail]=temp;            q2.tail++;            while(s.data[s.top]!=temp){                book[s.data[s.top]]=0;                q2.data[q2.tail]=s.data[s.top];                q2.tail++;                s.top--;            }        }    }    if(q2.head==q2.tail){        printf("A赢了\n");        printf("A当前手中的牌是");        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("B赢了\n");        printf("B当前手中的牌是");        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;}

测试结果如下：

【参考文献】数据结构(C语言版）、《啊哈！算法》