C語言中棧和隊列在業務中的運用

◆葉青

C語言中棧和隊列在業務中的運用

◆葉青

（廣州商學院 廣東 511363）

棧和隊列在程序設計中經常被程序員用來管理業務對象中一系列的數據，棧具有先進后出的特點，隊列具有先進先出的特點，在程序設計過程中會根據業務數據運行的特點來選擇使用棧還是隊列。本文以停車管理業務為例來闡述棧和隊列在業務中的一種運用方式。

棧；隊列；先進先出；后進先出

棧和隊列在程序設計中經常被用來管理業務對象的一系列數據。棧具有先進后出的特點，隊列具有先進先出的特點。根據業務運行數據管理的需要，程序員們會選擇合適的數據管理方式：比如下圖1鐵路調度所示，進入鐵路調度棧中的車輛要出去只能是后進入的車輛先出棧。

圖1 鐵路調度棧

如下圖2是排隊買票，只能是優先進排隊隊列的人員擁有優先購買票的權限。

圖2 排隊隊列

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

本文以此業務為例子來闡述C語言中棧和隊列的一種算法設計。

1 停車場業務分析

一般的停車場業務都會涉及：停車、車輛離開、收費、查看車輛信息等功能，本文僅分析涉及棧和隊列的業務，即停車業務和車輛離開業務。

1.1 停車業務分析：

車輛進停車場時如果有車位則車輛停入車位；如果沒有車位則車輛停入等候區；如果等候區中的位置已滿則提示不能進入停車場。

車輛停入車位是按編號的順序依次停靠，車輛停放在狹長通道，因為考慮車輛離開時后進來的車輛要為當前車輛讓道。此業務特點滿足先進后出的特點，所以本文將把車位的數據設計成棧。

車輛進入等候區，先進等候區的車輛有優先停車位的權限，滿足先進先出的特點，所以本文將把等候區的車輛數據設計成隊列。

1.2 車輛離開業務分析：

車輛離開時要考慮三個業務流程的處理：

（1）車輛停放在狹長通道，有車輛離開時其后面進來的車輛要為其讓道。

（2）車輛離開后，如果等候區有車輛則先進等候區的車輛優先停入停車位。

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

提供停車場內所有的車牌、車位、停車時長和停車費用等信息的查詢。

2 數據結構分析

棧和隊列都有兩種類型，分別為順序棧/隊列，鏈式棧/隊列。順序棧和隊列擁有內存連續的空間，但是使用時的大小是有限定的。而鏈式棧和隊列是在內存中開辟的不連續的內存空間來存儲數據，鏈式棧最大容量不受限制。停車場的車位數和等候區的車位數是固定的，本文將使用順序棧的方式來存儲和管理數據。

3 算法設計

下面將向大家論述在C語言中棧和隊列的一種算法設計。該設計的特點是使用結構體數組和數據標記法來進行棧和隊列的算法的控制。在論述過程中為了兼顧業務的完整性會涉及其他業務的代碼，比如計費等。

3.1 數據結構定義

使用C語言定義業務數據如下：

//車輛數據

typedef struct Car{

char plate[10]；

time_t timeIn；

time_t timeOunt；

}Car；

//停車位數據—棧

typedef struct Stop{

Car stop[MAXSTOP]；

int top； //棧頂標記

}Stop；

//等候區數據—隊列

typedef struct Pave{

Car pave[MAXPAVE]；

int front；//隊列頭標記

int rear；//隊列尾標記

int count；

}Pave；

//讓道區數據—棧

typedef struct Buffer{

Car buffer[MAXSTOP]；

int top；//棧頂標記

}Buffer；

3.2 數據和功能定義

#define MAXSTOP n//車位總個數

#define MAXPAVE m//等候區總個數

#define price x//單價

Car c；

Stop s；

Pave p；

Buffer b；

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

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

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

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

3.3 停車算法

void car_come（char plate[10]）{

//判斷有無車位

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

stop_to_pave（）；//停入等候區

}

else{

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

//停車時間

time_t t_in；

t_in=time（&t_in）；

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

//車輛信息進停車棧

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

printf（"牌號為%s的車進入%d的車位，停車時間為：%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；

//車輛信息進等候區隊列中

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

p.rear++；//隊列尾部后移

p.count++；

printf（"牌照為%s的車停入%d等候區！，時間為：%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 （"無車輛信息！ "）；

}

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++；//讓道區棧頂向上移

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

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

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

s.top--； //停車區棧頂向下移

}

}

//離開車輛車牌不正確

if（s.top<0）{

printf（"無此車輛信息！ "）；

}

else{

//第二步：車輛離開

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

printf （"牌照為%s的汽車從停車場開走 "， 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）；

//車輛離開要計費

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

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

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

//第三步：等候區車輛進入車位

if（s.top

{

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

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

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

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

p.front=p.front+1；

p.count--；

if（0==p.count）

{

p.front=p.rear=0；//隊列空

}

}

}

//第四步：臨時棧中的車輛回歸車位

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 算法運行

為了展示算法的控制過程，接下來將以圖形界面的形式進行呈現。以停車場停車位為3個，等候區為3個共6個位置來進行算法控制過程展示。

車輛進入停車場是進入棧的算法控制過程，棧滿后則車位已滿，再來車輛只能進入等候區位置，圖3為車輛進入等候區圖。

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

查看停車位上的車輛信息可以看到后進來的車輛在所有信息的頭部，見圖4停車位上的車輛信息顯示，說明車輛進入停車場的業務數據的控制和管理是棧的方式。

圖4 停車場車輛信息顯示

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

5 結語

本文以停車管理業務為例子，使用結構體數組和數據標記法來管理和控制業務運行過程中的棧和隊列的數據，利用棧和隊列的迎面增長和最大值的設定方法滿足了業務使用的需要，同時有效控制了棧頂和隊列溢出的異常。

本文僅向大家提供了一種C語言中棧和隊列的一種在業務中的運用方法，本文中棧和隊列的算法具有輕便簡單等相關特點。有關本文之外的其他技術將不在本文討論的范疇。

[1]陳竹云，葉雯. 數據結構中隊列的應用研究[J].電腦知識與技術，2017，13（03）：5-7.

[2]沈華. 數據結構課程中棧和隊列實驗教學方案設計[J].教育教學論壇，2016，（24）：274-276.

[3]嚴蔚敏，吳偉民.數據結構（C語言版）[M].北京：清華大學出版社，2012.

[4]譚浩強.C語言程序設計[M].北京：清華大學出版社，2012.

[5]朱戰立.數據結構——使用C語言[M].北京：電子工業出版社，2014.

[6]沈華，楊曉艷，馬馳，等.數據結構及應用：C語言描述[M].北京：機械工業出版社，2011.