目录介绍：
一、栈与队列的定义
二、纸牌游戏的规则
三、算法分析与实现
四、算法优化
前面学习了栈和队列的基本原理，先回忆一下它们的作用：栈主要是解决子程序的调用和返回；而列队主要是解决先来先服务的问题。现在应用栈与队列的原理来解决现实中基本的案例。
一、栈与队列的定义
栈（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语言版）、《啊哈！算法》
,
