数据结构与算法教程，数据结构C语言版教程！（第三部分、栈(Stack)和队列(Queue)详解）六

 第三部分、栈(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.head=0; q1.tail=0;

        q2.head=0; q2.tail=0;

        //初始化栈

        s.top=-1;

        //初始化用来标记的数组

        for(i=0;i<=13;i++)

                book[i]=0;

        //假设初期每个人手中仅有 6 张牌，每个人拥有的牌都是随机的，但都在 1-13 之间

        for(i=1;i<=6;i++){

                q1.data[q1.tail]=rand()%13+1;

                q1.tail++;

        }

        for(i=1;i<=6;i++){

                q2.data[q2.tail]=rand()%13+1;

                q2.tail++;

        }

        //仅当其中一个人没有牌时，游戏结束

        while(q1.head<q1.tail && q2.head<q2.tail ){        showCard(&q2, book, &s);//小李出牌

                showCard(&q1, book, &s);//小王出牌

        }

        //游戏结束时，输出最后的赢家以及手中剩余的牌数

        if(q2.head==q2.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 所示）呢？同栈一样，它存储的也是逻辑关系为 "一对一" 的数据，但它对数据入队和出队的要求是 "先进先出"。所以说，队列也是一种特殊的线性存储结构。

总的来说，栈和队列是线性存储结构，只不过它们比较 "特殊" 而已。

栈和队列，除了都是线性结构外，还有一个共同点，那就是数据的进出，只能在栈和队列的端点处进行。换句话说，栈结构中，数据的入栈和出栈只能在开口的一端进行；队列中，数据从一端进，从另一端出。

栈和队列最大的区别就是，栈结构中存储数据要求 "先进后出"；队列存储数据要求 "先进先出"。