栈与队列的综合应用
【栈的定义】
栈是限定仅在表尾进行插入和删除操作的线性表，栈的插入就是压栈，栈的删除就是出栈，为后进先出结构，出栈的地方叫做栈顶。
一共有两种栈的存储方式，一种顺序栈，通常由数组实现，另一种链栈，由单链表指针实现，顺序栈选择数组首元素作为栈顶，链栈选择头指针位置作为栈顶。
【队列定义】
1、队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
2、与栈相反，队列是一种先进先出的线性表.
3、实现一个队列同样需要顺序表或链表作为基础。
（头结点不是必要的，但为了方便操作还是加上）
（空队列时，front和rear都指向头结点。）
【纸牌游戏】
“小猫钓鱼”的游戏规则是这样的：将一副扑克牌平均分成两份，每人拿一份。玩家U1先拿出手中的第一张扑克牌放在桌上，然后玩家U2也拿出手中的第一张扑克牌，并放在玩家U1刚打出的扑克牌的上面，就像这样两个玩家交替出牌。出牌时，如果某人打出的牌与桌上某张牌的牌面相同，即可将两张相同的牌及其中间所夹的牌全部取走，并依次放到自己手中牌的末尾。当任意一个人手中的牌全部出完时，游戏结束，对手获胜。
现在要求你写一个算法来模拟这场游戏，并判断出谁最后获胜，获胜的同事打印出获胜者手中的牌以及桌上可能剩余的牌。
在写程序开始前，我们暂且先做一个约定，玩家U1和U2手中牌的牌面值只有1~9。
解法思路
我们可以先分析一下这个游戏存在哪几种操作。玩家U1有两种操作，分别是出牌和赢牌，出牌时将手中的牌打出去，赢牌的时候将桌上的牌放到手中牌的末尾，这恰好对应了队列的两个操作，出牌就是队列出队，赢牌就是队列入队。玩家U1和玩家U2的操作是一样的。而桌子很明显就可以看作是一个栈，玩家没打出一站牌就放到桌上，相当于入栈，因为顺序是往后的，当有人赢牌的时候，依次将牌从桌上拿走，这就相当于出栈。那如何判断是否赢牌呢？赢牌的判断就是：如果某人打出的牌与桌上的某张牌相同，即可将两张牌及其中间的所夹得牌全部取走。那如何直到桌上现在有哪些牌呢，很容易想到的就是每次打出牌之后遍历一遍桌上已有的牌然后比对，存在相同的牌则算赢牌。这是简单而且粗暴一点的方法，其实有更好的方法，那就是用桶来解决这个问题，牌面值只有1-9，我们可以设置一个大小为10的数组作为桶，每打出一张牌，就以此牌的牌面值作为下标找到数组对应位置，如果该位置存在值，则说明桌上有存在的牌，如果没有值，则说明桌上没有相同的牌，同时在通上做标记，即数组该下标位置设置为1。那如果赢牌了，桌上的牌拿走了桶应该怎么办呢？也很简单，出栈的时候依次按照牌面值清空桶就行了。最终怎么判断哪个玩家获得最终胜利呢，获得最终胜利的标准就是对方手上已经没牌了，如果从队列角度看，那就是头指针和尾指针相等了。
从上面的思路分析可以看出，为了模拟这场游戏，我们需要准备两个队列、一个栈和一个桶，分别表示玩家U1U2手中的牌、桌上的牌以及桌上牌的牌面值。下面我们写具体的代码，为了方便阅读，关键代码上面我都给出非常详细的注释。
首先创建两个结构体，一个表示栈一个表示队列
struct duilie
{
int head;
int tail;
int data[1000];
};
struct zhan
{
int top;
int data[1000];
};
初始化队列的头结点尾节点，利用for循环初始化桶
两个for循环输入分别输入6个数字进入队列
struct duilie q1,q2;
struct zhan s;
int book[10];
int i,t;
q1.head=0;
q1.tail=0;
q2.head=0;
q2.tail=0;
s.top=0;
for(i=0;i<10;i++)
{
book[i]=0;
}
for(i=0;i<6;i++)
{
scanf("%d",&q1.data[q1.tail]);
q1.tail++;//每输入一个数字队尾加一
}
for(i=0;i<6;i++)
{
scanf("%d",&q2.data[q2.tail]);
q2.tail++;//每输入一个数字队尾加一
}
小哼出牌
t=q1.data[q1.head];//将小哼打出的牌存放在临时变量t中
if(book[t]==0)//如果桶中没有这张牌，表示此回合并没有赢牌
{
q1.head++;//将牌从队列中取出
s.top++;//将取出的牌放在桌子上，由于桌子代表栈，所以栈顶+1
s.data[s.top]=t;//将取出的牌放在桌子上
book[t]=1;//将桌子上的牌放入桶中，标记为1，证明桌子上存在刚刚打出的这张牌
}
else//赢牌
{
q1.head++;//将牌从队列中取出
q1.data[q1.tail]=t;//由于赢牌将刚刚打出的牌放回手中，也就是队尾
q1.tail++;//队尾+1
while(s.data[s.top]!=t)//如果桌子上的牌不是刚刚打出的牌，则全部收走
{
book[s.data[s.top]]=0;//取消桶中的标记
q1.data[q1.tail]=s.data[s.top];//讲桌上的牌放入手中
q1.tail++;//队尾+1
s.top--;//由于在桌子上取走牌，所以栈顶-1
}
book[s.data[s.top]]=0;//这张牌是t的牌，也就是与刚打出牌相同的牌，取消标记
q1.data[q1.tail]=s.data[s.top];//取出这张牌，放手里
q1.tail++;//手里多张牌，队尾+1
s.top--;//桌上少一张牌，栈顶-1
}
if(q1.head==q1.tail)//如果小哈没牌，则结束循环
{
break;
}
小哈出牌
同理
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;
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--;
}
book[s.data[s.top]]=0;
q2.data[q2.tail]=s.data[s.top];
q2.tail++;
s.top--;
}
}
判断如果小哼没牌时，则小哈赢
if(q1.head==q1.tail)
{
printf("小哈win\n");
printf("小哈手中的牌是");
for(i=q2.head;i<q2.tail;i++)//将队列的牌取出
{
printf("%d ",q2.data[i]);
}
printf("\n");
if(s.top>0)//如果桌子上还有牌
{
printf("桌上还有牌为");
for(i=1;i<s.top;i++)//将桌子上的牌取出
{
printf("%d ",s.data[i]);
}
}
printf("\n");
}
判断如果小哈没牌时，则小哼赢
else
{
printf("小哼win\n");
printf("小哼手中的牌是");
for(i=q1.head;i<q1.tail;i++)
{
printf("%d ",q1.data[i]);
}
printf("\n");
if(s.top>0)
{
printf("桌上还有牌为");
for(i=1;i<s.top;i++)
{
printf("%d ",s.data[i]);
}
}
printf("\n");
}
完整代码
#include<stdio.h>//玩牌游戏
struct duilie
{
int head;
int tail;
int data[1000];
};
struct zhan
{
int top;
int data[1000];
};
int main()
{
struct duilie q1,q2;
struct zhan s;
int book[10];
int i,t;
q1.head=0;
q1.tail=0;
q2.head=0;
q2.tail=0;
s.top=0;
for(i=0;i<10;i++)
{
book[i]=0;
}
for(i=0;i<6;i++)
{
scanf("%d",&q1.data[q1.tail]);
q1.tail++;
}
for(i=0;i<6;i++)
{
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.head++;
s.top++;
s.data[s.top]=t;
book[t]=1;
}
else
{
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--;
}
book[s.data[s.top]]=0;
q1.data[q1.tail]=s.data[s.top];
q1.tail++;
s.top--;
}
if(q1.head==q1.tail)
{
break;
}
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;
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--;
}
book[s.data[s.top]]=0;
q2.data[q2.tail]=s.data[s.top];
q2.tail++;
s.top--;
}
}
if(q1.head==q1.tail)
{
printf("小哈win\n");
printf("小哈手中的牌是");
for(i=q2.head;i<q2.tail;i++)
{
printf("%d ",q2.data[i]);
}
printf("\n");
if(s.top>0)
{
printf("桌上还有牌为");
for(i=1;i<s.top;i++)
{
printf("%d ",s.data[i]);
}
}
printf("\n");
}
else
{
printf("小哼win\n");
printf("小哼手中的牌是");
for(i=q1.head;i<q1.tail;i++)
{
printf("%d ",q1.data[i]);
}
printf("\n");
if(s.top>0)
{
printf("桌上还有牌为");
for(i=1;i<s.top;i++)
{
printf("%d ",s.data[i]);
}
}
printf("\n");
}
return 0;
}