棧和隊列教學實例在數據結構中的應用研究

洪新華 洪新建 /湖南生物機電職業技術學院

棧和隊列教學實例在數據結構中的應用研究

洪新華 洪新建 /湖南生物機電職業技術學院

棧和隊列是一種特殊的線性結構，從數據結構的角度看它們是線性表，從操作的角度上看它們是操作受限制的線性表。在日常生活中棧和隊列也有廣泛的應用，如鐵路調度、民航機票訂購等。在停車場管理系統的應用研究中，狹長的停車通道符合棧的后進先出、便道的管理符合隊列的先進先出操作特性，基于此特性研究如何利用棧和隊列來模擬停車場管理的問題。

數據結構；線性表；棧；隊列

一、數據結構概述

數據結構課程是計算機相關專業學生必修的重要專業基礎課，同時也是專業基礎課中具有一定難度的課程。它的主要研究的內容就是數據在計算機中的邏輯結構、存儲結構以及設計相應的算法對數據進行各種操作。簡而言之就是數據結構=邏輯結構+存儲結構+算法，其中以算法為中心，算法的設計取決于數據的邏輯結構，算法的實現取決于數據的物理存儲結構。數據結構是軟件開發類課程的最重要的先修課程之一，學好數據結構是參加計算機各類考試的必備要求，是培養變成能力的必由之路，同時為計算機各門專業課程學習提供良好的基礎。數據結構的研究不僅涉及到計算機硬件的研究范圍，而且和計算機軟件的研究有著更密切的關系，無論是編譯程序還是操作系統，都涉及到數據元素在存儲器中的分配問題。數據結構中的邏輯結構研究主要有線性結構和非線性結構，線性結構中線性表是一種最常用的線性結構，其中棧和隊列是兩種典型的線性表。棧被廣泛應用于編譯軟件和程序設計中，而隊列在計算機操作系統和事務管理中得到廣泛的應用。

二、棧和隊列在模擬停車場管理中的應用

停車場管理系統一般都采用棧+隊列來模擬管理程序設計。假設停車場是一個可停放n輛汽車的狹長通道，且只有一個大門可供汽車進出。車輛按到達停車場時間的先后順序從停車場最里面向門口處停放（最先到達的第一輛車停在停車場最里面）。如果停車場已經停滿了n輛車，則后來的車輛只能在停車場大門外的便道上等待。如果停車場內有車要開走，則排在便道上的第一輛車就可以進入停車場。當某輛車要離開時，在他之后進入的車輛必須先退出停車場為它讓路，待其開出停車場后，其他車輛再按原次序進入停車場。停車場的管理是最先進去的車輛在最前面，符合棧的后進先出操作特性。在停車場內有空余車位的時候便道上的車輛按到達順序先行停放則符合隊列的特征。該問題便可以采用棧+隊列加以實現。

三、任務分析

（一）數據結構描述

由于停車場只有一個大門，因此可以用一個棧來模擬。在便道停車的問題上，因為先排隊的車輛先離開便道進入停車場，可以采用一個隊列來模擬。又因為該停車場是狹長的停車場，停在中間的車輛是可以提前離開的，為了解決這個問題，我們還需要一個臨時地方（車輛規避所）保留為了讓路離開停車場的車輛，很顯然這個問題也需要用一個棧來實現，在程序中可以采用兩個順序棧s1和s2來表示停車場和車輛規避所，設置一個鏈隊q表示便道，棧和隊列定義如下：

（二）系統主要功能設計與實現

1.車輛到達。

void Arrive(SqStack *s1,LQueue *q,ElemType x);

此函數用以表示當車輛x到達時，判斷棧s1是否滿，若未滿就將車輛x進棧s1,若棧已滿，就將車輛x入隊列q，表示車輛x在便道上等待進入停車場。

此函數用以表示當車輛x要離去時，就在棧s1中尋找此車牌號的車輛，如果找到則讓其離開停車場，且根據其停車時間收費，此車離開后將隊列q的隊頭元素進棧s1,如果沒找到，則在隊列q中去尋找此車牌號碼的車，如果找到，則允許離開隊列，但不收費，如找不到則顯示錯誤信息，在車輛離開停車場時，如果該車輛位于棧s1的中間位置時，需將此位置到棧頂之間的所有車輛退到棧s2，然后該車輛出棧，然后將棧s2中的車輛倒回棧s1。

2.信息查詢。

可以查詢車位空閑數目、車位停車情況等。如果車位未滿，提示便道上等待的車輛可以進入停車場；如果車位己滿，不允許車輛進入停車場，只能在便道上等待。

3.停車場車輛信息。

顯示停車場內每一停車位上是否有車，若有顯示該車的車牌號、到達時間。統計停車場內車輛數目以及空車位數目。先輸入到達車輛的車牌號，若停車場未滿，則車進停車場，輸入到達時間，記錄該車輛在停車場的位置。若停車場己滿，則車進便道，記錄該車在便道的位置。便道的管理是最先到達的車輛在最前面，一旦停車場有空位，最前面的車輛最先進入停車場，符合隊列的先進先出操作特性。可以用一個鏈隊來實現，此時只需要改變便道上車輛結點的連接方式，將模擬便道的鏈隊頭結點連到原來的第二輛車上就可以了。

四、結束語

棧和隊列是一種常見的數據結構模型，在日常工作生活中有很廣泛的應用，真正的把握好這兩個數據結構模型對于程序設計來說有很重要的現實意義。

[1]韋斯.數據結構與算法分析:Java語言描述(第2版)[M].機械出版社，2009（1）

[2]陳雁.數據結構[M].北京：高等教育出版社，2010(12)

[3]梅因.數據結構與面向對象程序設計(C++版) [M].北京：清華大學出版社,2012（5）