巧用堆棧與隊列解決撲克牌排序問題*

◆葉青 鄒軍華

作者：葉青、鄒軍華，湖北大學教育學院（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.