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

一：题目

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

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

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

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

二：思想

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;
}

四：运行结果