实验二栈和队列实验报告---停车场问题.doc

数据结构实验报告
实验二 栈和队列实验
班级：计12-2 姓名：毛文祥 学号

熟悉栈和队列的基本特性，掌握栈和队列基本运算的实现过程。重点掌握栈和队列各种操作的实现。

设停车场内只有一个可停放 n 辆汽车的狭长通道，且只有一个大门可供汽车进出，汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满 n 辆汽车，则后来的汽车只能在门外的便道上等候, 一旦有车开走，则排在便道上的第一辆车即可开入，当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用，试为停车场编制按上述要求进行管理的模拟程序。

该停车场问题可以理解为栈和队列的结合，因为停车场内部是先进入的车辆放到最北面，之后进来的车辆依次排到南面，如果有车辆要出去，那么在它之后进入的车辆必须先退出，给这个车辆让路，这个车辆出去之后再返回到停车场，这就是栈的先进后出的操作一致，因此选择栈存储停车场内的车辆，而便道上的车辆则不同，便道上的车辆，进来之后就排在最西边，如果有车辆要出去，那么在它之前车辆必须依次排到队尾，之后这个车辆开出便道，这和队列的先进先出操作一致，因此用队列存储便道上的车辆。

：
struct Park
{
int status;//车的状态,0表示进入,1表示离开
int num;//车的牌号
int time;//车离开或者进入的时间
};//车的基本信息的结构体定义
typedef struct
{
struct Park *base;//栈底指针
struct Park *top;//栈顶指针
int stacksize;
}SqStack;栈数据结构定义
队列数据结构类型定义
typedef struct QNode
{
struct Park data;//数据域
struct QNode *next;
}QNode,*Queueptr;
typedef struct
{
Queueptr front;//队头指针
Queueptr rear;//队尾指针
}LinkQueue;

void InitStack(SqStack &S);
//初始化一个栈
void Push(SqStack &S,struct Park e);
//压入一个栈顶元素
struct Park GetTop(SqStack &S);
//得到栈顶元素,函数的返回值为存放车的信息的结构体变量
struct Park Pop(SqStack &S);
//删除栈顶元素，且函数的返回值为栈顶元素
int EmptyStack(SqStack S);
//判断一个栈是否为空，空返回1，非空返回0
void VisitStack(SqStack S);
//遍历一个栈而且输出栈元素的信息,输出顺序为从栈底元素到栈顶元素
void InitQueue(LinkQueue &Q);
//初始化一个队列
void InsertQueue(LinkQueue &Q,struct Park e);
//在队列的队尾处中插入一个元素
void DeleteQueue(LinkQueue &Q);
//删除队头元素
void VisitQueue(LinkQueue Q);
//遍历队列，且输出队列元素信息,按照从队头到队尾的顺序输出
void DQueue(LinkQueue &Q,struct Park e);
//在队列中删除元素信息的数据域中的num值和e的num相等的元素
int DStack(SqStack &S,struct Park p,double &d);
//在栈中查找是否有与p的num值相等的元素，如果找到，改变d的值，函数值返回1，否则函数值返回0
主程序模块处理过程描述
首先输入该车辆信息，判断是否是输入结束标志，是则跳出循环，否则判断是否是进入的车辆，如果是进入的车辆，那么判断此时栈是否已经满了，如果此时栈已满，那么该车辆就要入队列，否则入栈。如果该车辆是出去的，那么