#include <stdio.h>
#include<iostream>
#include<string.h>
#include<math.h>
#include<malloc.h>
using namespace std;

int n=2;//定義車場的容量為n,即場內最多能停n輛車

//模擬停車場的堆棧的性質
typedef struct car{     
    int number;    //汽車車號
    int arv_time;    //汽車到達時間
}Scar;

typedef struct{
   Scar   *base;    //停車場的堆棧底
   Scar    *top;    //停車場的堆棧頂
   int stacksize;
}Sstack;

//堆棧的基本操作；
int  initstack(Sstack &S)    //構造一個空棧
{
    S.base=(Scar*)malloc(sizeof(car));
    if(!S.base)     return -1;
    S.top=S.base;
    S.stacksize=0;
   return 0;
}
int push(Sstack  &S, Scar e) //把元素e壓入s棧
{
    *S.top++=e;
    S.stacksize++;
	return 0;
}

int  pop(Sstack &S,  Scar &e)    //把元素e彈出s棧
{
    if(S.top==S.base) 
    {
        printf("停車場為空 !!");
        return  -1;
    }
    e=*--S.top;
    S.stacksize--;
	return 0;
}

//模擬便道的隊列的性質；
typedef struct duilie{     
    int number;      //汽車車號
    int arv_time;      //汽車到達時間
   struct duilie *next;
}*queueptr;

typedef struct{
    queueptr front;    //便道的隊列的對頭
    queueptr rear;    //便道的隊列的隊尾
    int length;
}linkqueue;

//隊列的基本操作；
int initqueue(linkqueue &Q) //構造一個空隊列 
{
    Q.front=Q.rear=(queueptr)malloc(sizeof(duilie));
    if(!Q.front||!Q.rear)
        return -1;
    Q.front->next=NULL;
    Q.length=0;
	return 0;
}
int  enqueue(linkqueue &Q , int number , int arvtime) //在隊尾插入一個新的元素（屬性為number，ar_time
{
    queueptr p;
    p=(queueptr)malloc(sizeof(duilie));
    if(!p) return 0;
    p->number=number;
    p->arv_time=arvtime;
    p->next=NULL;
    Q.rear->next=p;
    Q.rear=p;
    Q.length++;
   return 0;

}
void Dequeue(linkqueue &Q, queueptr &w) //若隊列不空,則刪除隊頭元素,用w返回其值,（屬性為number，ar_time）
{
    queueptr p;
    if(Q.front==Q.rear) 
    {
		cout<<"停車場的通道為空 ! !"<<endl;
		return;
    }
    p=Q.front->next;
    w=p;    
    Q.front->next=p->next;
    Q.length--;
    if(Q.rear==p)  Q.rear=Q.front;
	//free(p);
   
}

void Arv_Car(Sstack &S,  linkqueue &Q)    //對進入停車場的汽車的處理；
{
    int number,time_a;
  cout<<"車牌為：";
   cin>>number;
   cout<<"到達時刻:";
   cin>>time_a;
    if(S.stacksize<n)
    {
       Scar e;
       e.number=number;
       e.arv_time=time_a;
     push(S,e);
	cout<< " 該車已進入停車場,停在第 " <<S.stacksize<<"   號車道  "<<endl;
	}
    else
    {
     enqueue(Q,number,time_a);
	 cout<<"停車場已滿，該車先停在便道的第  " << Q.length<<  "個位置上"<<endl<<endl;
     }
}

void depart_car(Sstack &St, Sstack &Sd, linkqueue &Q) //對離開的汽車的處理；
{                                                                                                        //St堆棧為停車場，Sd堆棧為倒車場
    int number=0, time_d=0, flag=1,money,arvtime;              //Q為便道隊列
    Scar e,q_to_s;
    queueptr w;

	cout<<"車牌為：";
    cin>>number;
   cout<<endl<<"出場的時刻：";
   cin>>time_d;

    while(flag)    //找到要開出的車，并彈出停車場棧
    {
		  pop(St,e);
		  push(Sd,e);
		  if(e.number==number)
		  {
			 flag=0;
			 money=(time_d-e.arv_time)*2;
             arvtime=e.arv_time;
     }
    }

    pop(Sd,e);    //把臨時堆棧的第一輛車（要離開的）去掉；

    while(Sd.stacksize) //把倒車場的車倒回停車場
    {
        pop(Sd,e);
        push(St,e);
    }

    if(St.stacksize<n && Q.length!=0) //停車場有空位，便道上的車進入停車場
    {
		 Dequeue(Q,w);
		 q_to_s.arv_time=time_d;
		 q_to_s.number=w->number;
		 push(St,q_to_s);
		cout<<"車牌為"<< q_to_s.number<<" 的車已從便道進入停車場,停在第 "<<St.stacksize<<"  號車道上"<<endl<<endl;
    }


  cout<<"----------------------------------------收據----------------------------------"<<endl; 
 cout<<"====================== 車牌號:   "<<number<<endl; 
  cout<<"=========================================================="<<endl;
  cout<<"|進車場時刻 | 出車場時刻 | 停留時間 | 應付（元）|"<<endl;
 cout<<"=========================================================="<<endl;
  cout<<"    |    "<<arvtime<< "     |     "<<time_d<< "     |     "<<time_d-arvtime<< "     |     "<<money<< "     |     "<<endl;
 cout<<"---------------------------------------------------------------------------------"<<endl;
}

int main()
{
 int m=100;
 char flag;              //進入或離開的標識；
 Sstack St , Sd;    //停車場和臨時倒車場堆棧的定義；
 linkqueue   line;        //隊列的定義；
 initstack(St);        //構造停車場堆棧sting
 initstack(Sd);        //構造倒車場堆棧slinshi
 initqueue(line);          //構造便道隊列line
   
 //printf(" 請輸入停車場的容量 n:   ");
// scanf_s("%d",n);
   cout<<" ***********************************停車場管理程序************************************"<<endl<<endl;
   cout<<"================================================"<<endl;
   cout<<" **********A --- 汽車進車場;    D --- 汽車出車場 ;   E --- 退出程序 *****"<<endl;
  cout<<"================================================"<<endl<<endl;
 while(m)
 {
 
 cout<<" 請選擇 :(A,D,E): ";
   cin>>flag;
   switch(flag)
     {
     case 'A':Arv_Car(St,line);break;        //汽車進車場
     case 'D':depart_car(St,Sd,line);break; //汽車出車場
     case 'E': return 0;
     }
     m--;
 }


}