《啊哈！算法》 中 队列和栈的综合练习

本文主要是介绍《啊哈！算法》 中 队列和栈的综合练习，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

/*
	queen and stack practice
	
	题来自 啊哈!算法
	
	描述：
	星期天小哼和小哈约在一起玩桌游，他们正在玩一个非常古怪的扑克游戏——“小猫钓鱼”。游戏的规则是这样的：将一副扑克牌平均分成两份，每人拿一份。小哼先拿出手中的第一张扑克牌放在桌上，然后小哈也拿出手中的第一张扑克牌，并放在小哼刚打出的扑克牌的上面，就像这样两人交替出牌。出牌时，如果某人打出的牌与桌上某张牌的牌面相同，即可将两张相同的牌及其中间所夹的牌全部取走，并依次放到自己手中牌的末尾。当任意一人手中的牌全部出完时，游戏结束，对手获胜。假如游戏开始时，小哼手中有 6 张牌，顺序为 2 4 1 2 5 6，小哈手中也有 6 张牌，顺序为 3 1 3 5 6 4，最终谁会获胜呢？现在你可以拿出纸牌来试一试。接下来请你写一个程序来自动判断谁将获胜。这里我们做一个约定，小哼和小哈手中牌的牌面只有 1~9。
	分析：
	我们先来分析一下这个游戏有哪几种操作。小哼有两种操作，分别是出牌和赢牌。这恰好对应队列的两个操作，出牌就是出队，赢牌就是入队。小哈的操作和小哼是一样的。而桌子就是一个栈，每打出一张牌放到桌上就相当于入栈。当有人赢牌的时候，依次将牌从桌上拿走，这就相当于出栈。那如何解决赢牌的问题呢？赢牌的规则是：如果某人打出的牌与桌上的某张牌相同，即可将两张牌以及中间所夹的牌全部取走。那如何知道桌上已经有哪些牌了呢？最简单的方法就是枚举桌上的每一张牌，当然也有更好的办法我们待会再说。OK，小结一下，我们需要两个队列、一个栈来模拟整个游戏。

	
	书上的解答没有把栈中前面的那个数拿走 如 3 2 3; 只是取走2 3。
	在下面的代码注释地方已解释清楚，该代码显示了每一次跑完显示栈的元素，可自测。
*/


#include<iostream>
using namespace std;

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

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


int main(void)
{
	struct queen meng, hu;
	struct stack s;
	// respresent stack  where the number appear(0 - 9)
	int book[10] = {0};
	int tmp = 0;
	// init queen and stack
	meng.head = 1; meng.tail = 1;
	hu.head = 1; hu.tail = 1;
	// indicate no card
	s.top = 0;
	
	int cyc = 0;
	// queen add number
	for(int i = 1; i < 7; i++) cin >> meng.data[meng.tail++];
	for(int i = 1; i < 7; i++) cin >> hu.data[hu.tail++];
	
	// Case-by-case discussion meng and hu
	while(meng.head < meng.tail && hu.head < hu.tail)
	{
		// case meng 
		tmp = meng.data[meng.head];
		// judge stack if exist meng.data[meng.head] number
		if(book[tmp] == 0)
		{
			meng.head++;
			s.data[++s.top] = tmp;
			book[tmp] = 1;
		}else{
			meng.head++;
			meng.data[meng.tail++] = tmp;
			while(s.data[s.top] != tmp) 
			{
				book[s.data[s.top]] = 0;
				meng.data[meng.tail] = s.data[s.top];
				meng.tail++;
				s.top--;
			}
            // 书上答案没有取前面的数，在这里加上这一句
				book[s.data[s.top]] = 0;
				hu.data[hu.tail] = s.data[s.top];
				hu.tail++;
				s.top--;
//		执行顺序好像有问题 不能代替上面的	meng.data[meng.tail++] = s.data[s.top--];
		}
		
		
		// case hu
		tmp = hu.data[hu.head];
		// judge stack if exist meng.data[meng.head] number
		if(book[tmp] == 0)
		{
			hu.head++;
			s.top++;
			s.data[s.top] = tmp;
			book[tmp] = 1;
		}else{
			hu.head++;
			hu.data[hu.tail++] = tmp;
			while(s.data[s.top] != tmp) 
			{
				book[s.data[s.top]] = 0;
				hu.data[hu.tail] = s.data[s.top];
				hu.tail++;
				s.top--;
			}
				book[s.data[s.top]] = 0;
				hu.data[hu.tail] = s.data[s.top];
				hu.tail++;
				s.top--;
            
//		执行顺序好像有问题 不能代替上面的	hu.data[hu.tail++] = s.data[s.top--];
		}
		
		// every 
		for(int i = 1; i <= s.top; i++) cout << s.data[i] << ' ';
		cout << endl << ++cyc << "  frequency" << endl << endl;
			
	}
	
	// boundary
	if(meng.head == meng.tail)
	{
		cout << "hu win" << endl;
		cout << "hu's card:" << endl;
		for(int i = hu.head; i < hu.tail; i++) cout << hu.data[i] << ' ';
		cout << endl;
		if(s.top > 0)
		{
			cout << "stack's card: " << endl;
			for(int i = 1; i <= s.top; i++) cout << s.data[i] << ' ';
			cout << endl;
		}else{
			cout << "stack is not card!!!" << endl;
		}
	}
	
	if(hu.head == hu.tail)
	{
		cout << "meng win" << endl;
		cout << "meng's card:" << endl;
		for(int i = meng.head; i < meng.tail; i++) cout << meng.data[i] << ' ';
		cout << endl;
		if(s.top > 0)
		{
			cout << "stack's card: " << endl;
			for(int i = 1; i <= s.top; i++) cout << s.data[i] << ' ';
			cout << endl;
		}else{
			cout << "stack is not card!!!" << endl;
		}
	}
	getchar();
	return 0;
}

这篇关于《啊哈！算法》 中 队列和栈的综合练习的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！