洪新華+洪新建

湖南生物機電職業(yè)技術(shù)學院

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

【關(guān)鍵詞】數(shù)據(jù)結(jié)構(gòu)；線性表；棧；隊列

一、數(shù)據(jù)結(jié)構(gòu)概述

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

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

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

三、任務分析

（一）數(shù)據(jù)結(jié)構(gòu)描述

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

（二）系統(tǒng)主要功能設計與實現(xiàn)

1.車輛到達。

void Arrive（SqStack *s1，LQueue *q，ElemType x）；

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

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

2.信息查詢。

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

3.停車場車輛信息。

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

四、結(jié)束語

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

參考文獻：

[1]韋斯.數(shù)據(jù)結(jié)構(gòu)與算法分析：Java語言描述（第2版）[M].機械出版社，2009（1）

[2]陳雁.數(shù)據(jù)結(jié)構(gòu)[M].北京：高等教育出版社，2010（12）

[3]梅因.數(shù)據(jù)結(jié)構(gòu)與面向?qū)ο蟪绦蛟O計（C++版） [M].北京：清華大學出版社，2012（5）