巧用堆栈与队列解决扑克牌排序问题*

◆叶青 邹军华

作者：叶青、邹军华，湖北大学教育学院（430062）。

数据结构的主要内容包括将现实世界转化为在计算机世界中的抽象的数据描述，数据在计算机中的组织以及不同数据类型的基本操作实现等，是相对比较难于理解和掌握的课程。学生学习的积极性不仅关系到对数据结构课程的掌握程度，而且影响到对整个专业知识的掌握。因此，可以通过自己设计问题、分析问题并灵活运用所学知识解决问题的方式来增强学习兴趣。

本文通过数据结构中堆栈和队列的基本方法来解决一个扑克牌排序问题，通过C语言进行编程和调试程序，能够利用C语言编写简单程序，加深对教学内容的理解，验证所学的算法和数据结构，培养设计数据结构的能力和根据数据结构设计算法的能力，掌握非数值问题的数据结构和算法的设计方法，通过对具体问题的分析、设计和实现，培养实践能力。在设计问题、解决问题的过程中，既很好地培养了创造能力、抽象思维能力和逻辑思维能力，也能帮助学生更好地理解算法的思考过程，更主要的是能够将课程中所学到的知识灵活运用，做到举一反三，活学活用。

1 问题描述

任意输入扑克牌的张数n，程序按一定算法排序后，输出一列数字，使得这列数字经过下列操作后，得到一串由小到大排列的扑克牌数字。首先按照程序输出的数字序列将这些扑克牌从上往下排放。每次将这叠扑克牌最上面的一张移到最下面后，移出此时扑克牌最上面的—张；重复这个操作，直到这叠扑克牌全部移出时停止操作。

例如，当用户输入3时，程序输出213三个数，扑克牌从上往下依次是2、1、3：

1）将2移到扑克牌的末尾（3的后面），将1移出扑克牌队列，剩下：

2）将3移到扑克牌的末尾（2的后面），将2移出扑克牌队列，剩下：

3）最后将3移出。

可以看到，按照2、1、3的次序拍好后，依次将最上面的一张扑克牌放到最下面后，移出此时扑克牌最上面的—张扑克牌，三张扑克牌是按从小到大移出的。

问题是：当用户输入任意扑克牌的张数n时，如何得到正确的扑克牌序列，使得用户能够进行上述操作。在熟悉堆栈和队列的特点后，可以巧用堆栈和队列的方法来设计程序。

2 算法分析

此算法要用到堆栈和队列的基本实现和操作。栈和队列是两种重要的线性结构，它们是操作受限的线性表，称为限定性的数据结构。

栈是限定仅在表尾进行插入或删除操作的线性表，允许进行插入、删除操作的一端称为栈顶，固定端为栈底，它有两种存储表示方法：顺序表示和链式表示。栈的顺序存储结构（即顺序栈）是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，限定插入和删除操作只能在线性表的一端进行，又称为后进先出线性表。称插入操作为进栈，删除操作为出栈。栈的基本操作除了在栈顶进行插入或删除外，还有栈的初始化、判空操作、销毁操作、置空操作以及取栈顶元素等。

图1 程序运行结果

而队列与栈不同，它是一种先进先出的线性表，只允许在表的一端进行插入，而在另一端删除元素。允许删除的一端称为队首，允许插入的一端叫做队尾。称插入操作为入队，删除操作为出队。第一个出队的元素为队头元素，最后一个出队的元素为队尾元素。其基本操作与栈的操作类似，也有出队操作、入队操作、初始化、判空操作、销毁操作、置空操作、取队头元素等，不同的是，删除是在表的头部（即队头）进行。

在此程序中，输入数字个数n之后，为了让后面的扑克牌先处理，要用到堆栈操作，即让连续1～n张扑克牌全部入栈（此时栈元素个数为n，栈不为空），然后进入循环操作：依次让栈顶元素出栈，并让该元素入队列（栈长度依次减1，队列长度依次加1）；接着为实现扑克牌最上面一张移到最下面，需要进行队列头元素移动操作，让队列头元素移到队尾（进入队列的第一个元素不需要此操作）；当全部元素都进入队列并且完成队列操作之后，栈为空，无栈顶元素，循环结束。发现若按此时的输出数字序列操作，得到的是一串由大到小的数字排列，而不是由小到大，因此需要把这串队列数字逆序输出。根据堆栈先进后出的特点，要做到逆序输出，只需让队列数字全部入堆栈，再依次输出栈的元素即可。

分析此算法，用到的栈和队列的主要基本操作有：初始化栈和队列（InitStack(S); InitQueue(Q)）、元素入栈操作（Push(S,i)）、判空（StackEmpty(S);QueueEmpty(Q)）、出栈操作（Pop(S,e)）、元素入队列操作（EnQueue(Q,e)）、删除队列头元素（DeQueue(Q,e)）等。

3 程序设计

为增强程序的可读性和稳定性，将程序划分为若干个模块。头文件以及预定义常量放在c1.h中；顺序栈的定义放在c2.h中，栈的基本操作算法放在b1.cpp中；队列的定义放在c3.h中，队列的基本操作算法放在b2.cpp中。核心代码如下：

4 运行结果

运行程序，根据提示输入扑克牌的张数，输入13后回车，程序输出结果，根据此输出结果进行验证后可以得到从小到大依次排列的13个数，说明程序正确，结果如图1所示。

5 结语

刚开始学习数据结构的时候，虽然已经学过程序设计语言，但仅是初学，并不精通。对于抽象的数据类型、动态分配存储空间的概念，在理解上还是很困难的，知道算法也往往编写不出函数。只停留在看懂算法的水平上，而忽视将算法转换为具体程序设计语言中的函数以及编写出运行该函数的主程序。所以在上机实验中往往编写不出完整的程序，得出正确的结果。只有真正在解决问题，设计程序的过程中，才能提高语言编程能力，锻炼抽象思维能力。通过扑克牌程序，对数据结构有了更深入的理解，也体会到了数据结构的灵活性和趣味性，明白了只有勤于思考，多动手实践操作，才能有效提高编程能力，并养成良好的学习习惯，为后续课程的学习打好基础。

[1]严蔚敏,吴伟民.数据结构:C语言版[M].北京:清华大学出版社,2010.

[2]范策,等.算法与数据结构:C语言版[M].北京:机械工业出版社,2004.

[3]许卓群,等.数据结构与算法[M].北京:高等教育出版社,2005.

[4]谢楚屏,等.数据结构[M].北京:人民邮电出版社,2001.

[5]傅清祥,等.算法与数据结构[M].北京:电子工业出版社,1998.