3.4 栈与队列的综合应用举例
栈和队列这两种特殊的线性表与基本线性表一样，在实际工作和生活中有着广泛的应用。本节通过一个实例再一次给出栈与队列的综合应用，使读者能更进一步区分栈与队列的特性和它们各自的实现技巧。
【例3-8】停车场管理问题。
【问题描述】假设停车场是一个可停放n辆车的狭长通道，并且只有一个大门可供汽车进出。在停车场内，汽车按到达的先后次序，由北向南依次排列（假设大门在最南端）。若车场内已停满n辆车，则后来的汽车需在门外的便道上等候，当有车开走时，便道上的第一辆车即可驶入。当停车场内某辆车要离开时，在它之后进入的车辆必须先退出停车场为它让路，待该辆车开出大门后，其他车辆再按原次序返回停车场。每辆车离开停车场时，应按其停留时间的长短交费（在便道上停留的时间不收费）。
试编写程序，模拟上述管理过程。
【问题分析】由于停车场中某辆车的离开是按在它之后进入的车辆必须先退出停车场为它让路的原则下进行的，显然满足了“后进先出”的特性，所以可以用栈式结构来模拟停车场；而对于指定停车场，它的车位数是相对固定的，因而本题采用顺序栈来加以实现，并假设栈的容量为10。又由于便道上的车是按先到先开进停车场的原则进行的，即满足“先进先出”的特性，所以可以用队列来模拟便道；而对于便道上停放车辆的数目是不固定的，因而本题采用链队列来加以实现。
为了能更好地模拟停车场管理，可以从终端读入汽车到达或离去的数据，每组数据应该包括两项：①汽车牌照号码；②是“到达”还是“离去”。程序中通过库函数time（0）自动获取当前“到达”或“离去”的时间秒数。与每组输入信息相应的输出信息为：若是到达的车辆，则输出其在停车场中或便道上的位置；若是离去的车辆，则输出其在停车场中停留的时间和应交纳的费用。
费用的计算方法是：由离开时间减去到达时间求得停留时间的总秒数，因time函数返回的为unix时间戳，即从1970年1月1日（UTC/GMT的午夜）开始所经过的秒数。然后再将秒数除以60使其转换成多少分钟，当不足整数分钟时，则以整数分钟计算。如停留时间是大于5分钟而小于6分钟，则以6分钟计算。最后每分钟的停车费乘以停车时间即可计算出总的停车费用。此题以每分钟2元的费用进行模拟计算。
【参考代码】
#include"Queue.cpp"//Queue.cpp中有队列抽象数据类型定义中的所有基本操作函数
#include"Stack.cpp"//Stack.cpp中有栈抽象数据类型定义中的所有基本操作函数
#include ＜stdio.h＞
#include ＜time.h＞
#include ＜string.h＞
#define DEPARTURE 0； //标识车辆离开
#define ARRIVAL 1； //标识车辆到达
double fee 2.0 //每分钟停车费用，全局变量
SqStack S； //顺序栈存放停车场内的车辆信息，全局变量
LinkQueue Q； //链队列存放便道上的车辆信息，全局变量
typedef struct
{ int state； //车辆状态，离开或到达
time_t arrTime； //车辆达到时间
time_t depTime； //车辆离开时间
char *license； //车牌号
}CarInfo； //用于存放车辆信息的类型
typedef CarInfo QElemType；
typedef CarInfo SElemType；
void ParkingManag（char *license，char *action）
//停车场管理，参数license表示车牌号码，action表示此车辆的动作到达或离开
{ if（strcmp（"arrive"，action）==0）{ //车辆到达
CarInfo info； //定义一个车辆信息类型变量
info.license=l icense； //修改车辆状态
if（StackLength（S）＜ S.stacksize）{ //停车场未满
info.arrTime=time（0）； //当前时间初始化到达时间
info.state=ARRIVAL；
Push（S，info）；
printf（"%s停放在停车场第%d个位置!\n"，info.l icense，StackLength（S））；
}
else { //停车场已满
EnQueue（Q，info）； //进入便道队列
printf（"%s停放在便道第%d个位置\n"，info.l icense，QueueLength（Q））；
}
}
else if（strcmp（"depart"，action）==0） //车辆离开
{ CarInfo info；
int location=0； //车辆的位置
SqStack S2；
InitStack（S2）； //构造栈用于存放因车辆离开而导致的其他车辆暂时退出停车场
for（int i=StackLength（S）；i ＞ 0；i--）{
Pop（S，info）；
if（strcmp（info.license，l icense）==0） //将离开的车辆
{ info.depTime=time（0）； //用当前时间来初始化离开时间
info.state=DEPARTURE；
location=i； //取得车辆位置信息
break；
}
else //其他车辆暂时退出停车场
Push（S2，info）；
}//for
while（! StackEmpty（S2）） //其他车辆重新进入停车场
{ CarInfo e；
Pop（S2，e）；
Push（S，e）；
}
if（location !=0） //停车场内存在指定车牌号码的车辆
//计算停放时间，并把秒换成分钟
{ double time=（d）ouble（info.depTime-info.arrTime）/60；
if（（int）time＜time） //停车时间处理后输出
printf（"%s停放%.2f分钟，费用为：%.2f\n"，info.license，time，（int）（time+1）*fee）；
else
printf（"%s停放%.2f分钟，费用为：%.2f\n"，info.license，time，（int）time*fee）；
}
if（!QueueEmpty（Q）） //便道上的第一辆车进入停车场
{ DeQueue（Q，info）；
info.arrTime=time（0）； //当前时间来初始化到达时间
info.state=ARRIVAL；
Push（S，info）；
}
}
}//ParkingManag
int main（ ）
{ char l icense[20]；
char action[20]；
InitStack（S）； //顺序栈存放停车场内的车辆信息
InitQueue（Q）； //链队列存放便道上的车辆信息
//初始化 12 辆车，车牌号分别为 1，2，…，12，其中有 10 辆车停在停车场内，2 辆车停放在便道上
for（int i=1；i ＜=12；i++）
{ printf（"请输入第%d辆车的车牌号："，i）；
gets（license）；
ParkingManag（license，"arrive"）；
}
printf（"请输入车牌号："）；
gets（license）；
printf（"arrive or depart ?"）；
gets（action）；
ParkingManag（license，action）； //调用停车场管理函数
return 0；
} //例3-8 程序结束
此程序的运行结果如图3-30所示。
图3-30 例3-8 程序的运行结果