数据结构：“小猫钓鱼游戏”

一：题目

栈和队列的综合应用：“小猫钓鱼”的游戏规则是：将一副扑克牌平均分成两份，每人拿一份。玩家甲先拿出手中的第一张扑克牌放在桌上，然后玩家乙也拿出手中的第一张扑克牌，并放在玩家甲刚打出的扑克牌的上面，就像这样两个玩家交替出牌。出牌时，如果某人打出的牌与桌上某张牌的牌面相同，即可将两张相同的牌及其中间所夹的牌全部取走，并依次放到自己手中牌的末尾。当任意一个人手中的牌全部出完时，游戏结束，对手获胜。

要求编写程序来模拟这场游戏，并判断出谁最后获胜，获胜的同时打印出获胜者手中的牌以及桌上可能剩余的牌。（应用性设计内容）

为了简化实现，先做这样一个约定，玩家甲和乙手中牌的牌面值只有1-9。

测试样例（测试样例均采用输入前规定当前发牌数量的方式）

序号	输入	输出
1	请输入发牌数：6 玩家甲：2 4 1 2 5 6 玩家乙：3 1 3 5 6 4	游戏结束：玩家乙赢玩家乙手中牌为：6 5 2 3 4 1 桌面上还有牌为：3 4 5 6 2 1
2	请输入发牌数：8 玩家甲：5 4 1 3 7 9 6 2 玩家乙：6 2 4 8 5 7 1 3	游戏结束：玩家乙赢玩家乙手中牌为：4 1 2 4 5 7 8 3 6 5 桌面上还有牌为：9 7 6 1 2 3
3	请输入发牌数：9 玩家甲：3 4 5 6 2 1 8 7 9 玩家乙：6 5 2 3 4 1 9 7 8	游戏结束：玩家甲赢玩家乙手中牌为：2 1 6 3 4 2 9 8 9 5 6 3 7 5 桌面上还有牌为：1 4 8 7

二：思想

1.玩家手中的牌可看成队列，桌上牌看成栈。

2.判断是否和桌上牌某张相同时，可用遍历，或设个buff数组，用下标代表牌，值代表在不在

1代表在，0代表不在。如buff【1】=1，表示牌面为1的牌已经存在，需相关操作。

3.其他就是出栈入栈出队入队

三：代码

new可替换malloc delete替代free

#include<iostream>
using namespace std;
int buff[10] = { 0 };typedef int  QElemType;
typedef struct QNode
{QElemType data;struct QNode* next;
}QNode, * QueuePtr;
typedef struct
{QueuePtr front;QueuePtr rear;
}LinkQueue;
void initQueue(LinkQueue& q)
{q.front = new QNode;q.front->next = nullptr;q.rear = q.front;}
void pushQueue(LinkQueue& q, QElemType x)
{QueuePtr p = new QNode;p->data = x;p->next = nullptr;q.rear->next = p;q.rear = p;}
void popQueue(LinkQueue& q, QElemType& e)
{e = 0;QueuePtr p;if (q.rear == q.front) {return;}p = q.front->next;e = p->data;q.front->next = p->next;if (p == q.rear)q.rear = q.front;delete p;}
bool emptyQueue(LinkQueue& q)
{return q.front == q.rear;
}
QElemType gettopQueue(LinkQueue& q)
{if (emptyQueue(q)) {return -1;}else return  q.front->next->data;
}
void clearQueue(LinkQueue& q)
{while (q.front->next){QueuePtr p = q.front->next;q.front->next = p->next;delete p;}q.rear = q.front;
}
void destroyQueue(LinkQueue& q)
{while (q.front){q.rear = q.front->next;delete q.front;q.front = q.rear;}
}
void displayQueue(LinkQueue& q)
{if (emptyQueue(q)) {  return; }QueuePtr  p = q.front->next;while (p){cout << p->data; cout << " ";p = p->next;}
}
/// <summary>
/// /
/// </summary>typedef int SElemType;
#define minsize 100
typedef struct
{SElemType* base;SElemType* top;int stacksize;
}SqStack;
void initStack(SqStack& s)
{s.base = new SElemType[minsize];s.top = s.base;s.stacksize = minsize;
}
void pushStack(SqStack& s, SElemType x)
{if (s.top - s.base == s.stacksize) {SElemType* tmp = new SElemType[100];int i = 0;while (s.base != s.top) {tmp[i] = *s.top; i++;s.top++;}s.base = tmp;}*s.top = x;s.top++;
}
bool emptyStack(SqStack& s)
{return s.base == s.top;
}
void popStack(SqStack& s, SElemType& e)
{if (emptyStack(s)) {return;}e = *(s.top - 1);s.top--;}
void gettopStack(SqStack& s, SElemType& e)
{if (emptyStack(s)) {return;}e = *(s.top - 1);}
void clearStack(SqStack& s)
{SElemType e;while (!emptyStack(s)){popStack(s, e);}
}
void destroyStack(SqStack& s)
{delete[] s.base;s.base = s.top = nullptr;s.stacksize = 0;
}
void displayStack(SqStack S)
//输出顺序栈S中所有元素的值,顺序为从栈底到栈顶
{SElemType* p;if (S.base == S.top)               //如果栈空{printf("The Stack is NULL\n");return;}for (p = S.base; p < S.top; p++)cout << *p;cout << endl;}
void add(LinkQueue& q,SqStack& s,int e)
{pushQueue(q, e);int f;while (1){gettopStack(s, f);if (f == e) { pushQueue(q, e); popStack(s, f); buff[f] = 0; break; }pushQueue(q, f); popStack(s, f); buff[f] = 0;}
}
int main()
{LinkQueue q1, q2; initQueue(q1); initQueue(q2);cout << "请输入发牌数:";int n; cin >> n; int i = 0, j = 0,k=0;cout << "请给玩家甲发牌:";while (i != n){QueuePtr p = new QNode;cin >> p->data;pushQueue(q1, p->data); i++;}cout << "请给玩家乙发牌:";while (j != n){QueuePtr p = new QNode;cin >> p->data;pushQueue(q2, p->data); j++;}cout << "游戏开始:" << endl;cout << "玩家甲手里的牌为" << endl;displayQueue(q1); cout  << endl;cout << "玩家乙手里的牌为" << endl;displayQueue(q2); cout << endl;SqStack s;initStack(s);int e, f;while (k != n){if (emptyQueue(q1) || emptyQueue(q2)) break;popQueue(q1, e);if (buff[e] == 1) { add(q1, s, e); }else { buff[e] = 1; pushStack(s, e); }popQueue(q2, f);if (buff[f] == 1) { add(q2, s, f); }else {buff[f] = 1; pushStack(s, f);}}if (emptyQueue(q1)){cout << "游戏结束:玩家乙赢" << endl;cout << "玩家乙手里的牌为："; displayQueue(q2);cout << "桌面上还有牌为："; displayStack(s);}else{cout << "游戏结束:玩家甲赢" << endl;cout << "玩家甲手里的牌为："; displayQueue(q1);cout << "桌面上还有牌为："; displayStack(s);}return 0;
}