◆葉青

C語(yǔ)言中棧和隊(duì)列在業(yè)務(wù)中的運(yùn)用

◆葉青

（廣州商學(xué)院 廣東 511363）

棧和隊(duì)列在程序設(shè)計(jì)中經(jīng)常被程序員用來(lái)管理業(yè)務(wù)對(duì)象中一系列的數(shù)據(jù)，棧具有先進(jìn)后出的特點(diǎn)，隊(duì)列具有先進(jìn)先出的特點(diǎn)，在程序設(shè)計(jì)過程中會(huì)根據(jù)業(yè)務(wù)數(shù)據(jù)運(yùn)行的特點(diǎn)來(lái)選擇使用棧還是隊(duì)列。本文以停車管理業(yè)務(wù)為例來(lái)闡述棧和隊(duì)列在業(yè)務(wù)中的一種運(yùn)用方式。

棧；隊(duì)列；先進(jìn)先出；后進(jìn)先出

棧和隊(duì)列在程序設(shè)計(jì)中經(jīng)常被用來(lái)管理業(yè)務(wù)對(duì)象的一系列數(shù)據(jù)。棧具有先進(jìn)后出的特點(diǎn)，隊(duì)列具有先進(jìn)先出的特點(diǎn)。根據(jù)業(yè)務(wù)運(yùn)行數(shù)據(jù)管理的需要，程序員們會(huì)選擇合適的數(shù)據(jù)管理方式：比如下圖1鐵路調(diào)度所示，進(jìn)入鐵路調(diào)度棧中的車輛要出去只能是后進(jìn)入的車輛先出棧。

圖1 鐵路調(diào)度棧

如下圖2是排隊(duì)買票，只能是優(yōu)先進(jìn)排隊(duì)隊(duì)列的人員擁有優(yōu)先購(gòu)買票的權(quán)限。

圖2 排隊(duì)隊(duì)列

一個(gè)可以停放n 輛汽車的狹長(zhǎng)停車場(chǎng)，它只有一個(gè)大門可以供車輛進(jìn)出。車輛按到達(dá)停車場(chǎng)時(shí)間的先后次序依次從停車場(chǎng)最里面向大門口處停放（即最先到達(dá)的第一輛車停放在停車場(chǎng)的最里面）。如果停車場(chǎng)已放滿n 輛車，則以后到達(dá)的車輛只能在停車場(chǎng)大門外的等候區(qū)上等待，一旦停車場(chǎng)內(nèi)有車開走，則排在等候區(qū)上的第一輛車可以進(jìn)入停車場(chǎng)。停車場(chǎng)內(nèi)如有某輛車要開走，則在它之后進(jìn)入停車場(chǎng)的車都必須先退出停車場(chǎng)為它讓路，待其開出停車場(chǎng)后，這些車輛再依原來(lái)的次序進(jìn)場(chǎng)。每輛車在離開停車場(chǎng)時(shí)，都應(yīng)根據(jù)它在停車場(chǎng)內(nèi)停留的時(shí)間長(zhǎng)短交費(fèi)。

本文以此業(yè)務(wù)為例子來(lái)闡述C語(yǔ)言中棧和隊(duì)列的一種算法設(shè)計(jì)。

1 停車場(chǎng)業(yè)務(wù)分析

一般的停車場(chǎng)業(yè)務(wù)都會(huì)涉及：停車、車輛離開、收費(fèi)、查看車輛信息等功能，本文僅分析涉及棧和隊(duì)列的業(yè)務(wù)，即停車業(yè)務(wù)和車輛離開業(yè)務(wù)。

1.1 停車業(yè)務(wù)分析：

車輛進(jìn)停車場(chǎng)時(shí)如果有車位則車輛停入車位；如果沒有車位則車輛停入等候區(qū)；如果等候區(qū)中的位置已滿則提示不能進(jìn)入停車場(chǎng)。

車輛停入車位是按編號(hào)的順序依次?？?，車輛停放在狹長(zhǎng)通道，因?yàn)榭紤]車輛離開時(shí)后進(jìn)來(lái)的車輛要為當(dāng)前車輛讓道。此業(yè)務(wù)特點(diǎn)滿足先進(jìn)后出的特點(diǎn)，所以本文將把車位的數(shù)據(jù)設(shè)計(jì)成棧。

車輛進(jìn)入等候區(qū)，先進(jìn)等候區(qū)的車輛有優(yōu)先停車位的權(quán)限，滿足先進(jìn)先出的特點(diǎn)，所以本文將把等候區(qū)的車輛數(shù)據(jù)設(shè)計(jì)成隊(duì)列。

1.2 車輛離開業(yè)務(wù)分析：

車輛離開時(shí)要考慮三個(gè)業(yè)務(wù)流程的處理：

（1）車輛停放在狹長(zhǎng)通道，有車輛離開時(shí)其后面進(jìn)來(lái)的車輛要為其讓道。

（2）車輛離開后，如果等候區(qū)有車輛則先進(jìn)等候區(qū)的車輛優(yōu)先停入停車位。

（3）讓道車輛要回歸原車位。

提供停車場(chǎng)內(nèi)所有的車牌、車位、停車時(shí)長(zhǎng)和停車費(fèi)用等信息的查詢。

2 數(shù)據(jù)結(jié)構(gòu)分析

棧和隊(duì)列都有兩種類型，分別為順序棧/隊(duì)列，鏈?zhǔn)綏?隊(duì)列。順序棧和隊(duì)列擁有內(nèi)存連續(xù)的空間，但是使用時(shí)的大小是有限定的。而鏈?zhǔn)綏：完?duì)列是在內(nèi)存中開辟的不連續(xù)的內(nèi)存空間來(lái)存儲(chǔ)數(shù)據(jù)，鏈?zhǔn)綏Ｗ畲笕萘坎皇芟拗?。停車?chǎng)的車位數(shù)和等候區(qū)的車位數(shù)是固定的，本文將使用順序棧的方式來(lái)存儲(chǔ)和管理數(shù)據(jù)。

3 算法設(shè)計(jì)

下面將向大家論述在C語(yǔ)言中棧和隊(duì)列的一種算法設(shè)計(jì)。該設(shè)計(jì)的特點(diǎn)是使用結(jié)構(gòu)體數(shù)組和數(shù)據(jù)標(biāo)記法來(lái)進(jìn)行棧和隊(duì)列的算法的控制。在論述過程中為了兼顧業(yè)務(wù)的完整性會(huì)涉及其他業(yè)務(wù)的代碼，比如計(jì)費(fèi)等。

3.1 數(shù)據(jù)結(jié)構(gòu)定義

使用C語(yǔ)言定義業(yè)務(wù)數(shù)據(jù)如下：

//車輛數(shù)據(jù)

typedef struct Car{

char plate[10]；

time_t timeIn；

time_t timeOunt；

}Car；

//停車位數(shù)據(jù)—棧

typedef struct Stop{

Car stop[MAXSTOP]；

int top； //棧頂標(biāo)記

}Stop；

//等候區(qū)數(shù)據(jù)—隊(duì)列

typedef struct Pave{

Car pave[MAXPAVE]；

int front；//隊(duì)列頭標(biāo)記

int rear；//隊(duì)列尾標(biāo)記

int count；

}Pave；

//讓道區(qū)數(shù)據(jù)—棧

typedef struct Buffer{

Car buffer[MAXSTOP]；

int top；//棧頂標(biāo)記

}Buffer；

3.2 數(shù)據(jù)和功能定義

#define MAXSTOP n//車位總個(gè)數(shù)

#define MAXPAVE m//等候區(qū)總個(gè)數(shù)

#define price x//單價(jià)

Car c；

Stop s；

Pave p；

Buffer b；

void car_come（char plate[10]）；//停車算法

void stop_to_pave（char plate[10]）；//停入等候區(qū)算法

void car_leave（char plate[10]）； //車輛離開算法

void stop_to_buff（char plate[10]）；//車輛讓道算法

3.3 停車算法

void car_come（char plate[10]）{

//判斷有無(wú)車位

if（s.top>=MAXSTOP-1）{

stop_to_pave（）；//停入等候區(qū)

}

else{

s.top++；//棧頂向上移位

//停車時(shí)間

time_t t_in；

t_in=time（&t_in）；

s.stop[s.top].timeIn=t_in；

//車輛信息進(jìn)停車棧

strcpy（s.stop[s.top].plate， plate）；

printf（"牌號(hào)為%s的車進(jìn)入%d的車位，停車時(shí)間為：%s "， plate，s.top+1，ctime（&t_in））；

}

}

void stop_to_pave（char plate[10]）

{

if（p.count==MAXPAVE）{

printf（"車位已滿！ "）；

}

else{

time_t t_in；

t_in=time（&t_in）；

p.pave[p.rear].timeIn=t_in；

//車輛信息進(jìn)等候區(qū)隊(duì)列中

strcpy（p.pave[p.rear].plate， plate）；

p.rear++；//隊(duì)列尾部后移

p.count++；

printf（"牌照為%s的車停入%d等候區(qū)！，時(shí)間為：%s "， plate，p.rear，ctime（&t_in））；

}

}

3.4 車輛離開算法

void car_leave（char plate[10]）

{

char plate[10]；

int i=s.top；

if（s.top<0）{

printf （"無(wú)車輛信息！ "）；

}

else{

stop_to_buff（plate）；

}

}

//車輛讓道算法

void stop_to_buff（char plate[10]）

{

while（s.top>-1）{

//第一步：讓道

if（0==strcmp（s.stop[s.top].plate，plate）{

break；

}

else{

b.top++；//讓道區(qū)棧頂向上移

strcpy（b.buffer[b.top].plate，s.stop[s.top].plate）；

printf（"====開始讓道==== "）；

printf（"%s車輛讓道 "，s.stop[s.top].plate）；

s.top--； //停車區(qū)棧頂向下移

}

}

//離開車輛車牌不正確

if（s.top<0）{

printf（"無(wú)此車輛信息！ "）；

}

else{

//第二步：車輛離開

printf（"====車輛開始離開==== "）；

printf （"牌照為%s的汽車從停車場(chǎng)開走 "， s.stop[s.top].plate）；

time_t t_out；

t_out=time（&t_out）；

int diff=difftime（t_out，s.stop[s.top].timeIn）；

float charge=change（diff）；

//車輛離開要計(jì)費(fèi)

printf（"停車費(fèi)用共：%.1f（元） "，charge）；

printf（"============= "）；

s.top--；//棧頂向下移

//第三步：等候區(qū)車輛進(jìn)入車位

if（s.top

{

s.top++；//棧頂向上移

strcpy（s.stop[s.top].plate，p.pave[p.front].plate）；

printf（"%s等候區(qū)車輛停入車位 "，p.pave[p.front].plate）；

printf（"=========== "）；

p.front=p.front+1；

p.count--；

if（0==p.count）

{

p.front=p.rear=0；//隊(duì)列空

}

}

}

//第四步：臨時(shí)棧中的車輛回歸車位

while（b.top>-1）{

s.top++；//棧頂向上移

strcpy（s.stop[s.top].plate，b.buffer[b.top].plate）；

printf（"%s讓道車輛回歸車位 "，b.buffer[b.top]）；

b.top--；//棧頂向下移

}

}

4 算法運(yùn)行

為了展示算法的控制過程，接下來(lái)將以圖形界面的形式進(jìn)行呈現(xiàn)。以停車場(chǎng)停車位為3個(gè)，等候區(qū)為3個(gè)共6個(gè)位置來(lái)進(jìn)行算法控制過程展示。

車輛進(jìn)入停車場(chǎng)是進(jìn)入棧的算法控制過程，棧滿后則車位已滿，再來(lái)車輛只能進(jìn)入等候區(qū)位置，圖3為車輛進(jìn)入等候區(qū)圖。

車輛離開涉及車輛讓道和讓道車輛回歸，以及便道區(qū)車輛停靠車位等算法的控制。車輛讓道涉及數(shù)據(jù)的出棧，車輛回歸車位涉及數(shù)據(jù)的入棧，便道區(qū)車輛停入車位涉及隊(duì)列數(shù)據(jù)的出列和該數(shù)據(jù)的入棧。算法控制過程見圖5車輛離開算法控制過程展示。

查看停車位上的車輛信息可以看到后進(jìn)來(lái)的車輛在所有信息的頭部，見圖4停車位上的車輛信息顯示，說(shuō)明車輛進(jìn)入停車場(chǎng)的業(yè)務(wù)數(shù)據(jù)的控制和管理是棧的方式。

圖4 停車場(chǎng)車輛信息顯示

圖5 車輛離開算法控制過程展示

5 結(jié)語(yǔ)

本文以停車管理業(yè)務(wù)為例子，使用結(jié)構(gòu)體數(shù)組和數(shù)據(jù)標(biāo)記法來(lái)管理和控制業(yè)務(wù)運(yùn)行過程中的棧和隊(duì)列的數(shù)據(jù)，利用棧和隊(duì)列的迎面增長(zhǎng)和最大值的設(shè)定方法滿足了業(yè)務(wù)使用的需要，同時(shí)有效控制了棧頂和隊(duì)列溢出的異常。

本文僅向大家提供了一種C語(yǔ)言中棧和隊(duì)列的一種在業(yè)務(wù)中的運(yùn)用方法，本文中棧和隊(duì)列的算法具有輕便簡(jiǎn)單等相關(guān)特點(diǎn)。有關(guān)本文之外的其他技術(shù)將不在本文討論的范疇。

[1]陳竹云，葉雯. 數(shù)據(jù)結(jié)構(gòu)中隊(duì)列的應(yīng)用研究[J].電腦知識(shí)與技術(shù)，2017，13（03）：5-7.

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

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

[4]譚浩強(qiáng).C語(yǔ)言程序設(shè)計(jì)[M].北京：清華大學(xué)出版社，2012.

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

[6]沈華，楊曉艷，馬馳，等.數(shù)據(jù)結(jié)構(gòu)及應(yīng)用：C語(yǔ)言描述[M].北京：機(jī)械工業(yè)出版社，2011.