陳竹云++葉雯

摘要：隊(duì)列是一種特殊的線性表，是計(jì)算機(jī)科學(xué)中非常重要的、有用的數(shù)據(jù)結(jié)構(gòu)，在計(jì)算機(jī)操作系統(tǒng)和事務(wù)管理中得到廣泛的應(yīng)用。在對(duì)停車場(chǎng)管理系統(tǒng)的研究中，便道的管理符合隊(duì)列的先進(jìn)先出操作特性，基于此特性研究了如何利用隊(duì)列來(lái)模擬管理的方法。

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

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2017）03-0005-03

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

數(shù)據(jù)結(jié)構(gòu)被稱為計(jì)算機(jī)科學(xué)的兩大支柱之一，因此數(shù)據(jù)結(jié)構(gòu)課程被列為計(jì)算機(jī)專業(yè)的一門專業(yè)基礎(chǔ)必修課程。我們研究數(shù)據(jù)結(jié)構(gòu)的目的是為了學(xué)會(huì)如何更好地編寫出效率更高的程序。

數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作等等的學(xué)科。數(shù)據(jù)結(jié)構(gòu)的研究不僅涉及計(jì)算機(jī)硬件的研究范圍，而且和計(jì)算機(jī)軟件的研究有著更密切的關(guān)系，無(wú)論是編譯程序還是操作系統(tǒng)，都涉及數(shù)據(jù)元素在存儲(chǔ)器中的分配問題。

數(shù)據(jù)的邏輯結(jié)構(gòu)分為集合、線性、樹形和圖形4種結(jié)構(gòu)。線性表是最簡(jiǎn)單、最常用的一種數(shù)據(jù)結(jié)構(gòu)，棧和隊(duì)列是兩種特殊的線性表，是計(jì)算機(jī)科學(xué)中非常重要的、有用的數(shù)據(jù)結(jié)構(gòu)。棧被廣泛應(yīng)用于編譯軟件和程序設(shè)計(jì)中，而隊(duì)列在計(jì)算機(jī)操作系統(tǒng)和事務(wù)管理中得到廣泛的應(yīng)用。

2 隊(duì)列的基本知識(shí)

隊(duì)列是一種特殊的線性表，特殊之處在于，它只允許在表的前端（front）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作，和棧一樣，隊(duì)列是一種操作受限制的線性表。允許插入操作的一端稱為隊(duì)尾，允許刪除操作的一端稱為隊(duì)頭。隊(duì)列中沒有元素時(shí)，稱為空隊(duì)列。

隊(duì)列的數(shù)據(jù)元素又稱為隊(duì)列元素。在隊(duì)列中插入一個(gè)隊(duì)列元素稱為入隊(duì)，從隊(duì)列中刪除一個(gè)隊(duì)列元素成為出隊(duì)。因?yàn)殛?duì)列只允許在一段插入，在另一端刪除，所以只有最早進(jìn)入隊(duì)列的元素才能最先從隊(duì)列中刪除，故隊(duì)列又稱為先進(jìn)先出（FIFO—first in first out）線性表。

3 隊(duì)列在停車場(chǎng)管理中的應(yīng)用

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)中的停車場(chǎng)管理系統(tǒng)一般都采用棧+隊(duì)列來(lái)模擬管理程序。

假設(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)停車場(chǎng)內(nèi)某輛車要離開時(shí)，在它之后進(jìn)入的車輛必須先退出停車場(chǎng)為它讓路，待該輛車開出大門外，其他車輛再按原次序進(jìn)入停車場(chǎng)。每輛停放在停車場(chǎng)的車，在它離開停車場(chǎng)時(shí)，必須按它停留的時(shí)間長(zhǎng)短交納費(fèi)用，在便道上停車不收費(fèi)。

停車場(chǎng)的管理是最先進(jìn)去的車輛在最前面，符合棧的后進(jìn)先出操作特性。但是，實(shí)際的停車場(chǎng)并不一定是狹長(zhǎng)的通道，若某車輛到達(dá)，只要有空閑車位就可以停車，不一定先到的停在最里面，后到的停在最外面；若某輛車離開，只需按它停留的時(shí)間長(zhǎng)短交納費(fèi)用，便可以離開，不必讓它之后進(jìn)入的車輛為它讓路。所以，我認(rèn)為采用有序鏈表+隊(duì)列來(lái)模擬停車場(chǎng)管理更符合實(shí)際情況。

3.1系統(tǒng)結(jié)構(gòu)分析

該問題包含兩方面的信息。一方面是車輛的信息，可包含車牌號(hào)、汽車種類等；另一方面是停車記錄信息，可包含車牌號(hào)、停車位置、到達(dá)時(shí)間、離開時(shí)間等。兩方面信息通過車牌號(hào)關(guān)聯(lián)起來(lái)。使用順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)或樹形存儲(chǔ)結(jié)構(gòu)都可以存儲(chǔ)這些信息，但其中各有利弊。

順序存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)簡(jiǎn)單，但容量固定，插入和刪除需要進(jìn)行記錄的移動(dòng)。停車記錄信息存儲(chǔ)不易連續(xù)，導(dǎo)致列舉時(shí)需要對(duì)全部停車記錄進(jìn)行完整遍歷。對(duì)已排序順序表查找某一記錄時(shí)，可以采用特定算法（如二分法）提高效率，總體上說(shuō)實(shí)用性和整體效率相對(duì)較差。

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)設(shè)計(jì)略復(fù)雜，容量不設(shè)上限，插入和刪除較方便，采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的停車記錄形式上連續(xù)，列舉時(shí)很方便，但在查找某一記錄時(shí)需要遍歷整個(gè)鏈表效率較低，總體上說(shuō)實(shí)用性和整體效率中上。

樹形存儲(chǔ)結(jié)構(gòu)相對(duì)最復(fù)雜，容量也不設(shè)上限，插入和刪除算法也相對(duì)復(fù)雜，采用特殊樹形結(jié)構(gòu)（如二叉排序樹）能夠提高查找記錄時(shí)的效率，停車記錄仍可以采用鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)，總體來(lái)說(shuō)實(shí)用性和整體效率較好，現(xiàn)實(shí)中的數(shù)據(jù)庫(kù)管理系統(tǒng)多是用樹形結(jié)構(gòu)來(lái)實(shí)現(xiàn)的。

從實(shí)現(xiàn)難度上來(lái)說(shuō)，順序存儲(chǔ)最簡(jiǎn)單，鏈?zhǔn)酱鎯?chǔ)次之，樹形存儲(chǔ)最難。因此，對(duì)學(xué)生而言，一般要求采用鏈?zhǔn)酱鎯?chǔ)來(lái)實(shí)現(xiàn)。

車輛信息和停車記錄信息之間是通過車牌號(hào)來(lái)關(guān)聯(lián)的，在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中可以用指針來(lái)表示兩者的關(guān)聯(lián)。每輛車的數(shù)據(jù)域可包含車牌號(hào)、汽車種類等，兩個(gè)指針域，一個(gè)指針指向下一個(gè)停車位置節(jié)點(diǎn)，另一個(gè)指針指向該車輛的停車記錄鏈表，該節(jié)點(diǎn)的數(shù)據(jù)域可包含離開時(shí)間、到達(dá)時(shí)間等。

從功能上分析，車輛到達(dá)、車輛離開就是在停車記錄鏈表中進(jìn)行插入和刪除操作；信息查詢就是遍歷停車記錄鏈表，顯示該車輛對(duì)應(yīng)的停車記錄。

3.2 系統(tǒng)設(shè)計(jì)及實(shí)現(xiàn)

3.2.1 車輛到達(dá)

先輸入到達(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)的第二輛車上就可以了。

3.2.2 車輛離開

當(dāng)車庫(kù)為空時(shí)，提示沒有車，結(jié)束；否則車輛離開。離開時(shí)，首先輸入離開車輛的車牌號(hào)以及離開時(shí)間，計(jì)算其停放時(shí)間并收取相應(yīng)的停車費(fèi)用，然后記錄要離開車輛在停車場(chǎng)的位置，該位置置空。之后，再檢查便道上是否有車等候，如果便道上有等待的車輛，讓便道上的第一輛車進(jìn)入停車場(chǎng)，接著輸入要進(jìn)去停車場(chǎng)的車輛信息，以現(xiàn)在的時(shí)間作為車輛到達(dá)的時(shí)間。便道隊(duì)列的頭結(jié)點(diǎn)指向剛進(jìn)入停車場(chǎng)的車輛結(jié)點(diǎn)的后繼結(jié)點(diǎn)，即原隊(duì)列中第二輛車的結(jié)點(diǎn)。

3.2.3 信息查詢

可以查詢車位空閑數(shù)目、車位停車情況等。如果車位未滿，提示便道上等待的車輛可以進(jìn)入停車場(chǎng)，進(jìn)入停車場(chǎng)時(shí)需要輸入車輛的各種信息；如果車位已滿，系統(tǒng)會(huì)輸出排隊(duì)信息，不允許車輛進(jìn)入停車場(chǎng)，只能在便道上等待，但是仍然需要信息登記才可以進(jìn)入便道。

3.2.3.1 停車場(chǎng)車輛信息

顯示停車場(chǎng)內(nèi)每一停車位上是否有車，若有，則顯示該車的車牌號(hào)、到達(dá)時(shí)間等信息。統(tǒng)計(jì)停車場(chǎng)內(nèi)車輛數(shù)目以及空車位數(shù)目。

3.2.3.2 便道車輛信息

顯示便道上等待車輛的車牌號(hào)以及位置號(hào)，統(tǒng)計(jì)便道上等待車輛數(shù)目。

3.3模擬狀態(tài)變化圖

假設(shè)停車場(chǎng)最多能停放車輛：MAX=2。按照從終端讀入數(shù)據(jù)的序列進(jìn)行模擬管理，汽車的模擬輸入信息格式可設(shè)定為（到達(dá)/離開，車牌號(hào)，到達(dá)/離開的時(shí)刻）。例如，（A，3，10）表示3號(hào)牌照車在10點(diǎn)到達(dá)，而（L，8，17）表示8號(hào)牌照車在17點(diǎn)離開。便道上車輛信息可表示為（位置號(hào)，車牌號(hào)，指針），停車場(chǎng)內(nèi)車輛信息可表示為（車牌號(hào)，到達(dá)時(shí)間，指針），停車記錄信息可表示為（車位號(hào)，指向下一車位節(jié)點(diǎn)的指針，指向停車場(chǎng)內(nèi)車輛信息的指針）。當(dāng)輸入數(shù)據(jù)項(xiàng)為（E， 0， 0），程序會(huì)跳出循環(huán)，同時(shí)程序結(jié)束。模擬程序從第一輛車到達(dá)開始運(yùn)行。

初始狀態(tài)如圖所示：

說(shuō)明：先后到達(dá)了四輛車，因?yàn)橥＼噲?chǎng)最多只能停放兩輛車，所以最先到達(dá)的兩輛車依次停放在車位號(hào)為1和2的位置上，記錄下他們的車牌號(hào)和到達(dá)時(shí)間。由于中間沒有離開的車輛，所以后到達(dá)的兩輛車只能依次停放在便道上。因?yàn)橥７旁诒愕郎系能囕v是不需要收費(fèi)的，所以不需要記錄他們的到達(dá)時(shí)間，只需要記錄他們的車牌號(hào)就行了。

說(shuō)明：由于3號(hào)牌照車先離開了，所以1號(hào)停車位為空。原來(lái)便道上等待的第一輛車15號(hào)牌照車進(jìn)入停車場(chǎng)1號(hào)停車位，第二輛車2號(hào)牌照車成為現(xiàn)在便道上的第一輛車。因?yàn)橥＼嚂r(shí)間是從進(jìn)入停車場(chǎng)開始計(jì)算的，所以此刻的時(shí)間為15號(hào)牌照車的到達(dá)時(shí)間。在14點(diǎn)的時(shí)候又來(lái)了一輛20號(hào)牌照車，因?yàn)榇藭r(shí)停車場(chǎng)為滿，便道上已有一輛車，所以20號(hào)牌照車只能依次排在便道上第二輛車的位置等待。

3.4系統(tǒng)相關(guān)問題說(shuō)明

對(duì)于進(jìn)出停車場(chǎng)的時(shí)間，簡(jiǎn)化了操作，只輸入當(dāng)時(shí)的時(shí)刻，沒有具體到小時(shí)和分鐘。對(duì)于停車費(fèi)率的設(shè)定，可以根據(jù)不同的汽車種類分別設(shè)定停車費(fèi)率，如小汽車每小時(shí)收費(fèi)5元，客車每小時(shí)收費(fèi)8元，卡車每小時(shí)收費(fèi)10元。系統(tǒng)根據(jù)不同種類的車輛計(jì)算出停車費(fèi)用。當(dāng)用戶輸入的車牌號(hào)不在停車場(chǎng)時(shí)，系統(tǒng)會(huì)提示輸入錯(cuò)誤，請(qǐng)重新輸入。

對(duì)程序進(jìn)行操作運(yùn)行時(shí)，可以采用菜單的方式進(jìn)行。設(shè)置歡迎界面、主界面、幫助界面、退出界面、停車場(chǎng)管理主菜單和信息查詢子菜單等。使用菜單時(shí)，可以利用清屏：system（“cls”）；暫停：system（“pause”）等命令。

4 結(jié)束語(yǔ)

從保存信息角度來(lái)看，定義隊(duì)列數(shù)據(jù)結(jié)構(gòu)是為了保存遍歷所經(jīng)過的路徑，亦即保存遍歷過程中的每一個(gè)結(jié)點(diǎn)的信息，而不僅僅只是終結(jié)點(diǎn)的信息。而之所以要用隊(duì)列保存每個(gè)遍歷節(jié)點(diǎn)信息，是因?yàn)樵诖_定下一次的遍歷節(jié)點(diǎn)時(shí)，可能需要利用已經(jīng)遍歷過的節(jié)點(diǎn)的信息。從次序角度來(lái)看，定義隊(duì)列是為了對(duì)序列實(shí)行一種順序操作。

在日常生活中，我們經(jīng)常會(huì)遇到許多為了維護(hù)社會(huì)正常秩序而需要排隊(duì)的情境。在現(xiàn)實(shí)生活中，隊(duì)列的應(yīng)用也很廣泛，特別是在計(jì)算機(jī)科學(xué)領(lǐng)域中所起的作用很大。比如我們播放器上的播放列表，我們的數(shù)據(jù)流對(duì)象，異步的數(shù)據(jù)傳輸結(jié)構(gòu)（文件IO、管道通訊、套接字等）。還有一些解決對(duì)共享資源的沖突訪問，比如打印機(jī)的打印隊(duì)列，消息隊(duì)列，交通狀況模擬，呼叫中心用戶等待時(shí)間的模擬等等。另外在解決主機(jī)與外部設(shè)備之間速度不匹配問題，解決多用戶引起的資源競(jìng)爭(zhēng)問題等都運(yùn)用了隊(duì)列這樣的數(shù)據(jù)結(jié)構(gòu)算法。

參考文獻(xiàn)：

[1] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）[M].北京：清華大學(xué)出版社，2012.

[2] 朱戰(zhàn)立.數(shù)據(jù)結(jié)構(gòu)——使用C語(yǔ)言[M].北京：電子工業(yè)出版社，2014.

[3] 沈華，文志誠(chéng)，楊曉艷，張明武.數(shù)據(jù)結(jié)構(gòu)與算法：C語(yǔ)言描述[M].北京：機(jī)械工業(yè)出版社，2015.

[4] 耿國(guó)華，張德同，周明全，等.數(shù)據(jù)結(jié)構(gòu)——用C語(yǔ)言描述[M].北京：高等教育出版社，2015.

[5] 沈華.數(shù)據(jù)結(jié)構(gòu)課程中棧和隊(duì)列實(shí)驗(yàn)教學(xué)方案設(shè)計(jì)[J].教育教學(xué)論壇，2016（6）.