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.