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

◆葉青

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ì)過(guò)程中會(huì)根據(jù)業(yè)務(wù)數(shù)據(jù)運(yùn)行的特點(diǎn)來(lái)選擇使用棧還是隊(duì)列。本文以停車(chē)管理業(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)度棧中的車(chē)輛要出去只能是后進(jìn)入的車(chē)輛先出棧。

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

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

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

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

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

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

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

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

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

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

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

1.2 車(chē)輛離開(kāi)業(yè)務(wù)分析：

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

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

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

（3）讓道車(chē)輛要回歸原車(chē)位。

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

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

棧和隊(duì)列都有兩種類(lèi)型，分別為順序棧/隊(duì)列，鏈?zhǔn)綏?隊(duì)列。順序棧和隊(duì)列擁有內(nèi)存連續(xù)的空間，但是使用時(shí)的大小是有限定的。而鏈?zhǔn)綏：完?duì)列是在內(nèi)存中開(kāi)辟的不連續(xù)的內(nèi)存空間來(lái)存儲(chǔ)數(shù)據(jù)，鏈?zhǔn)綏Ｗ畲笕萘坎皇芟拗?。停?chē)場(chǎng)的車(chē)位數(shù)和等候區(qū)的車(chē)位數(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ì)列的算法的控制。在論述過(guò)程中為了兼顧業(yè)務(wù)的完整性會(huì)涉及其他業(yè)務(wù)的代碼，比如計(jì)費(fèi)等。

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

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

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

typedef struct Car{

char plate[10]；

time_t timeIn；

time_t timeOunt；

}Car；

//停車(chē)位數(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//車(chē)位總個(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]）；//停車(chē)算法

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

void car_leave（char plate[10]）； //車(chē)輛離開(kāi)算法

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

3.3 停車(chē)算法

void car_come（char plate[10]）{

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

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

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

}

else{

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

//停車(chē)時(shí)間

time_t t_in；

t_in=time（&t_in）；

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

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

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

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

}

}

void stop_to_pave（char plate[10]）

{

if（p.count==MAXPAVE）{

printf（"車(chē)位已滿(mǎn)！ "）；

}

else{

time_t t_in；

t_in=time（&t_in）；

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

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

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

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

p.count++；

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

}

}

3.4 車(chē)輛離開(kāi)算法

void car_leave（char plate[10]）

{

char plate[10]；

int i=s.top；

if（s.top<0）{

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

}

else{

stop_to_buff（plate）；

}

}

//車(chē)輛讓道算法

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（"====開(kāi)始讓道==== "）；

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

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

}

}

//離開(kāi)車(chē)輛車(chē)牌不正確

if（s.top<0）{

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

}

else{

//第二步：車(chē)輛離開(kāi)

printf（"====車(chē)輛開(kāi)始離開(kāi)==== "）；

printf （"牌照為%s的汽車(chē)從停車(chē)場(chǎng)開(kāi)走 "， 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）；

//車(chē)輛離開(kāi)要計(jì)費(fèi)

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

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

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

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

if（s.top

{

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

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

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

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

p.front=p.front+1；

p.count--；

if（0==p.count）

{

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

}

}

}

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

while（b.top>-1）{

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

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

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

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

}

}

4 算法運(yùn)行

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

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

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

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

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

圖5 車(chē)輛離開(kāi)算法控制過(guò)程展示

5 結(jié)語(yǔ)

本文以停車(chē)管理業(yè)務(wù)為例子，使用結(jié)構(gòu)體數(shù)組和數(shù)據(jù)標(biāo)記法來(lái)管理和控制業(yè)務(wù)運(yùn)行過(guò)程中的棧和隊(duì)列的數(shù)據(jù)，利用棧和隊(duì)列的迎面增長(zhǎng)和最大值的設(shè)定方法滿(mǎn)足了業(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.