#include <stdio.h>
#include <stdlib.h>
#define Max 4
#define Max1 100
typedef struct 
{
        int data1[Max];
        int data2[Max];
        int top;
}SqStack;
typedef struct qnode 
{ 
        int data1;
        int data2;
        struct qnode *next;
}QNode;
typedef struct
{
        QNode *front;
        QNode *rear;
}LiQueue;
void InitStack(SqStack *&s)                      //初始化顺序栈 
{
     s=(SqStack *)malloc(sizeof(SqStack));
     s->top=-1;
}
void Push(SqStack *&s,int a,int b)                //元素入栈   
{
    s->top++;
    s->data1[s->top]=a;
    s->data2[s->top]=b;
}
void InitQueue(LiQueue *&q)                     //初始化链队 
{
     q=(LiQueue *)malloc(sizeof(LiQueue));
     q->front=q->rear=NULL;
}
void enQueue(LiQueue *&q,int a,int b)          //元素入对队 
{
     QNode *s;
     s=(QNode *)malloc(sizeof(QNode));
     s->data1=a;
     s->data2=b;
     s->next=NULL;
     if(q->rear==NULL)
       q->front=q->rear=s;
     else
     {
         q->rear->next=s;
         q->rear=s;
     }
}
int deQueue(LiQueue *&q,int &a,int &b)           //队首元素出队 
{
    QNode *t;
    if(q->rear==NULL)
       return 0;
    t=q->front;
    if(q->front==q->rear)
       q->front=q->rear=NULL;
    else
       q->front=q->front->next;
    a=t->data1;
    b=t->data2;
    free(t);
    return 1;                  
}
void SqStackCopy(SqStack *&s1,SqStack *&s2,int i)   //将栈s1中第i+1个之后的元素到栈顶元素退栈到栈s2中      
{
     while(s1->top>i)
     {
                      s2->top++;
                      s2->data1[s2->top]=s1->data1[s1->top];
                      s2->data2[s2->top]=s1->data2[s1->top];
                      s1->top--;
     }
}
void feecharge(int a,int b)                    //收费函数 
{
     int t;
     t=(b-a)*2;
     printf("该车离开，该车应收费:%d元\n",t); 
}
void print(SqStack *s,LiQueue *q)            //打印当前停车场和便道的停车情况 
{
     QNode *p;
     printf("现在停车场的车辆有:");
     while(s->top!=-1)
     {
                      printf("%d,%d  ",s->data1[s->top],s->data2[s->top]);
                      s->top--;
     }
     printf("\n");
     printf("现在便道的车辆有:");
     p=q->front;
     while(p!=NULL)
     {
                   printf("%d,%d  ",p->data1,p->data2);
                   p=p->next;
     }
     printf("\n");
}    
int main(void)
{
     SqStack *s1,*s2;
     LiQueue *q;
     QNode *p,*w;
     int r,i,a,b,m,n,k,t,u=0;
     InitStack(s1);                                         //s1初始化 
     InitStack(s2);                                         //s2初始化 
     InitQueue(q);                                          //q初始化  
     print(s1,q);
     for(r=0;r<Max1;r++)
     {
       printf("请输入车辆的编号，到达或离开的时间\n"); 
       scanf("%d,%d",&m,&n);
       printf("请输入处理车辆的代号<1:到达，2:离开，3:结束>:");
       scanf("%d",&k);
       if(k==1)                                         //该车进入停车场          
        {
           if(s1->top!=Max-1)                                  //s1未满时 
           {
              Push(s1,m,n);                            //车进入停车场 
              print(s1,q);
           }
           else                                           //车停在便道 
           { 
              enQueue(q,m,n); 
              print(s1,q);
           } 
        } 
       if(k==2)                                        //查找是否有编号为m的车 
        {
           for(i=0;i<=s1->top;i++)                     //在停车场里查找是否有编号为m的车       
             {
                if(s1->data1[i]==m)                    //停车场有编号为m的车 
                 {  
                     printf("停车场有编号为%d的车\n",m);
                     u=1;
                     SqStackCopy(s1,s2,i);              //停车场里编号为m的车之后的车都退栈到s2 
                     s1->top--;                         //编号为m 的车开离停车场 
                     SqStackCopy(s2,s1,-1);             //s2中的车全部进栈到s1中 
                     feecharge(s1->data2[i],n);         //编号为m的车应收的费用 
                     if(q->rear!=NULL)
                     {
                       deQueue(q,a,b);                  //便道的队首车辆出队 
                       Push(s1,a,b);                    //便道的队首车辆进入停车场 
                     }
                     print(s1,q);
                 }
             } 
           if(u==0)                                     //若停车场未找到编号为m的车 
             {
                if(q->rear!=NULL)                       //便道有车时，在便道查找是否有编号为m的车 
                {
                   p=q->front;
                   if(p->data1==m)                       //便道的队首元素就是编号为m的车，直接队首元素出队,不要交费 
                      deQueue(q,m,n);
                   else                                  //在队首以后的结点中查找编号为m的车 
                   {
                       while(p!=NULL)
                       {
                          if(p->data1==m)                    //便道有编号为m的车 
                           {
                             printf("便道有编号为%d的车\n",m);
                             w=q->front;
                             while(w!=NULL)                 //查找便道编号为m的车之前的车 
                             {
                                if(w->next==p)
                                    break;
                                else
                                    w=w->next;
                             }
                             w->next=p->next;
                             free(p);                    //便道上编号为m的车直接离开，不需要交费 
                             u=1;
                             print(s1,q);
                           }
                           if(u==1)
                              break;
                           else
                              p=p->next;
                      }
                   }
                }
              }  
              if(u==0)
                  printf("停车场和便道都不存在编号为%d的车\n",m);
        }
        if(k==3)
           break;
    }
  system("PAUSE");    
  return 0;
}