网站门户设计,电子商务网络运营,竞价网站移动端,杭州职工业能力建设网站第三部分、栈(Stack)和队列(Queue)详解 栈和队列#xff0c;严格意义上来说#xff0c;也属于线性表#xff0c;因为它们也都用于存储逻辑关系为 一对一 的数据#xff0c;但由于它们比较特殊#xff0c;因此将其单独作为一章#xff0c;做重点讲解。
使用栈… 第三部分、栈(Stack)和队列(Queue)详解 栈和队列严格意义上来说也属于线性表因为它们也都用于存储逻辑关系为 一对一 的数据但由于它们比较特殊因此将其单独作为一章做重点讲解。
使用栈结构存储数据讲究“先进后出”即最先进栈的数据最后出栈使用队列存储数据讲究 先进先出即最先进队列的数据也最先出队列。
既然栈和队列都属于线性表根据线性表分为顺序表和链表的特点栈也可分为顺序栈和链表队列也分为顺序队列和链队列这些内容都会在本章做详细讲解。
十一、[数据结构实践项目]扑克牌游戏包含C语言实现代码
小时候在刚开始接触扑克牌的时候最初学会的扑克游戏就是类似于“推小车”这样的无脑游戏本节带领大家使用学过的知识编写推小车卡牌游戏。 “推小车”扑克牌游戏适合 2-3 个人玩游戏规则也超级简单将一副扑克牌平均分成两份每人拿一份每个人手中的扑克牌全部反面朝上叠成一摞。游戏进行时每个人轮流拿出第一张扑克牌放到桌上将其排成一竖行。如果打出的牌与桌上某张牌的数字红桃 5 和黑桃 5 在此游戏中相等相等即可将两张相同的牌以及两张中间所夹的所有的牌全部取走每次取走的一小摞牌都必须放到自己本摞的下面。 游戏过程中一旦有人手中没有牌则宣布另一人获胜同时游戏结束。
1、设计思路
假设模拟两个人进行该扑克牌游戏。每个人在游戏过程中都是不断地从自己这一摞扑克牌的最上方去取牌放到桌子上当发现自己的牌同桌子上的牌相等时将赢得的牌依次放在自己扑克牌的下方。这是典型的队列的“先进先出”。而对于桌子而言就相当于是一个栈。每次放到桌子上的扑克牌都相当于进栈当有相同的扑克牌时相同的扑克牌连通之间的所有的扑克牌则依次出栈。 所以模拟该扑克牌游戏需要同时使用 2 个队列和 1 个栈。
2、实现代码 #include stdio.h #include stdlib.h struct queue { int data[1000]; int head; int tail; }; struct stack { int data[10]; int top; }; void showCard(struct queue *q,int *book,struct stack *s){ int t(*q).data[(*q).head]; //打出一张牌即从队列 q 的队头取元素此时还不往桌子的栈里放 //判断取出的这张牌是否会赢牌 if(book[t]0){ //若不赢牌只需放到桌子上入栈即可 (*q).head;//由于此时牌已经打出所以队列的队头需要前进 (*s).top; (*s).data[(*s).top]t; //再把打出的牌放到桌上即入栈 book[t]1; //标记桌上现在已经有牌面为t的牌 } else{ (*q).head;//由于此时已经打出去一张牌所以队头需要 1 (*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--; } //最后别忘了将最后一张相等的牌取出放入队列 book[(*s).data[(*s).top]]0; (*q).data[(*q).tail](*s).data[(*s).top]; (*q).tail; (*s).top--; } } int main() { struct queue q1,q2;//两个队列分别模拟两个人假设分别为小王和小李 struct stack s;//栈模拟桌子 int book[14];//为了便于判断桌子上的牌是否有相同的增加一个数组用于判断 int i; //初始化队列 q1.head0; q1.tail0; q2.head0; q2.tail0; //初始化栈 s.top-1; //初始化用来标记的数组 for(i0;i13;i) book[i]0; //假设初期每个人手中仅有 6 张牌每个人拥有的牌都是随机的但都在 1-13 之间 for(i1;i6;i){ q1.data[q1.tail]rand()%131; q1.tail; } for(i1;i6;i){ q2.data[q2.tail]rand()%131; q2.tail; } //仅当其中一个人没有牌时游戏结束 while(q1.headq1.tail q2.headq2.tail ){ showCard(q2, book, s);//小李出牌 showCard(q1, book, s);//小王出牌 } //游戏结束时输出最后的赢家以及手中剩余的牌数 if(q2.headq2.tail){ printf(小李赢\n); printf(手中还有%d 张牌,q1.tail-q1.head); } else{ printf(小王赢\n); printf(手中还有%d 张牌,q2.tail-q2.head); } return 0; } 运行结果 小王赢 手中还有7 张牌 十二、栈和队列是线性结构包含栈和队列的区别和共同点
很多学员问栈和队列是线性结构吗这里再次强调栈和队列是线性结构。 数据结构中如果想知道存储结构之间是否相同和类似只需要比对它们存储的目标数据之间的逻辑关系即可所存储数据的逻辑关系相同则说明它们是同一类存储结构反之则不是。 通过前面的学习我们知道线性结构即用于存储逻辑关系为 一对一 数据的存储结构例如顺序存储结构和链式存储结构。 图 1 栈存储结构
回过头再分析栈如图 1 所示栈结构中存储的也是逻辑关系为 一对一 的数据只不过该结构对数据的存储顺序有额外的要求即数据进栈和出栈要满足 先进后出 的要求。因此可以这么说栈是一种特殊的线性存储结构。 图 2 队列存储结构
那么队列存储结构如图 2 所示呢同栈一样它存储的也是逻辑关系为 一对一 的数据但它对数据入队和出队的要求是 先进先出。所以说队列也是一种特殊的线性存储结构。总的来说栈和队列是线性存储结构只不过它们比较 特殊 而已。 栈和队列除了都是线性结构外还有一个共同点那就是数据的进出只能在栈和队列的端点处进行。换句话说栈结构中数据的入栈和出栈只能在开口的一端进行队列中数据从一端进从另一端出。栈和队列最大的区别就是栈结构中存储数据要求 先进后出队列存储数据要求 先进先出。
