堆疊

上一篇講的是佇列，是一種先進先出的資料結構，還有一種后進先出的資料結構，稱為堆疊，

堆疊限定為只能在一端進行插入和洗掉操作，比如往杯子里面放球，然后再往出拿，顯然，最后放入的球可以最先拿出來，

判斷回文

通過堆疊這個資料結構可以判斷一個字符是否是回文，

• 讀取字串

char a[101];
int len;
gets(a);
len=strlen(a);

• 如果一個字串是回文的話，那么它必須是中心對稱，求中點

mid=len/2-1;

• 將mid之前的字符全部入堆疊，此處堆疊用來存盤字符，所以此處用來實作堆疊的陣列型別是字符陣列，char s[101];，
• 初始化堆疊，top=0
• 入堆疊的操作top++;s[top]=x;（假設需要入堆疊的字符暫存在字符變數x中），簡寫成s[++top]=x;
• 代碼實作mid之前字符全部入堆疊

for(i=0;i<=mid;i++)
{
s[++top]=a[i];
}

• 判斷回文，將當前堆疊中的字符依次出堆疊，看是否能與mid之后的字符一一匹配，如果能匹配就是回文串，否則不是，

for(i=mid+1;i<=len-1;i++)
{
if(a[i]!=s[top])
{
break;
}
top--;
}
if(top==0)
printf("YES");
else
printf("NO");

當top=0時，說明堆疊內所有的字符都被一一匹配了，那么這個字符就是回文串，

下面附判斷回文串完整代碼：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//解密回文--堆疊
int main()
{
	char a[101],s[101];
	int i,len,mid,next,top;
	gets(a);//讀入字串
	len=strlen(a);//字串長度
	mid=len/2-1;//求字串中點
	top=0;//初始化堆疊
	//將mid前的字符依次入堆疊
	for(i=0;i<=mid;i++)
	s[++top]=a[i];
	
	//判斷字串長度是奇數還是偶數,并找出需要進行字符匹配的起始下標
	if(len%2==0) //偶數 
	next=mid+1;
	else //奇數 
	next=mid+2;
	//開始匹配
	for(i=next;i<=len-1;i++)
	{
		if(a[i]!=s[top])
			break;
			top--;	
	 }
	 //當top=0時,說明堆疊內所有的字符都被一一匹配了
	 if(top==0)
	 printf("YES\n");
	 else
	 printf("NO\n");
	 return 0; 
 } 

堆疊還可以用來進行驗證括號的匹配，

紙牌游戲——小貓釣魚

游戲規則：將一副撲克牌平均分成兩份，每人拿1份，小哼先拿出第一張撲克牌放在桌上，然后小哈也拿出手中的第一張撲克牌，并放在小哼剛打出的撲克牌上面，兩人交替出牌，出牌時，如果某人打出的牌和桌上某張牌牌面相同，即可將兩張相同的牌，及夾在其中間的牌全部拿走，并依次放在自己手中牌的末尾，當任意一個人手中的牌全部出完時，游戲結束，對手獲勝，
游戲開始時，小哼手中6張牌2,4,1,2,5,6，小哈手上也有6張牌3,1,3,5,6,4，牌面只有1~9，判斷是誰贏，

分析

對于玩家而言有2種操作：贏牌和出牌

• 贏牌：入隊
• 出牌：出隊

對于桌子而言有2種操作：牌被放到桌上和牌被從桌上拿走

• 牌放到桌子上：入堆疊
• 牌被拿走：出堆疊

兩個玩家，一張桌子，所以用兩個佇列，一個堆疊來模擬整個游戲，

完整代碼

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct queue
{
	int data[1000];
	int head;
	int tail;
 };
 struct stack
 {
 	int data[10];
 	int top;
 };
 int main()
 {
 	struct queue q1,q2;//小哼的撲克牌佇列q1,小哈的撲克牌佇列q2
	 struct stack s;//桌子上的撲克牌
	 int book[10];
	 int i,t;
	 //初始化佇列,q1,q2為空,兩人手中沒有牌 
	 q1.head=1;
	 q1.tail=1;
	 q2.head=1;
	 q2.tail=1;
	 //初始化堆疊,桌子上面沒有牌 
	 s.top=0;
	 //初始化用來標記的陣列,用來標記哪些牌已經在桌子上
	 //book[10]={0};不可取 
	 for(i=0;i<=9;i++)
	 {
	 	book[i]=0;//初始化	  
	  } 
	  //依次向佇列中插入6個數
	  //小哼手上有6張牌
	  for(i=1;i<=6;i++) 
	  {
	  	scanf("%d",&q1.data[q1.tail]);//讀入一個數到隊尾q1.data[1],q1.data[2]...
	  	q1.tail++;//隊尾往后挪一位,q1.tail=2,3... 
	  	
	   } 
	   //小哈手上有6張牌
	   for(i=1;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];//小哼出一張牌,q1.data[1]
			//判斷小哼當前打出的牌是否能贏牌
			if(book[t]==0)//如果桌面上沒有為t的牌
			{
				//桌面上沒有為t的牌,說明小哼此輪沒有贏牌
				q1.head++;//小哼打出一張牌,那么這張牌就出列
				s.top++;//桌面上多出一張牌,s.top=1
				s.data[s.top]=t;//s.data[1]=t,將小哼打出的一張牌放到桌上,入堆疊
				book[t]=1;//標記桌面上此時已有牌面為t的牌 
			 } 
			 else
			 {
			 	//小哼此輪可以贏0
				 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--;//堆疊中少了一張牌,所以堆疊頂減1 
				  } 
				  //識訓桌面上牌面為t的牌
				  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(q2.head==q2.tail)
		   {
		   	printf("小哼win\n");
		   	printf("小哼當前手中的牌是");
			   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("小哈win\n");
			 	printf("小哈當前手中的牌是");
				 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桌面上已經沒有牌了");
			  } 
			  getchar();getchar();
			  return 0;
 }
 

，，，好長的難代碼，自己一下子寫也寫不出來，這就是就是計算機模擬程序，之前涉足數模的時候，老師說要給一個模型就能用程式寫出來，我說我不能，，一個軟工的學生，多多少少得學點編程到時候還能混口飯的，，雖然數模是個水比賽，代碼大部分也是copy，，，但是我發現了計算機模擬程序是我一點都不會的，，，

結束

分割線

=============================================================
判斷每個人打出一張牌之后能否贏牌，可以通過列舉桌上的每一張牌來實作，用for回圈來依次判斷桌上的每一張牌是否與打出的牌相等，
上述代碼通過用一個陣列來記錄桌上有哪些牌
因為牌面只有1~9，所以開一個大小為10的陣列來記錄當前桌上已經有哪些牌面，
book[10]
沒有贏牌時和贏牌時代碼區別：
未贏牌時：

if(book[t]==0)
	{
		q.head++;//打出一張牌，所以將打出的牌出列
		s.top++;//桌面上多出一張牌
		s.data[s.top]=t;//s.top是指向堆疊頂的變數
	}

贏牌時：

//贏牌
else//book[t]==1
	{
		q.head++;//打出一張牌，將打出的牌出列
		q.data[q.tail]=t;//已經確定能贏牌，所以就將這張牌直接放到隊尾，即放到自己手中牌的末尾
		q.tail++;
		while(s.data[s.top]!=t)//桌上和自己打的牌不一樣的牌
		{
			book[s.data[s.top]]=0;//因為牌要取走，所以就取消標記
			q.data[q.tail]=s.data[s.top];//將桌上那些牌依次放入自己手中牌之后
			q.tail++;
			s.top--;//桌面上少了1張牌
		}
		//識訓桌面上為t的牌
		book[s.data[s.top]]=0;//取消標記
		q.data[q.tail]=s.data[s.top];
		q.tail++;
		s.top--;
	}

再次回看題目，程式模擬程序對應實際游戲程序
* 出牌——>出佇列
*桌面上多一張牌——>堆疊頂+1
*桌上少一張牌——>堆疊頂-1
*贏牌時，先將打出的牌立即放到自己手中牌的最后，然后將桌面上牌和自己手中不一樣的識訓手中，依次放到自己手中末尾
*最后再將桌上的和自己手中一樣的牌收了，放入手中牌最后

=============================================================
真的結束，有補充再說吧