棧和隊(duì)列教學(xué)實(shí)例在數(shù)據(jù)結(jié)構(gòu)中的應(yīng)用研究

洪新華+洪新建

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

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

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

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

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

二、棧和隊(duì)列在模擬停車場管理中的應(yīng)用

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

三、任務(wù)分析

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

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

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

1.車輛到達(dá)。

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

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

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

2.信息查詢。

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

3.停車場車輛信息。

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

四、結(jié)束語

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

參考文獻(xiàn)：

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

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

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