公共停车管理问题
- 目标:深入掌握栈和队列应用的算法设计。
-
内容:汽车在停车场内按车辆到达时间的先后顺序依次排列,若停车场内已停满n辆车,则后来的汽车只能在门外的便道等候,一旦有车开走,则排在便道上的第一辆车即可开入;当停车场内某辆车要离开时,在它之后进入的车辆必须先退出停车场为它让路,待该车辆开出大门外,其他车辆再按原次序进入停车场,每辆停放在停车场的车辆在它离开停车场时必须按停留的时间长短交费用。
-
问题概述:
----一共要开辟两个栈,一个队列。S1栈用来存取 停车场中车辆,S2栈用来存取某辆车离开时退出停车场的车辆,Q队列用来存取候车场中车辆。
----当S1不满时汽车进入其中,S1满时存入Q中,Q满时,显示停车场已满。当停车场S1出车时,若此车之后有车停入,则将之后的车倒入S2中,等S1中车辆出车后再将S2中车辆停入S12,同时将Q中的车辆停入停车场S1中。
- 源程序及系统文件使用说明:
using namespace std;
#include <iostream>
#define N 3 //停车场中最大停车数
#define M 2 //候车场中最大停车数
#define Money 10
typedef struct
{
int CarNumber[N];
int CarTime;
int top;
}SqStack; //堆栈定义
void InitStack(SqStack *&s) //初始化堆栈
{
s = (SqStack*)malloc(sizeof(SqStack));
s->top = -1;
}
int StackEmpty(SqStack*s) //检测是否为空
{
return(s->top == -1);
}
int StackFull(SqStack*s) //检测堆栈是否为满
{
return(s->top ==N -1);
}
int Push(SqStack*&s, int e) //入栈
{
if (s->top == N - 1)
return 0;
s->top++;
s->CarNumber[s->top] = e;
return 1;
}
int Pop(SqStack*&s, int &e) //出栈
{
if (s->top == -1)
return 0;
e = s->CarNumber[s->top];
s->top--;
return 1;
}
void DispStack(SqStack*s) //循环输出栈
{
int i;
for (i = s->top; i >= 0; i--)
cout<<s->CarNumber[i]<<" ";
}
typedef struct //队列定义
{
int WaitCarNumber[M];
int front, rear;
}SqQueue;
void InitQueue(SqQueue*&q) //初始化队列
{
q = (SqQueue*)malloc(sizeof(SqQueue));
q->front = q->rear = -1;
}
int QueueEmpty(SqQueue*q) //检测队列是否为空
{
return(q->front == q->rear);
}
int QueueFull(SqQueue*q) //检测队列是否为满
{
if (q->rear== M-1)
return 1;
else return 0;
}
int enQueue(SqQueue*&q, int e) //入队
{
if ((q->rear + 1) % M == q->front) //队满上溢出
return 0;
q->rear = (q->rear + 1) % M; //队尾增1
q->WaitCarNumber[q->rear] = e; //队尾位置插入元素e
return 1;
}
int deQueue(SqQueue*&q, int &e)
{
if (q->front == q->rear) //队空的情况(队空下溢出)
return 0;
q->front = (q->front + 1) % M;
e = q->WaitCarNumber[q->front];
return 1;
}
void DispQueue(SqQueue*q) //循环输出队列
{
int i;
i = (q->front + 1) % M;
cout<<q->WaitCarNumber[i]<<" ";
while ((q->rear - i + M) % M > 0)
{
i = (i + 1) % M;
cout<<q->WaitCarNumber[i]<<" ";
}
}
主函数:
int main()
{
int Menu; //设置菜单
int Number, Time,e; //设定时间和车号
int i, j, k;
SqStack *S1, *S2; //S1停车场内车辆 S2为出车暂时出来的车辆
SqQueue *Q; //Q便道内的车辆
InitStack(S1); InitStack(S2); InitQueue(Q); //初始化
do {
cout << "*******************************" << endl;
cout << "***1.停车 2.出车 3.查询停车场车辆 4.查询候车场车辆 5.退出***" << endl;
cout << "*******************************" << endl;
cout << "请输入您的选择:";
cin >> Menu;
switch (Menu)
{
case 1: //停车
cout << "请输入车号(整数):";
cin >> Number;
if (!StackFull(S1)) //栈不满车入栈
{
Push(S1,Number);
cout << "停车场有" << S1->top+1<<"辆车"<<endl;
}
else//栈满入队 若此时队不满 则车入队
{
if (!QueueFull(Q))
{
enQueue(Q, Number);
cout << "候车场有" << Q->rear+1<<"辆车"<<endl;
}
else
cout << "候车场已满无法停车" << endl;
}
break;
case 2: //出车
cout << "请输入车号:";
cin >> Number;
cout << "请输入停车时间(小时):" ;
cin >> Time;
for (i = 0; i <= S1->top && S1->CarNumber[i] != Number; i++); //在栈中找此车号
if (i > S1->top)
cout<<"未找到该车号的汽车"<<endl;
else
{
k= S1->top - i;
for (j = 1; j<=k; j++)
{
Pop(S1, e);
Push(S2, e); //倒车到临时栈S2中
}
Pop(S1, e) ; //将此车出栈
cout << "已找到此车, 此车车号为:" << Number << endl;
cout << "共停时间:" << Time << endl;
cout << "需要交付:" << Money * Time << endl;
while(!StackEmpty(S2)) //将临时栈S2重新回到S1中
{
Pop(S2, e);
Push(S1, e);
}
if (!QueueEmpty(Q)) //队不空时,将队头进栈S1
{
deQueue(Q, e); //出队头一个元素e
Push(S1, e); //入栈
}
}
break;
case 3: //输出停车场中的车辆
if (!StackEmpty(S1))
{
cout<<"停车场中的车号为:";
DispStack(S1);
cout << endl;
}
else
cout<<"停车场中无车辆"<<endl;
break;
case 4: //输出候车场中的车辆
if (!QueueEmpty(Q))
{
cout << "候车场中的车号为:";
DispQueue(Q);
cout << endl;
}
else
cout<<"候车场中无车辆"<<endl;
break;
case 5: //退出并输出停车场和候车场车辆
if (!StackEmpty(S1))//输出停车场中的车辆
{
cout<<"停车场中的车号为:";
DispStack(S1);
cout << endl;
}
if (!QueueEmpty(Q))//输出候车场中的车辆
{
cout<<"候车场中的车号为:";
DispQueue(Q);
cout << endl;
}
break;
default: //其他情况
cout<<"错误请重试";
break;
}
} while (Menu!=5);
return 0; }
开发环境与开发工具
- 开发环境:windows
- 开发工具:Microsoft Visual Studio 2017