数据结构学习（八）栈和队列案例分析

目录介绍：1。堆栈和队列2的定义。纸牌游戏3的规则。算法分析与实现4。算法优化我们之前学过堆栈和队列的基本原理，先回忆一下它们的作用：堆栈主要是解决子程序的调用和返回；而排队主要是解决先到先得的问题。

现在应用堆栈和队列原理解决现实中的基本案例。I .堆栈和队列的定义

Stack也叫栈，是一个线性表，操作有限。限制是只允许表的一端插入和删除。这一端叫做栈顶，反之，另一端叫做栈底。向堆栈中插入新元素也称为堆栈。。、堆栈。。或堆栈压入。

就是把新元素放在栈顶元素的上面，使之成为新的栈顶元素；从堆栈中删除一个元素也称为堆栈生成或堆栈撤销。就是删除栈顶元素，使其相邻元素成为新的顶元素。

队列是一种先进先出的线性表，简称FIFO。在表格的一端(页脚)插入，在另一端(页眉)删除。表插入操作称为入队，表提取操作称为出列。第二，纸牌游戏的规则

记得小时候，我们喜欢玩一个古老的游戏——小猫钓鱼。它的规则是：

把一副扑克牌分成两等份，每人拿一张。A先把手中的第一张扑克牌拿出来放在桌上，然后B也把手中的第一张扑克牌拿出来放在A刚刚打出的扑克牌上面。

打牌时，如果有人打出和桌上一张牌一样的牌，可以把所有一样的牌和夹在中间的牌，依次放在自己牌的末尾。当任何人手里的牌都打完了，游戏就结束了，对手赢了。

如果在游戏开始时，A手里有6张牌，顺序是2 4 1 2 5 6，B手里也有6张牌，顺序是3 1 3 5 6 4。最后谁会赢？

这里我们分析一下游戏的几种操作：打牌和赢牌，用队列模拟：打牌。。离队，赢牌。。入队，A和B都是同样的操作。牌桌相当于一个叠，桌上打出的每一张牌都相当于进入叠。当有人赢了牌，

把桌面上的牌拿走是很出格的。三、算法分析与实现

根据上面的分析，我们需要创建两个队列和一个堆栈来模拟整个游戏。首先，我们需要创建一个队列结构来实现出牌和赢牌的情况：

结构队列{ int data[1000]；int headint tail}head用于存储队列的头部，tail用于存储队列的尾部。数组数据用于存储队列中的元素。

可以将该大小设置得更大，以防止数组越界。

创建另一个结构实现栈，相当于放卡片的桌子：

结构堆栈{ int data[10]；int top};Top用于存储栈顶，数组数据用于存储栈中的元素。大小设置为10，因为假设只有9种不同的卡。

因此数组大小被设置为10。

假设q1用来模拟A手里的牌，q2用来模拟B手里的牌，定义一个变量S把牌放在桌面上，定义如下：

结构队列q1、Q2；结构堆栈；接下来，初始化队列和堆栈：

//初始化队列q1和q2为空，双手无卡Q1 . head=1；Q1 . tail=1；Q2 . head=1；Q2 . tail=1；//初始化堆栈s为空，

当初桌上没有牌s . top=0；然后先把A和B手里的牌读一遍，读两遍，分别插入q1和q2。

//先读6张牌，

放在A手里for(I=1；I=6；i ){scanf('%d 'Q1 . data[Q1 . tail])；//读取一个数字到队列的末尾q1.tail//在行尾后移一位}//多读六张牌。

放在B手里for(I=1；I=6；i ){scanf('%d 'Q2 . data[Q2 . tail])；//读取一个数字到队列的末尾q2.tail//队列末尾后移一位}程序的准备工作基本完成。

游戏正式开始，首先播放：

temp=q1.data[q1.head];A打出第一张牌，也就是q1的队首，先将这张牌存放在临时变量temp中，判断桌上的牌与temp 有没有相同的，枚举桌上的每一张牌与temp 进行比对：

flag=0;for(i=1;i=top;i++){if(temp==s[i]){flag=1;break;}}如果flag 的值为0 就说明A没能赢得桌上的牌，将打出的牌留在桌上。

if(flag==0){//A 此轮没有赢牌q1.head++;//A已经打出一张牌，所以要把打出的牌出队s.top++;s.data[s.top]=temp; //再把打出的牌放到桌上，

即入栈}如果flag 的值为1，就表明A 可以赢得桌上的牌，注意：首先把刚才打出的牌先放到手中牌的末尾，再把将赢得的牌依次放入A 的手中。

if(flag==1){//A 此轮可以赢牌q1.head++;//A 已经打出一张牌，所以要把打出的牌出队q1.data[q1.tail]=temp;//因为此轮可以赢牌，

所以紧接着把刚才打出的牌又放到手中牌的末尾q1.tail++;while(s.data[s.top]!=temp)//把桌上可以赢得的牌（从当前桌面最顶部的一张牌开始取，

直到取到与打出的牌相同为止//依次放到手中牌的末尾{q1.data[q1.tail]=s.data[s.top];//依次放入队尾q1.tail++;s.top--;//栈中少了一张牌，

所以栈顶要减1 } } A出牌的所有步骤模拟完了，B的出牌结果也是这样，接下来要判断游戏怎么结束？两个人中只要一个人的牌出完了，游戏也就结束了。因此，

需要在模拟两人出牌代码的外面加一个while循环来判断。

while(q1.head最后一步，打印出谁最终赢得了游戏，以及游戏结束后获胜者手中的牌和桌上的牌。假如A获胜了那么B的手中一定是没有牌了（队列q2 为空）。

if(q2.head==q2.tail){printf('A赢了\n');printf('A当前手中的牌是')；for(i=q1.head;i=q1.tail-1;i++) printf(' %d',q1.data[i]);if(s.top0)//如果桌上有牌则依次输出桌上的牌{printf('\n桌上的牌是');for(i=1;i=s.top;i++) printf(' %d',s.data[i]); } else { printf('\n桌上已经没有牌了'); }四、算法优化

在上面算法分析中，判断能否赢牌，是通过枚举桌上每一张牌来实现的，即用了一个for循环来依次判断桌上的每一张牌是否与打出的牌相同。其实这个步骤还可以优化，就是用一个数组来记录桌上有哪些牌，

因为牌面有9种，就是1-9，因此：int book[10]。

刚开始桌面上一张牌也没有，所以book[1]-book[10]都初始化为0：

for(i=1;i=9;i++) book[i]=0;接着，如果桌面增加一张牌面为“3”的牌，那就需要将book[3]设置为1,表示桌面已经有“3”的这张牌。如果这张“3”的牌被拿走，

book[3]重新设置为0。

if(book[temp]==0)//表明桌上没有牌面为temp 的牌{//A 此轮没有赢牌q1.head++;//A 已经打出一张牌，

所以要把打出的牌出队s.top++;s.data[s.top]=t;//再把打出的牌放到桌上，即入栈book[temp]=1;//标记桌上现在已经有牌面为t 的牌} 小猫钓鱼游戏算法讨论这里，

具体实现方法都说完了，下面给合完整代码：

#include struct queue{ int data[1000]; int head; int tail;};struct stack{ int data[10]; int top;};int main(){ struct queue q1,q2; struct stack s; int book[10]; int i,temp; //初始化队列 q1.head=1; q1.tail=1; q2.head=1; q2.tail=1; //初始化栈 s.top=0; //初始化用来标记的数组，

【参考文献】数据结构(C语言版）、 《啊哈！算法》