罗莉霞

摘要：队列是一种非常重要的线性结构，不仅在各类管理信息系统中应用极多，而且在日常生活中的很多场合都有所运用。循环队列尤其是《数据结构》课程中的重难点，为了帮助学生更好理解这个知识点，该文提出在循环队列的教学过程中引入医院的智能排队叫号系统作为案例，教师通过开展一系列讨论、分析、问答等师生互动的活动，最终让学生提出可行的解决方案，以此来加深学生对基本原理、概念的认识和理解。

关键词：案例教学法；排队叫号系统；循环队列

中图分类号：G64 文献标识码：A 文章编号：1009-3044（2018）01-0167-02

Abstract：The queue is an important linear structure. It is not only used in many management information systems， but also in many situations in our daily life. In particularly， circular-queue is the keystone in the data structure. In order to help students to understandit well， this paperintroduced the case of hospital intelligent calling and queuing systemswhile teaching， by guiding students to participate in the discussion， analysis， question and answer activities. After these interactive activities， the students were asked to come up with a feasible solution， thus deepening their understanding of the content.

Key words：case methodteaching；calling and queuing systems；circular-queue

案例教学是教师在教学过程中引入案例作为教学材料，结合教学主题，通过学生的调查、讨论、问答等师生互动的过程，来探讨解决问题的思路和方案，使得学生积极主动学习，从而培养学生更高层次能力的一种教学方法[1]。它是对传统意义上“老师讲、学生听”这种教学方法的突破，它要求教师以引导为主，将教学的中心由以教师为中心转换为以学生为中心，让学生真正成为学习的主角，从而激发学生的学习兴趣。

队列是《数据结构》课程中的重点，也是难点，它是一种非常重要的线性结构。随着服务行业业务种类和业务数量的急剧增长，队列的应用在生活中随处可见，例如医院的电子排队机系统、银行的叫号系统，以及工商、税务、电信大厅的业务排队系统等，这些基本上都是采用先来先服务的机制[2]。在循环队列的教学过程中，笔者注意到相当一部分学生对于“循环队列”的认知存在较大偏差，对于“循环队列算法”的理解存在困惑，为了帮助学生更好掌握循环队列这种结构体，本文结合了医院的智能排队叫号系统，深入分析和探讨循环队列的数据存储方式，以及主体算法的实现。本文所采用的教学思路亦可以运用到其他数据结构或者类似课程的教学中。

1 案例引入

为了贴合循环队列这个教学主题，案例的选择至关重要。首先看看生活中的例子，例如银行存取款，进入银行服务大厅，我们会在发号机上取一个号码，你的号码条上显示的内容是：“您的号码是098号，您前面有17个人在等待”，其中，“17”就是队列中排队的人数。毋庸置疑，本案例的数据存储采用循环队列的存储方式，算法需计算队列中排队元素的个数。这是队列的一般性应用方向：计算队列中排队元素的个数。具体实现方式可参照文献[2]给出的算法，算法如下：

算法一

int count（SqQueuesq）

{

（sq.rear+MaxSize-sq.front） % MaxSize；}

但是，队列除了一般性的应用之外，在医院和工商税务大厅的智能排队叫号系统都有更深层次的应用。我们具体以医院的智能排队叫号系统为例来进行分析，如果仔细观察过医院的就诊排队显示屏，就应该知道它显示的内容主要包括：目前就诊的患者姓名和排队编号，以及排队患者的姓名和排队编号，以及目前排队的人数。如果要实现这样的功能，我们需要从以下两个方面进行讨论和分析：

① 如何选用数据存储类型，队列的顺序存储方式还是链式存储方式呢？

② 需要添加哪些模块，才能满足该系统的功能要求？

2 案例分析

数据存储类型的选择，我们需要结合案例的实际情况，从数据的存储、选取和使用等方面对这两种存储方式进行比较[2]：

首先，从存储利用率来看，顺序存储方式下的存储密度为1，存储空间的利用率很高；但是链式队列的存储方式是不占优势的，因为它需要为每个数据元素附加一个指针用以存放下一个数据节点的地址，也就是逻辑关系，所以它的存储密度小于1。

其次，就存储的占用方式方面而言，和链式队列不一样，循环队列的存储空间是固定的，这就需要事先预估队列的长度，这个预估的长度太大會使存储空间无法被充分利用，长度太小又会造成“溢出”，使得入队操作不成功。就这一点来看，链式队列的动态分配空间机制为解决“溢出”提供了较好的解决思路。但是，就本案例而言，生活中需要用到这种排队机制的地方，例如银行、医院、工商税务大厅等场合，基本上每天的人流量是有限的，所以只要根据经验值来设定一个较大值MaxSize，分配一块连续的空间来存储数据，这在理论上和实践上都是可行的。endprint

第三，就存取方式而言，循环队列只需要根据数组元素的下标直接读取数据，而链式队列却需要从头至尾逐个访问读取，从查找效率上来看，链式队列的查找效率还是没有循环队列的效率高。

最后，从描述的工具上来分析，循环队列的操作和管理数据的工具是数组，这是很容易理解的，并且编写代码的难度不大。链式队列则采用指针对其进行管理和操作的，相对而言，指针的使用过程比较复杂，而且容易出错：例如指针传递过程中做了0值传递，造成地址丢失，那么很多数据就会丢失；又例如由于人为的失误在入队函数中写入死循环，会导致系统内存写满，从而造成灾难性的后果，这恰好是初学者容易犯错的地方。所以结合本案例的要求，对于仅需在队首（队尾）进行删除（插入）操作，以及经常执行查找操作的线性表，宜采用队列的顺序存储方式。

接下来，我们分析该功能需要实现哪些模块？

模块一，获取排队的号码。这个号码就是元素入队的序号，可以直接通过定义全局变量来实现，全局变量被初始化为0，元素每入队一次，全局变量就自加1一次。这是容易实现的。

模块二，读出队列中排队元素的值。我们需要设计出这个队列的遍历算法，读取出排队患者的姓名和排队编号。循环队列的基本算法中并没有提及如何顺序访问到每一个队列元素，这种算法如何实现呢？笔者给出了以下的可行方案。

设计循环队列遍历算法，我们首先回顾顺序队列是如何实现遍历算法的，如果要逐个访问如下图中顺序队列的元素值，我们可以通过算法二这个简单的循环实现：

算法二：

intDispQueue（SqQueuesq）

{if（sq.rear==sq.front）

{printf（"＼t＼t＼t＼a没有人在排队＼n＼n"）；

return 0； }

for（i=sq.front+1；i<=sq.rear；i++）

printf（“%c正在排队＼n”，sq.data[i]）；

return 1；}

仔细观察图1，上述的算法二似乎能够很完美地解决这个问题，但是这不是最优的。因为在顺序队列中有“假溢出”的情况产生，所以我们需要是将顺序队列的连续空间想象成首尾相连的环状空间，如果队首位置出现了空位，就可以将入队的元素存入空闲的存储空间，从而能够充分利用空间，避免不必要的空间浪费，循环队列能够很好地解决队列“假溢出”这种情况[3]。但是问题来了，能否像顺序队列一样通过直接访问数组成员data[i]，读取出相应的队列元素呢？答案是肯定的。

我们仍然可以定义一个循环控制变量i， 设定好i的初始值和终值，然后通过数组元素data[i]来逐个访问队列成员，如何设置i的初值和终值呢？首先我们分析循环队列的存储情况，基本上可以分为以下两种情况：①rear≥front，②rear

① rear≥front这种情况和顺序队列的实现方法类似，不在赘述；

② rear

4=（3+1）% MaxSize0=（4+1）% MaxSize1=（5+1）% MaxSize

我們将将算法二中i++改进为 i = （i + 1） % MaxSize， 综合上述分析，循环队列遍历算法如下：

算法三：

intCircDispQueue（SqQueuesq）

{if（sq.rear==sq.front）

{printf（"＼t＼t＼t＼a没有人在排队＼n＼n"）；

return 0； }

int i=sq.front+1；

while（i<=sq.rear）

{printf（“%c正在排队＼n”，sq.data[i]）；

i=（i+1）%MaxSize；}

return 1； }

3 结束语

本文就循环队列教学中如何采用案例教学法的组织和实施方法做了探讨，特别引入了实际生活中医院的智能排队叫号系统作为案例，并就这个系统的实现宜采用的数据存储方式，以及实现的主体功能模块等内容做了详细的分析和讨论。实践证明，在课堂上中采用本文阐述的案例教学法是一种行之有效的教学方法，通过对案例的分析和讨论，大部分学生都能积极主动思考，并参与到整个课堂教学的过程中来，从而理解并掌握了循环队列的存储方式和具体算法的实现过程。

案例教学法可以让学生结合教学主题的理论知识参与到案例的调查、分析、讨论等活动中来，进而提高他们分析问题和解决问题的能力，反过来还能加深他们对基本原理和概念的理解[4]。所有理论知识的学习和储备最终都是为了能够解决生活中的实际问题，这恰好又是大学生普遍存在的短板，这就要求教师在课堂教学中采用多种更为科学有效的教学方式，提高学生学习的效率[5]。

参考文献：

[1] 张家军，靳玉乐. 论案例教学的本质与特点[J].中国教育学刊，2004（1）：48-50.

[2] 殷人昆. 数据结构（C语言版）[M]. 北京：清华大学出版社，2012：54-55，74.

[3] 李春葆.数据结构简明教程[M].北京：清华大学出版社，2014（1）：87-92.

[4] 姜彦伟. 关于循环队列遍历算法的讨论及修正[J]. 工业仪表与自动化装置，2015（6）：86-89.

[5] 吴高臣，刘爽. 实践导向：案例教学法研究[J]. 黑龙江高教研究，2011（12）：178-181.