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

棧和隊(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ī)票訂購(gòu)等。在停車場(chǎng)管理系統(tǒng)的應(yīng)用研究中，狹長(zhǎng)的停車通道符合棧的后進(jìn)先出、便道的管理符合隊(duì)列的先進(jìn)先出操作特性，基于此特性研究如何利用棧和隊(duì)列來(lái)模擬停車場(chǎng)管理的問題。

數(shù)據(jù)結(jié)構(gòu)；線性表；棧；隊(duì)列

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

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

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

三、任務(wù)分析

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

由于停車場(chǎng)只有一個(gè)大門，因此可以用一個(gè)棧來(lái)模擬。在便道停車的問題上，因?yàn)橄扰抨?duì)的車輛先離開便道進(jìn)入停車場(chǎng)，可以采用一個(gè)隊(duì)列來(lái)模擬。又因?yàn)樵撏＼噲?chǎng)是狹長(zhǎng)的停車場(chǎng)，停在中間的車輛是可以提前離開的，為了解決這個(gè)問題，我們還需要一個(gè)臨時(shí)地方（車輛規(guī)避所）保留為了讓路離開停車場(chǎng)的車輛，很顯然這個(gè)問題也需要用一個(gè)棧來(lái)實(shí)現(xiàn)，在程序中可以采用兩個(gè)順序棧s1和s2來(lái)表示停車場(chǎng)和車輛規(guī)避所，設(shè)置一個(gè)鏈隊(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á)時(shí)，判斷棧s1是否滿，若未滿就將車輛x進(jìn)棧s1,若棧已滿，就將車輛x入隊(duì)列q，表示車輛x在便道上等待進(jìn)入停車場(chǎng)。

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

2.信息查詢。

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

3.停車場(chǎng)車輛信息。

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

四、結(jié)束語(yǔ)

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

[1]韋斯.數(shù)據(jù)結(jié)構(gòu)與算法分析:Java語(yǔ)言描述(第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）