学校的数据结构课程实验之一。
用到的数据结构：栈、队列
需求分析
设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序依次排列。
若车场内已停满n辆汽车，则后来的汽车只能在门外便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，该车开出后，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开时必须按它停留的时间长短交纳费用。
数据要求
要求模拟停车场车辆的管理，按照从终端读入的输入数据序列进行模拟管理。
每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。
主函数流程图
主函数：
1 #include <iostream> 2 #include <string> 3 #include "Stack.h" 4 #include "Queue.h" 5 #include "Time.h" 6 #include "Parking.h" 7 using namespace std; 8 int main() 9 { 10 Parking parking; 11 cout<<"输入示例"<<endl<<"到达：A 京C001 9:40"<<endl<<"离开：D 京B984 10:25"; 12 char choice='y'; 13 while(choice == 'y') 14 { 15 cout<<endl<<"请输入事件："<<endl; 16 fflush(stdin); 17 char action; 18 string num; 19 Time timing; 20 cin>>action>>num>>timing;//读入事件 21 if(action == 'A') 22 { 23 parking.park(num, timing); 24 } 25 else if(action == 'D') 26 { 27 parking.leave(num,timing); 28 } 29 cout<<endl<<"继续吗[y/n]？"; 30 cin>>choice; 31 } 32 return 0; 33 }
栈类模板（数组实现，同样参考了经典教材"Data Structures and Program Design in C++" Robert L. Kruse, Alexander J. Ryba 高等教育出版社-影印版）
1 const int maxStack=3;//最多元素个数 2 enum Error_code 3 { 4 success, underflow, overflow 5 }; 6 7 template <class Stack_entry> 8 class Stack 9 { 10 private: 11 unsigned int count;//记录栈内元素个数 12 Stack_entry entry[maxStack];//数组实现 13 public: 14 Stack() 15 { 16 count=0; 17 } 18 bool empty() const 19 { 20 if(count==0) return true; 21 else return false; 22 } 23 bool full() const 24 { 25 if(count==maxStack) return true; 26 else return false; 27 } 28 Error_code pop() 29 { 30 if(count==0) return underflow; 31 else 32 { 33 --count; 34 return success; 35 } 36 } 37 Error_code top(Stack_entry &item) const//取栈顶元素 38 { 39 if(count==0) return underflow; 40 else 41 { 42 item=entry[count-1]; 43 return success; 44 } 45 } 46 Error_code push(Stack_entry &item) 47 { 48 if(count >= maxStack) return overflow; 49 else 50 { 51 entry[count++]=item; 52 item.position = count;//返回停车位置，从1开始记 53 return success; 54 } 55 } 56 };
队列类模板（链表实现，同样参考了经典教材"Data Structures and Program Design in C++" Robert L. Kruse, Alexander J. Ryba 高等教育出版社-影印版）
1 template<class Node_entry>//链队列结点定义（单链表） 2 struct Node 3 { 4 //数据成员 5 Node_entry entry; 6 Node<Node_entry> *next; 7 8 //构造函数 9 Node(){} 10 Node(Node_entry new_entry, Node<Node_entry> *new_next=NULL) 11 :entry(new_entry), next(new_next){} 12 }; 13 14 template<class Queue_entry> 15 class Queue 16 { 17 public: 18 unsigned int count;//结点个数 19 Node<Queue_entry> *front, *rear;//队列头、尾结点 20 21 Queue()//构造函数 22 { 23 count=0; 24 front=rear=NULL; 25 } 26 bool empty() const 27 { 28 if(count==0) return true; 29 else return false; 30 } 31 Error_code serve() 32 { 33 if(count==0) return underflow; 34 else 35 { 36 Node<Queue_entry> *out=front; 37 front=front->next; 38 if(front==NULL) rear=NULL; 39 delete out; 40 count--; 41 return success; 42 } 43 } 44 Error_code retrieve(Queue_entry &item) const//取队列头元素 45 { 46 if(count==0) return underflow; 47 else 48 { 49 item=front->entry;//解引用 50 return success; 51 } 52 } 53 Error_code append(const Queue_entry &item) 54 { 55 Node<Queue_entry> *in=new Node<Queue_entry>(item); 56 if(in==NULL) return overflow; 57 if (count == 0) 58 { 59 front=rear=in; 60 } 61 else 62 { 63 rear->next=in; 64 rear=in;; 65 } 66 count++; 67 return success; 68 } 69 };
时间类（为停车场计时而设计）
1 #include <iostream> 2 using namespace std; 3 class Time 4 { 5 private: 6 unsigned short hour; 7 unsigned short minute; 8 public: 9 Time(){ hour = 0; minute = 0; }//默认构造函数 10 Time(unsigned short h, unsigned short m):hour(h),minute(m){}//构造函数 11 int HowManyMinutes(const Time &time)//计算时间间隔 12 { 13 return time-*this; 14 } 15 Time& operator=(const Time &t) 16 { 17 hour = t.hour; 18 minute = t.minute; 19 return *this; 20 } 21 friend int operator-(const Time &t1, const Time &t2);//重载相减运算符 22 friend istream &operator>>(istream &is, Time &t); 23 friend ostream &operator<<(ostream &os, Time &t); 24 }; 25 26 int operator-(const Time &t1, const Time &t2)//重载相减运算符 27 { 28 int dur=0; 29 if(t1.minute < t2.minute) 30 { 31 dur = t1.minute+60-t2.minute; 32 dur += 60*(t1.hour-1-t2.hour); 33 } 34 else 35 { 36 dur = t1.minute - t2.minute; 37 dur += 60*(t1.hour - t2.hour); 38 } 39 return dur; 40 } 41 istream &operator>>(istream &is, Time &t) 42 { 43 char sem; 44 is >> t.hour >> sem >> t.minute; 45 return is; 46 } 47 ostream &operator<<(ostream &os, Time &t)//此处不能加const 48 { 49 os << t.hour << ':' << t.minute; 50 return os; 51 }
汽车离开、到达的流程图
汽车类
1 struct Car 2 { 3 string num;//车牌号 4 Time arrTime;//到达时间（未必立即停入车位） 5 Time inTime;//停入车位的时间 6 short position;//停入的车位，0为便道，栈底为1 7 Time depTime;//离开时间 8 //构造函数 9 Car(){} 10 Car(string n, Time a):num(n),arrTime(a){} 11 void CheckOut()//离开时的结算 12 { 13 cout<<"停留时间为"<<depTime - arrTime<<"分钟"<<endl;//停留时间 14 cout << "到达时间" << arrTime << endl; 15 cout << "离开时间" << depTime << endl; 16 cout << "停入时间" << inTime << endl; 17 cout << "应交纳停车费 " << (depTime - inTime) * 2 << "元"; 18 } 19 void CheckIn() 20 { 21 cout << "到达时间为" << arrTime << endl; 22 cout << "进入停车场时间为" << inTime<<endl; 23 cout << "停入的位置为#" << position; 24 } 25 };
停车场类
1 enum Status 2 { 3 succeed, fail 4 }; 5 6 class Parking 7 { 8 private: 9 Stack<Car> parkStack;//停车栈 10 Stack<Car> tempStack;//临时栈 11 Queue<Car> waitingQueue;//便道 12 public: 13 Status park(string num, Time arr) 14 { 15 Car *new_car = new Car(num, arr); 16 if (parkStack.full())//栈满，入便道 17 { 18 waitingQueue.append(*new_car); 19 new_car->position = 0; 20 cout << "停车场已满，进入便道"; 21 } 22 else//栈未满，入栈 23 { 24 new_car->inTime = arr;//到达即入栈 25 parkStack.push(*new_car); 26 new_car->CheckIn(); 27 } 28 return succeed; 29 } 30 Status leave(string num, Time dep) 31 { 32 Car *currentCar= new Car(); 33 parkStack.top(*currentCar); 34 while(currentCar->num != num)//遍历栈以找到要离开的车 35 { 36 tempStack.push(*currentCar);//前面的车退出到临时栈 37 parkStack.pop(); 38 parkStack.top(*currentCar); 39 } 40 //找到了要离开的那辆车 41 currentCar->depTime = dep;//登记离开时间 42 currentCar->CheckOut();//结账，打印账单 43 parkStack.pop();//该车出栈 44 //临时栈中的车依次放回停车栈 45 while (!tempStack.empty()) 46 { 47 tempStack.top(*currentCar); 48 parkStack.push(*currentCar); 49 tempStack.pop(); 50 } 51 if(!waitingQueue.empty())//便道不空，队头入栈 52 { 53 waitingQueue.retrieve(*currentCar); 54 waitingQueue.serve(); 55 parkStack.push(*currentCar); 56 currentCar->inTime = dep;//上一辆车离开的时间就是这一辆的入栈时间 57 cout <<endl<< "车辆" << currentCar->num << "已从便道开入停车场" << endl; 58 currentCar->CheckIn(); 59 } 60 return succeed; 61 } 62 };
测试结果
