数据结构--栈和队列--停车场问题-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构--栈和队列--停车场问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、问题描述

二、实验目的

三、需求分析

四、方法描述

五、代码实现

六、实验结果测试

一、问题描述

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

二、实验目的

熟悉栈和队列的基本特性，掌握栈和队列基本运算的实现过程。

三、需求分析

问题理解：该问题结合了栈和队列。停车场进出车相当于栈，先进后出。便道上的车，要排队，相当于队列，先进先出。

其中本题要考虑进车、出车、缴费三个模块问题

进车：停车场是否停满了，若停满了则在便道等候

出车：找到要出去的车，是在停车场还是便道。停车场则如栈的方式出去，便道为队列。同时其他车辆更新其时间

缴费：计算其停车时间经行计算。

解决问题的策略：

该程序使用一个栈来表示停车场，使用一个链式队列来表示等待区。程序还有一个临时停车区，使用另一个栈来表示。当一辆车进入停车场时，程序会检查停车场是否有空位。如果有空位，车辆将被停放在停车场中。如果没有空位，车辆将被添加到等待区。

当一辆车离开停车场时，程序首先检查车辆是否在停车场或等待区中。如果车辆在停车场中，程序会计算应付的金额并将车辆从停车场中移除。如果车辆在等待区中，程序会将车辆从等待区中移除并将其添加到临时停车区中。

在所有车辆离开停车场后，程序输出仍然停留在临时停车区和等待区的车的车牌号。

四、方法描述

本题定义5个结构体：车辆信息、停车场顺序存储栈、车辆的信息和便道链队中的节点、便道链队、缓存车道。抽象出基本操作描述：定义10个自定义函数。

首先，程序通过输入获取停车场的最大容量和停车费用。

接着，程序初始化了停车场（carpark）、便道链队（linkWait）和临时区（dengdai）。

然后，程序通过循环不断接收输入，每次输入包括车辆的进出状态、车牌号和时间。当输入的进出状态、车牌号和时间都为0时，循环结束。

对于每次输入，程序根据车辆的进出状态进行处理：

如果是进场，检查停车场是否有空位，有空位则将车辆入场，否则将车辆放到便道上。

如果是出场，程序会根据车辆的状态在停车场和便道上进行查找和移动操作，以计算费用和安排车辆出场。

五、代码实现

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
int max;
typedef struct//车辆信息 
{
	int inOut;
	int carNumber;
	int time;
	int inpark;//车辆是否在停车场中 1:在停车场中；0：在便道中 
}cardata;

typedef struct//停车场顺序存储栈 
{
	cardata *top;
	cardata *base;
	int stacksize;
}carpark;


typedef struct waitcar//便道链队 
{
	cardata base;
	struct waitcar *next;
}waitcar,*waitcarPtr;

typedef struct//便道链队
{
	waitcarPtr front;
	waitcarPtr rear;
}linkWait;

typedef struct
{
	cardata *top;
	cardata *base;
	int stacksize;
}dengdai;


void Initdengdai(int max,dengdai& d)//新建临时停放区 
{
	d.base=(cardata *)malloc(max*sizeof(cardata));
	if(!d.base) return;
	d.stacksize=1;
	d.top=d.base;
}

void dengdaipush(dengdai& d,cardata* &data)//临时停放区进车 
{
	*d.top=*data;
	d.top++;
	d.stacksize++;
}

void dengdaipop(dengdai& d,cardata* &data)//临时停放区出车
{
	if(d.top==d.base) return;
	d.top--;
	data=d.top;
	d.stacksize--;
}


void InitPark(int m,carpark& c)//新建停车场 
{
	c.base=(cardata *)malloc(m*sizeof(cardata));
	if(!c.base) return;
	c.stacksize=0;
	c.top=c.base;
}

void parkpush(carpark& c,cardata data)//停车场进车 
{
	if(c.top-c.base>=max) return;
	if(!c.base) return;
	*c.top=data;
	c.top++;
	c.stacksize++;
}

void parkpop(carpark& c,cardata* &data)//停车场出车
{
	if(c.top==c.base) return;
	c.top--;
	data=c.top;
	c.stacksize--;
}

void searchPark(carpark& c,cardata* &data)//查找停车场栈顶 
{
	if(c.top==c.base) return;
	data=(c.top-1);
}

void Initwait(linkWait& l)//新建便道
{
	l.front=l.rear=(waitcarPtr)malloc(sizeof(waitcar));
	if(!l.front) return;
	l.front->next=NULL;
}

void Enwait(linkWait& l,cardata data)//进入便道 
{
	waitcarPtr p;
	p=(waitcarPtr)malloc(sizeof(waitcar));
	if(!p) return;
	p->base=data;
	p->next=NULL;
	l.rear->next=p;
	l.rear=p;
	if(l.front->next == NULL){
		l.front->next = l.rear;
	}
}

void Dewait(linkWait& l,cardata* &data)//出便道 
{
	waitcarPtr p;
	if(l.front==l.rear) return;
	p=l.front->next;
	*data=p->base;
	l.front->next=p->next;
	if(l.rear==p) l.rear=l.front;
	free(p);
}

int main()
{
	int parkCarNum=0;
	int i,res=0;
	double price,P;
	scanf("%d %lf",&max,&price);
	carpark c;
	linkWait l;
	dengdai d;
	waitcarPtr test;
	InitPark(max,c);
	Initwait(l);
	Initdengdai(max,d);
	cardata data,*DATA;//DATA为测试数据 
	while(1)
	{
		scanf("%d %d %d",&data.inOut,&data.carNumber,&data.time);
		if(data.inOut==0&&data.carNumber==0&&data.time==0) break;
		if(data.inOut==0)//入场 
		{
			if(c.stacksize<max)
			{
				data.inpark=1;
				parkpush(c,data);
			}
			else
			{
				data.inpark=0;
				Enwait(l,data);
			}
		}
		else//出场
		/* 1.找该车是在停车场还是便道 
		2.若在停车场让后面的车去临时区，
		搜索到出车的信息并计算费用 ,
		把临时区的车放回停车场，让便道的第一辆车进停车场并更改time
		3.若在便道上让前面的车到临时区，
		删掉离开的车的那个节点，
		把临时区的车接到链表的末尾  
		
		(每次要清理干净等待区)
		*/
		{
			data.inpark=1;
			res=0;
			if(data.inpark==1)
			{
				while(c.stacksize>0)
				{
					parkpop(c,DATA);
					if(DATA->carNumber==data.carNumber)
					{
						P=(data.time-DATA->time)*price;
						printf("%d %.2lf\n",data.carNumber,P);
						res=1;
						break;
					}
					dengdaipush(d,DATA);
				}
				while(d.top!=d.base)
				{
					dengdaipop(d,DATA);
					parkpush(c,*DATA);
				}
				if(res==1&&l.front!=l.rear)
				{
					Dewait(l,DATA);
					DATA->inpark=1;
					DATA->time=data.time;
					parkpush(c,*DATA);
					
				}
			} 
		    if(res==0)
			{
				DATA=&(l.front->next->base);
				while(DATA->carNumber!=data.carNumber)
				{
					Enwait(l,*DATA);
					Dewait(l,DATA);
				}
			}
		}
	}
	
	while(c.stacksize>0)
	{
		parkpop(c,DATA);
		dengdaipush(d,DATA);
	}
	while(d.top!=d.base)
	{
		dengdaipop(d,DATA);
		printf("%d ",DATA->carNumber);
		parkpush(c,*DATA);
	}
	putchar('\n');
	test=l.front->next;
	while(l.rear!=test)
	{
		DATA=&(test->base);
		printf("%d ",DATA->carNumber);
		test=test->next;
	}
	return 0;
}