栈与队列应用举例

精选文库 设有一个可以停放n辆汽车的狭长停车场,它只有一个大门可以供车辆进出。车辆按到达停车场时间的先后次序从停车场最里面向门口处停放最先到达的第一辆车停在停车场的最里面)。如果停车场已放满n辆车，则后来的车辆只能在停车场大门外的便道上等待，一旦停车场内有车开走,则排在便道上的第一辆车就可进入停车场。停车场内如有某辆车要开走,在它之后进入停车场的车辆都必须先退出停车场为它让路,待其开出停车场后,这些车辆再依原来的次序进入。每辆车在离开停车场时,根据它在停车场内停留时间的长短交费。如果停在便道上的车辆未进停车场就要离去，允许其离去时不收停车费,并且仍然保持在便道上等待的车辆的次序。现在编制一个程序来模拟停车场的管理。 首先确定模拟程序中需要的数据结构及其操作。由于停车场只有一个大门,因此可用一个栈来模拟；根据便道停车的特点，先排队的车辆先离开便道进入停车场,可以用一个队列来模拟；又因为排在停车场中间的车辆可以提前离开，因此还需要有一个地方(车辆规避所)保存为了让路离开停车场的车辆,很显然这也应该用一个栈来模拟。所以在程序中设置了两个顺序栈s1和s2分别表示停车场和规避所；设置了一个链队列q表示便道。它们的数据类型定义在下面的源程序中，为了操作方便，链队列表头结点中的num域中存放便道上的车辆数量。 程序执行时，当输入数据表示有车辆到达时，判断栈s1是否满，若未满就将新数据进栈s1；若栈已满,就将数据入队列q，表示车辆在便道上等待进入停车场。该操作过程由函数Arrive完成。当输入数据表示有车辆要离去时,就在栈s1中寻找此车牌号的车辆,如寻找到就让其离开停车场,并根据停车时间计费，同时将队列q的队头元素进栈s1；如没有找到,就到队列q中去寻找此车牌号的车辆。如在队列q中找到就允许其离开队列,并不收费；如找不到就显示出错信息。当离开停车场的车辆位于栈s1的中间时,必须先将此位置到栈顶之间的所有数据倒到栈s2中去,然后安排车辆出栈s1,最后将栈s2中的数据倒回到栈s1中来。该操作过程由函数Delive完成。显然，以上两个主要操作需要利用栈和队列的两个基本操作入栈（队列）和出栈（队列）来实现。源程序中的函数Display则可以随时显示停车场的状况。#includestdio.h#defineN10 /*停车场容量*/#defineM5 /*停车单价*/#defineTrue1#defineFalse0typedefstructint num;/*车牌号*/intarrtime;/*到达/离开时间*/ELEMTP;/*顺序栈的数据元素类型*/typedefstructELEMTPelemN;inttop;SqStack;/*顺序栈类型*/typedefstructnodeintnum;/*车牌号/便道上的车辆数量*/structnode*next;QNode;/*链队列的数据元素类型*/typedefstructQNode*front,*rear;LQueue;/*链队列类型*/voidInitStack_Sq(SqStack*s);/*初始化栈*/intPush_Sq(SqStack*s,ELEMTP x);/*入栈*/ELEMTPPop_Sq(SqStack*s);/*出栈*/voidInitQueue_L(LQueue *q); /*初始化队列*/voidEnQueue_L(LLQueue*q,intnum1);/*入队列*/intDelQueue_L(LQueue*q);/*出队列*/VoidInitStack_Sq(SqStack *s)s-top=0;IntPush_Sq(SqStack *s,ELEMTP x)if(s-top=N)return(False);elses-elems-top=x;s-top+;return(True);ELEMTPPop_Sq(SqStack *s)ELEMTPx;if(s-top=0)x.num=NULL;x.arrtime=NULL;return(x);elses-top-;return(s-elems-top);voidInitQueue_L(LQueue *q)q-front=(QNode *)malloc(sizeof(QNode);q-rear=q-front;q-front-next=NULL;q-front-num=0;voidEnQueue_L(Lqueue*q,intnum1)QNode*p;p=(QNode*)malloc(sizeof(QNode);p-num=num1;p-next=NULL;q-rear-next=p;q-rear=p;q-front-num+;intDelQueue_L(LQueue *q)QNode*p;intn;if(q-front=q-rear)return(NULL);elsep=q-front-next;q-front-next=p-next;if(p-next=NULL)q-rear=q-front;n=p-num;free(p);q-front-num-;return(n);voidArrive(SqStack*s1,LQueue*q,ELEMTPx)/*车辆x进入停车场*/intf;f=Push_Sq(s1,x);if(f=False)/*停车场栈s1已满入便道q*/EnQueue_L(q,x.num);printf(第%d号车停在便道第%d车位上n,x.num,q-front-num);elseprintf(第%d号车停在停车场第%d车位上n,x.num,s1-top);/* Arrive*/voidDelive(SqStack*s1,SqStack*s2,LQueue*q,ELEMTPx)/*车辆x离开停车场*/intn,f=False;ELEMTPy;QNode*p;While(s1-top0)&(f!=True)/*在栈s1中寻找车辆x*/y=Pop_Sq(s1);if(y.num!=x.num)n=Push_Sq(s2,y);elsef=True;if(y.num=x.num)/*寻找到车辆x*/printf(第%d号车应收费%d元n,y.num,(x.arrtime-y.arrtime)*M);while(s2-top0)/*将栈s2中的车辆倒回到栈s1中*/y=Pop_Sq(s2);f=Push_Sq(s1,y);n=DelQueue_L(q);if(n!=NULL)/*便道q上的第一辆车入栈s1*/y.num=n;y.arrtime=x.arrtime;f=Push_Sq(s1,y);printf(第%d号车停在停车场第%d号车位上n,y.num,s1-top);else/*栈s1中未找到车辆x*/while(s2-top0)/*将栈s2中的车辆倒回到栈s1中*/y=Pop_Sq(s2);f=Push_Sq(s1,y);p=q-front;/*在便道q上找到车辆x*/f=False;while(f=False&p-next!=NULL)if(p-next-num!=x.num)p=p-next;elsep-next=p-next-next;q-front-num-;if(p-next=NULL)q-rear=q-front;printf(第%d号车离开便道n,x.num);f=True;if(f=False)printf(输入数据错误，停车场和便道上均无%d号车n,x.num);/* Delive */voidDisplay(SqStack*s1,LQueue*q)/*显示停车场的状况*/intk;Qnode*p;printf(停车场状况:n);if(s1-top!=0)printf(车道车号n);for(k=0;ktop;k+)printf(%d%dn,k+1,s1-elemk.num);elseprintf(停车场没有车辆n);printf(便道状况:n);if(q-front-num)printf(车道 车号n);for(k=1,p=q-front-next;p;p=p-next)printf(%d %dn,k+,p-num);else printf(便道没有车辆n);/*Display */voidmain()charch1,ch2;SqStack*s1,*s2;LQueue*q;ELEMTPx;intflag;s1=(SqStack*)malloc(sizeof(SqStack);s2=(SqStack*)malloc(sizeof(SqStack);q=(LQueue*)malloc(sizeof(LQueue);InitStack_Sq(s1);InitStack_Sq(s2);InitQueue_L(q);flag=True;while(flag)printf(请输入您的选择n);printf(S-显示停车场状况n);printf(A-车辆到达n);printf(D-车辆离开n);printf(E-程序结束n);ch1=getchar();switch(ch1)caseS:Display(s1,q);break;caseA:printf(输入数据:车牌号，到达时间：);scanf(%d,%d,&x.num,&x.arrtime);Ar