数据结构实验报告
实验二栈和队列及其应用
一、实验题目：
栈和队列及其应用——停车场管理
二、实验内容：
设停车场是一个可停放n辆车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北段），若停车厂内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车迹可开入；停车场内某辆车要离开时，在它之后进入的车连必须先退出车厂为它让路，待该车辆开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车时必须按它停留的时间长短缴纳费用。编写按上述要求进行管理的模拟程序。
可以将停车场定义成一个顺序栈s0，便道定义成一个链队列q，而停车场中的某辆车要离开，则在它后面进停车场的车必须让道，让其离开，所以必须有一个临时的顺序栈s1，存放让道的车辆。
当有车辆进停车场时，若栈s0不满，则直接进入栈s0；若栈s0满，则进入便道（链队列q）。若有s0中车辆x离开时，先让在x后面进栈的车从s0退栈并进入栈s1中，让x离开并收取停车费（在便道上停留的时间不收费），然后再把s1中所有元素退栈并重新进入s0栈，最后，将链队列q中的队头元素出队并进栈到s0中。
三、程序源代码：
#include
#include
#define OVERFLOW -1
#define N 2
#define PRICE 20
#define STACK_INIT_SIZE 100
//构造顺序栈结构
typedef struct data{
int num; //车牌号
int Atime; //车到达时间
}data;
typedef struct{
data *base;
data *top;
int stacksize;
}SqStack;
//构造链队列结构
typedef struct QNode{
int num; //车牌号
struct QNode *next;
}QNode,*QueuePtr;
typedef struct{
QueuePtr front;//队头指针
QueuePtr rear;//队尾指针
}LinkQueue;
void InitStack(SqStack &s)
{
//构造一个空栈s
s.base=(data *)malloc(STACK_INIT_SIZE*sizeof(data));
if(!s.base) exit (OVERFLOW); //存储分配失败
s.top=s.base; //栈空的条件
int sistacksize=STACK_INIT_SIZE;
}//InitStack
bool StackEmpty(SqStack &s)
{
//若栈s为空栈，则返回TRUE，否则返回FLASE
if(s.top==s.base) return true;
else
return false;
}
int GetTop(SqStack &s)
{
int e;
//若栈不空,则用e返回s的栈顶元素，并返回OK;否则返回ERROR if(s.top==s.base) return false;
e=(s.top-1)->Atime;
return e; //返回车进站的时间
}//GetTop
void Push(SqStack &s,int e,int e1)//e表示车牌号 e1表示车进站时间{
//插入元素e为新的栈顶元素
s.top->num=e;
s.top->Atime=e1;
s.top++;
}//Push
int Pop(SqStack &s)
{
int e;
//删除s的栈顶元素，用e返回其值
s.top--;
e=s.top->num;
return e; //返回车牌号
}//Pop
//---------------------------------
void InitQueue(LinkQueue &q)
{
//构造一个空队列q
q.front=q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!q.front) exit(OVERFLOW);
q.front->next=NULL;
}
void EnQueue(LinkQueue &q,int e) //e表示车牌号
{
//插入元素e为q的新的队尾元素
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
if(!p) exit(OVERFLOW);//存储分配失败
p->num=e;
p->next=NULL;
q.rear->next=p;
q.rear=p;
}
int DeQueue(LinkQueue &q)
{
int e;
//若队列不空，则删除q的队头元素，用e返回其值，并返回OK;否则返回ERROR if(q.front==q.rear) return false;
QueuePtr p;
p=q.front->next;
e=p->num;
q.front->next=p->next;
if(q.rear==p) q.rear=q.front;
free(p);
return e; //返回车牌号
}
bool QueueEmpty(LinkQueue &q)
{ //若队列q为空队列，则返回TRUE，否则返回FLASE
if(q.front==q.rear) return true;
else
return false;
}
void Car(SqStack &s0,SqStack &s1,LinkQueue &q,int n)
{//构造两个空栈s0 s1 一个空链队列q
InitStack(s0);
InitStack(s1);
