#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#define OK 1
#define NULL 0
#define ERROR 0
#define OVERFLOW 0
#define STACK_INIT_SIZE 2 //停車場大小

typedef struct{
	char AorD;       //表示車到達或離去的信息  
	char num[10];    //表示車的車牌號碼
	int time;        //表示車到達或離開的時間
}ElemType;
typedef struct{      //定義棧的結構體
	ElemType *base;  //在棧構造之前和銷毀之后，base的值為null
	ElemType *top;   //棧頂指針
	int stacksize;   //當前已分配的存儲空間
}SqStack;
typedef struct QNode{  
	ElemType cardata;
	struct QNode *next;
}QNode,*Queueptr;
typedef struct{      //定義隊的結構體
	Queueptr front;  //隊頭指針
	Queueptr rear;   //隊尾指針
}LinkQueue;

unsigned InitStack(SqStack &s){//構造一個空棧
	s.base=(ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
	if(!s.base)exit(OVERFLOW);  //存儲分配失敗
	s.top=s.base;
	s.stacksize=STACK_INIT_SIZE;
	return OK;
}//InitStack
unsigned Push(SqStack &s,ElemType e){//插入元素e為新的棧頂元素
	*s.top++=e;
	return OK;
}//Push
unsigned pop(SqStack &s,ElemType &e){//若棧不空，則刪除S的棧頂元素，用e返回其值并返回OK;否則返回ERROR;
	if(s.top==s.base)return ERROR;
	e=*--s.top;
	return OK;
}//pop
void Delete(SqStack &s,ElemType e){//若棧不空，則刪除S中元素為e的元素
	ElemType m[20],n,g;
	int a,i=0;
	while(s.base!=s.top){
        g=*--s.top;
		s.top++;
		if(strcmp(g.num,e.num)==0)
			pop(s,n);
		else
			pop(s,m[i++]);
		    
	}
	for(a=0;a<i;a++)
		Push(s,m[a]);
}
unsigned FullStack(SqStack s){//判斷棧是否滿
	if(s.top-s.base>=s.stacksize)
		return OK;
	else 
		return ERROR;
}//FullStack
unsigned InitQueue(LinkQueue &Q){//構造一個空隊列
	Q.front=Q.rear=(Queueptr)malloc(sizeof(QNode));
	if(!Q.front)exit(OVERFLOW);
	Q.front->next=NULL;
	return OK;
}//InitQueue
unsigned EnQueue(LinkQueue &Q,ElemType e){//插入元素e為Q的新的隊尾元素
	Queueptr p;
	p=new QNode;
	if(!p)exit(OVERFLOW);
	p->cardata=e;
	p->next=NULL;
	Q.rear->next=p;
	Q.rear=p;
	return OK;
}//EnQueue
unsigned EmptyQueue(LinkQueue Q){//判斷隊列是否為空
	if(Q.front==Q.rear)
		return OK;
	else
		return ERROR;
}//EmptyQueue
unsigned DeQueue(LinkQueue &Q,ElemType &e){//若隊列不空，則刪除Q的對頭元素,并用e返回其值
	Queueptr p;
	if(!EmptyQueue(Q))
	{
	    p=Q.front->next;
	    e=p->cardata;
	    Q.front->next=p->next;
	    if(Q.rear==p)
		  Q.rear=Q.front;
	      free(p);
	      return OK;
	}
   else
	  return ERROR;
}//DeQueue
unsigned SeekStack(SqStack s,ElemType e,ElemType &m){//查找棧中是否和e有相同號碼的這個元素，若有則返回OK,否則返回ERROR,并用m返回這個元素
	while(s.top!=s.base){
		m=*(--s.top);
		if(strcmp(m.num,e.num)==0)
			return OK;
	}
	return ERROR;
}//SeekStack
void StackTrverse(SqStack s){//輸出棧中的元素
		ElemType m;
	while(s.top!=s.base){
		m=*(--s.top);
		printf(" %s           %d\n",m.num,m.time);
	}
}
unsigned SeekQueue(LinkQueue &Q,ElemType e,ElemType &n){//查找隊中是否有和e相同號碼的這個元素，若有則返回OK,否則返回ERROR,并用n返回這個元素
	Queueptr p,q;
	p=Q.front;
	while(p->next){
		if(strcmp(p->next->cardata.num,e.num)==0){
			n=p->next->cardata;
			q=p->next;
            p->next=q->next;
			free(q);
			return OK;
		}
		else
			p=p->next;
	}
	return ERROR;
}//SeekQueue
void QueueTrverse(LinkQueue Q){//輸出隊列中的元素
    Queueptr p;
	p=Q.front;
	while(p->next){
		printf(" %s           %d\n",p->next->cardata.num,p->next->cardata.time);
		p=p->next;
	}
}
void main(){//主函數
	int i=1,m=1,n=1,totaltime;
    ElemType e,f,g,k;
	SqStack s;
	LinkQueue Q; 
    InitStack(s);
	InitQueue(Q);
    printf("*******************停車場 管理系統******************\n");
	printf("*****車停在停車場內0.5元每分鐘，停在便道上免費******\n\n");
    printf("(A:表示ARRIVAL  D:表示DEPARTURE  E:表示END)\n");
	for(i=1;;i++)
	{
        printf("\n請輸入車輛信息:A/D/E  車牌號碼   到達/離開時間\n\n");
        fflush(stdin);
        scanf("%c%s%d",&e.AorD,&e.num,&e.time);	  
        if(e.AorD=='A')
		{
	        if(SeekStack(s,e,f))//查找棧中是否有和e相同號碼的這個元素(車)
			{
		        printf("你輸入的車牌號碼有誤(與停車場內的車有相同的)，請重新輸入:\n");
                i--;
			}
	        else{
		          if(!FullStack(s))
				  {
				     Push(s,e);
				     printf("請將車停在停車場的第%d個位置\n\n",m++);
                   printf("\n現在停車場內的車有:\n");
				     printf("車牌號碼    停入停車場的時間\n\n");
				     StackTrverse(s);
                   printf("\n現在便道上的車有:\n");
			         printf("車牌號碼    停入便道上的時間\n\n");
			         QueueTrverse(Q);
				  }
		          else{
		                 if(SeekQueue(Q,e,k))//查找隊中是否有和e相同號碼的這個元素(車)
						 {
			                 printf("你輸入的車牌號碼有誤(與便道上的車有相同的)，請重新輸入:\n");
			   	             i--;
						 }
		                 else
						 {
			                 EnQueue(Q,e);
			                 printf("停車場已滿，請將車停在便道的第%d個位置\n",n++);
			                 printf("\n現在停車場內的車有:\n");
			                 printf("車牌號碼    停入停車場的時間\n\n");
			                 StackTrverse(s);
			                 printf("\n現在便道上的車有:\n");
			                 printf("車牌號碼    停入便道上的時間\n\n");
			                 QueueTrverse(Q);
						 }
				  }
			}
		}
	    if(e.AorD=='D')
		{
			if(SeekStack(s,e,f))//查找棧中是否有和e相同號碼的這個元素(車)
			{
				Delete(s,f);
				m--;
				totaltime=e.time-f.time;
				printf("你的車在停車場內停留了%d分鐘\n", totaltime );
				printf("你應付停車費%.2f元\n\n",totaltime*0.5);

				if(!EmptyQueue(Q)){
					DeQueue(Q,g);
					g.time=e.time;
				    Push(s,g);
					m++;
					n--;
				    printf("\n現在停車場內的車有:\n");
			     	printf("車牌號碼    停入停車場的時間\n\n");
			       StackTrverse(s);
                  printf("\n現在便道上的車有:\n");
			       printf("車牌號碼    停入便道上的時間\n\n");
			       QueueTrverse(Q);
				}
			}
			else
			{
				if(SeekQueue(Q,e,k)){//查找隊中是否有和e相同號碼的這個元素(車)
		        totaltime=e.time-k.time;
				printf("你的車在便道上停留了%d分鐘\n",totaltime);
				printf("你不用繳納停車費\n\n");
                n--;
				printf("\n現在停車場內的車有:\n");
				printf("車牌號碼    停入停車場的時間\n\n");
			    StackTrverse(s);
                printf("\n現在便道上的車有:\n");
			    printf("車牌號碼    停入便道上的時間\n\n");
			    QueueTrverse(Q);
				}
				else
					printf("你的輸入有誤(停車場和便道上都沒有此車),請重新輸入:\n");
			}
		}
	    if(e.AorD=='E')
		{
	     	printf("輸入結束,請按任意鍵結束.\n");
	        break;
		}
	}
}