#define OK 1
#define ERROR 0
#define GARAGE 2
#define TAX 5
#define TAX2 0
#include<stdio.h>

typedef struct SNode{
 int cartag,time;
}SNode;
typedef struct QNode{
 int cartag,time;
 struct QNode *next;
}QNode;
typedef struct{
 struct SNode home[GARAGE];
 int stacktop;
}CarStack;
typedef struct{
 QNode *front,*rear;
}CarQueue;

CarStack CarS;
CarQueue CarQ;

void CarArrive(int cartag,int cartime){
 if(CarS.stacktop<GARAGE){
  CarS.home[CarS.stacktop].cartag=cartag;
  CarS.home[CarS.stacktop].time=cartime;
  printf("Car %d is in garage now(time: %d)!\n",CarS.home[CarS.stacktop].cartag,CarS.home[CarS.stacktop].time);
  CarS.stacktop++;
 }else{
  CarQ.front->cartag=cartag;
  CarQ.front->time=cartime;
  printf("Car %d is in small road now(time:%d)!\n",CarQ.front->cartag=cartag,CarQ.front->time=cartime);
  CarQ.front->next=(QNode *)malloc(sizeof(QNode));
  CarQ.front=CarQ.front->next;
 }
}
void CarLeave(int cartag,int cartime){
 CarStack CarS2;
 int i,findcar=-1;
 QNode *p,*f;
 CarS2.stacktop=0;
 for(i=0;i<CarS.stacktop;i++){
  if(cartag==CarS.home[i].cartag){
   findcar=i;
   break;
  }
 }
 if(-1!=findcar){
  for(;--CarS.stacktop>findcar;CarS2.stacktop++){
   CarS2.home[CarS2.stacktop].cartag=CarS.home[CarS.stacktop].cartag;
   CarS2.home[CarS2.stacktop].time=CarS.home[CarS.stacktop].time;
  }
  printf("Car %d is leave garage now(time: %d,stay(%d))!\n",CarS.home[CarS.stacktop].cartag,cartime,cartime-CarS.home[CarS.stacktop].time);
  printf("this car should pay %d\n",(cartime-CarS.home[CarS.stacktop].time)*TAX);
  for(i=CarS2.stacktop-1;i>=0;i--){
   CarS.home[CarS.stacktop].cartag=CarS2.home[i].cartag;
   CarS.home[CarS.stacktop].time=CarS2.home[i].time;
   CarS.stacktop++;
   CarS2.stacktop--;
  }
  if(CarQ.front!=CarQ.rear){
   CarS.home[CarS.stacktop].cartag=CarQ.rear->cartag;
   CarS.home[CarS.stacktop].time=CarQ.rear->time;
   CarS.stacktop++;
   p=CarQ.rear;
   CarQ.rear=CarQ.rear->next;
   free(p);
  }
 }else{
  p=CarQ.rear;
  if(p!=CarQ.front&&p->cartag!=cartag){
   f=p->next;
   while(f!=CarQ.front&&f->cartag!=cartag){
    p=f;
    f=f->next;
   }
   if(f->cartag==cartag){
    findcar=1;
    p->next=f->next;
    printf("Car %d is leave small road now(time: %d,stay(%d))!\n",f->cartag,cartime,cartime-f->time);
    printf("This car should pay %d\n",(cartime-f->time)*TAX2);
    free(f);
   }
  }
  if(p->cartag==cartag){
   findcar=1;
   CarQ.rear=CarQ.rear->next;
   printf("Car %d is leave small road now(time: %d,stay(%d))!\n",p->cartag,cartime,cartime-p->time);
   printf("This car should pay %d\n",(cartime-p->time)*TAX2);
   free(p);
  }
 }
 if(-1==findcar)printf("Num %d car is not found!\n",cartag);
}
int Move(char carmove,int cartag,int cartime){
 switch(carmove){
  case 'A':CarArrive(cartag,cartime);break;
  case 'D':CarLeave(cartag,cartime);break;
  case 'E':printf("EXIT!\n");return ERROR;
  default :printf("Input ERROR!\n");break;
 }
 return OK;
}

main(){
 int go=1,cartag,cartime;
 char carmove;
 CarS.stacktop=0;
 CarQ.rear=CarQ.front=(QNode *)malloc(sizeof(QNode));
 while(go){
  printf("\nPlease enter the information!\n");
  printf("move:\t\t");carmove=getch();
  printf("%c\ncar number:\t",carmove);scanf("%d",&cartag);
  printf("time:\t\t");scanf("%d",&cartime);
  if(!Move(carmove,cartag,cartime))go=0;
 }
 getch();
}