struct Stack{
    ElemType  *stack ;    // 存栈元素
    int  top;                // 栈顶指示器
    int MaxSize;            // 栈的最大长度
};
void InitStack (Stack &S)    //构造一个空栈 S
{
  S.MaxSize=10;
  S.stack=new ElemType[S.MaxSize];
  if(!S.stack){
    cerr<<"fail"<<endl;
    exit(1);
  }
  S.top=-1;
}

int EmptyStack (Stack S)   //若栈S为空栈返回1，否则返回0
{
  return S.top==-1;
}

void Push(Stack &S, ElemType item)   //元素 item进栈
{
  if(S.top==S.MaxSize-1){
    int k=sizeof(ElemType);
    S.stack=(ElemType*)realloc(S.stack,2*S.MaxSize*k);
    S.MaxSize=2*S.MaxSize;
  }
  S.top++;
  S.stack[S.top]=item;
}

ElemType Pop(Stack &S)    //栈S的栈顶元素出栈并返回
{
  if(S.top==-1){
    cerr<<"Stack is empty!"<<endl;
    exit(1);
  }
  S.top--;
  return S.stack[S.top+1];
}

ElemType Peek(Stack S)   //取栈S的当前栈顶元素并返回
{
  if(S.top==-1){
    cerr<<"Stack is empty!"<<endl;
    exit(1);
  }
  return S.stack[S.top];
}

void ClearStack (Stack &S)   //清除栈s，使成为空栈
{
  if(S.stack){
    delete []S.stack;
    S.stack=0;
  }
  S.top=-1;
  S.MaxSize=0;
}

struct LNode{
  ElemType data;
  LNode* next;
};
struct LinkQueue{
  LNode* front;
  LNode* rear;
};

void InitQueue(LinkQueue &HQ)
{
  HQ.front=HQ.rear=NULL;
}

bool EmptyQueue (LinkQueue &HQ)
{
  return HQ.front==NULL;
}

void EnQueue (LinkQueue &HQ, ElemType item)
{
  LNode* newptr=new LNode;
  newptr->data=item;
  newptr->next=NULL;
  if(HQ.rear==NULL)
    HQ.front=HQ.rear=newptr;
  else
    HQ.rear=HQ.rear->next=newptr;
}

ElemType OutQueue (LinkQueue &HQ)
{
  if(HQ.front==NULL){
    cerr<<"queue is empty!"<<endl;
    exit(1);
  }
  ElemType temp=HQ.front->data;
  LNode* p=HQ.front;
  HQ.front=p->next;
  if(HQ.front==NULL)
    HQ.rear=NULL;
  delete p;
  return temp;
}

ElemType PeekQueue (LinkQueue &HQ)
{
  if(HQ.front==NULL){
    cerr<<"queue is empty!"<<endl;
    exit(1);
  }
  return HQ.front->data;
}

void ClearQueue (LinkQueue &HQ)
{
  LNode* p=HQ.front;
  while(p!=NULL){
    HQ.front=HQ.front->next;
    delete p;
    p=HQ.front;
  }
  HQ.rear=NULL;
}

#include<stdio.h>
#include<iostream.h>
#include<stdlib.h>
typedef struct{
  int num;  //汽车牌照号码
  int time;   //进入停车场的时刻
} ElemType;  //栈与队列中元素的数据类型
#include"test9_stack.h"
#include"test9_queue.h"
void main()
{
  ElemType  x, y;
  char flag;
  int n,fee;
  Stack parking,temp;
  LinkQueue path;
  InitStack(parking);
  InitStack(temp);
  InitQueue(path);
  cout<<"请输入停车场的停车位个数：";
  cin>>n;
  cout<<"请输入每小时的停车费用（元/小时）：";
  cin>>fee;
  cout<<"请输入车辆情况(A: 到达  D: 离开  E: 结束) ，车牌号码，时间"<<endl;
  cin>>flag>>x.num>>x.time;
  while (flag!='E'){
    if (flag=='A'){ //进栈或进队列，并输出汽车的停车位置
      if(parking.top==n-1){
        EnQueue(path,x);
        cout<<"停车场车位已满，该车已停入过道"<<endl;
      }
      else{
        Push(parking,x);
        cout<<"该车停在"<<parking.top<<"号停车位"<<endl;
      }
    }
    else if (flag=='D'){
      y=Pop(parking);//出栈，并输出在车场内停留的时间和应交纳的费用
      while(y.num!=x.num){
        Push(temp,y);
        y=Pop(parking);
      }
      cout<<"该车在停车场内停留了"<<x.time-y.time<<"小时，需付费："<<fee*(x.time-y.time)<<"元"<<endl;
      while(!EmptyStack(temp))
        Push(parking,Pop(temp));
      if(!EmptyQueue(path)){  //若队列非空，则队头元素出队列（便道）并入栈（停车场）
        Push(parking,OutQueue(path));
        cout<<parking.top<<"号车位有空，过道中的第一辆车已停入该车位"<<endl;
      }
    }
    else     //打印出错信息，提示重新输入
      cout<<"输入错误，请重试！"<<endl;
    cout<<"请输入车辆情况(A: 到达  D: 离开  E: 结束) ，车牌号码，时间"<<endl;
    cin>>flag>>x.num>>x.time;
  }
  ClearStack(parking);
  ClearStack(temp);
  ClearQueue(path);
}

#include<stdio.h>
#include<iostream.h>
#include<stdlib.h>
typedef struct{
  int num;  //汽车牌照号码
  int time;   //进入停车场的时刻
} ElemType;  //栈与队列中元素的数据类型
#include"test9_stack.h"
#include"test9_queue.h"
void main()
{
  ElemType  x, y;
  char flag;
  int n,fee;
  Stack parking,temp;
  LinkQueue path,temp_Q;
  InitStack(parking);
  InitStack(temp);
  InitQueue(path);
  InitQueue(temp_Q);
  cout<<"请输入停车场的停车位个数：";
  cin>>n;
  cout<<"请输入停车场内每小时的停车费用（元/小时），过道内的停车费用为半价，费用不分开计算，以出来时所处位置为准：";
  cin>>fee;
  cout<<"请输入车辆情况(A: 到达  D: 离开  E: 结束) ，车牌号码，时间"<<endl;
  cin>>flag>>x.num>>x.time;
  while (flag!='E'){
    if (flag=='A'){ //进栈或进队列，并输出汽车的停车位置
      if(parking.top==n-1){
        EnQueue(path,x);
        cout<<"停车场车位已满，该车已停入过道"<<endl;
      }
      else{
        Push(parking,x);
        cout<<"该车停在"<<parking.top<<"号停车位"<<endl;
      }
    }
    else if (flag=='D'){//出栈，并输出在车场内停留的时间和应交纳的费用
      while(!EmptyStack(parking)){
        y=Pop(parking);
        Push(temp,y);
        if(x.num==y.num){
          cout<<"该车在停车场内停留了"<<x.time-y.time<<"小时，需付费："<<fee*(x.time-y.time)<<"元"<<endl;
              Pop(temp);
              while(!EmptyStack(temp))
            Push(parking,Pop(temp));
          if(!EmptyQueue(path)){  //若队列非空，则队头元素出队列（便道）并入栈（停车场）
            Push(parking,OutQueue(path));
            cout<<parking.top<<"号车位有空，过道中的第一辆车已停入该车位"<<endl;
          }          
          break;
        }
      }
      if(temp.top==n-1){ //在停车场内找不到该车，进入过道内查找
          while(!EmptyStack(temp))
          Push(parking,Pop(temp));
        if(!EmptyQueue(path)){
          while(!EmptyQueue(path)){
            y=OutQueue(path);
            if(x.num==y.num){
              cout<<"该车在过道内停留了"<<x.time-y.time<<"小时，需付费："<<0.5*fee*(x.time-y.time)<<"元"<<endl;
              continue;
            }
            EnQueue(temp_Q,y);
          }
          while(!EmptyQueue(temp_Q))
            EnQueue(path,OutQueue(temp_Q));
        }
      }
    }
    else     //打印出错信息，提示重新输入
      cout<<"输入错误，请重试！"<<endl;
    cout<<"请输入车辆情况(A: 到达  D: 离开  E: 结束) ，车牌号码，时间"<<endl;
    cin>>flag>>x.num>>x.time;
  }
  ClearStack(parking);
  ClearStack(temp);
  ClearQueue(path);
  ClearQueue(temp_Q);
}