案例教學法在循環隊列教學中的探究

羅莉霞

摘要：隊列是一種非常重要的線性結構，不僅在各類管理信息系統中應用極多，而且在日常生活中的很多場合都有所運用。循環隊列尤其是《數據結構》課程中的重難點，為了幫助學生更好理解這個知識點，該文提出在循環隊列的教學過程中引入醫院的智能排隊叫號系統作為案例，教師通過開展一系列討論、分析、問答等師生互動的活動，最終讓學生提出可行的解決方案，以此來加深學生對基本原理、概念的認識和理解。

關鍵詞：案例教學法；排隊叫號系統；循環隊列

中圖分類號：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.