问题描述
设停车场是一个可停放 n 辆汽车的狭长通道,且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序,依次由北向南排列(大门在最南端,最先到达的第一辆车停放在车场的最北端),若车场内已停满 n 辆汽车,则后来的汽车只能在门外的便道上等候,一旦有车开走,则排在便道上的第一辆车即可开入;当停车场内某辆车要离开时,在它之后进入的车辆必须先退出车场为它让路,待该辆车开出大门外,其他车辆再按原次序进入车场,每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。
基本要求
以栈模拟停车场,以队列模拟车场外的便道,按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项:汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为:若是车辆到达,则输出汽车在停车场内或便道上的停车位置;若是车辆离去,则输出汽车在停车场内停留的时间和应交纳的费用(在便道上停留的时间不收费)。
测试用例(举例)
设n = 2,输入数据为:(‘A’,1,5),(‘A’,2,10),(‘D’,1,15),(‘A’,3,20),(‘A’,4,25),(‘A’,5,30),(‘D’,2,35),(‘D’,4,40),(‘E’,0,0)。其中:‘A’表示车辆到达;‘D’表示车辆离去;‘E’表示输入结束。
要求用栈和队列实现,根据题目要求,当停车场内某辆车要离开时,在它之后进入停车场的车都必须先退出停车场为它让路,待其开出停车场后,这些辆再依原来的次序进场的功能,就可以设计两个栈,其中一个栈用来模拟停车场,另一个栈用来模拟临时停车场。停车场有车出来,让路的车进入模拟停车场,然后再由模拟停车场进入停车场。超过停车场容量的车停入便道,便道用队列模拟。
本代码的栈和队列都是用的顺序结构。
1 #include<iostream>
2 using namespace std;
3
4 class node { //节点类
5 public:
6 int num;
7 int time;
8 };
9 class AStack :public node { //栈类
10 private:
11 int size;
12 int top;
13 node *listArray;
14 public:
15 AStack(int sz) {
16 size = sz;top = 0;listArray = new node[sz];
17 }
18 ~AStack() { delete[] listArray; };
19 bool push(node a) {
20 if (top == size) return false;
21 listArray[top++]=a;
22 return true;
23 }
24 bool pop(node &a) {
25 if (top == 0) return false;
26 else {
27 a=listArray[--top];return true;
28 }
29 }
30 int length() {
31 return top;
32 }
33 bool topValue(node &a) {
34 if (top == 0)return false;
35 a = listArray[top - 1];
36 return true;
37 }
38 };
39 class AQueue :public node { //队列类
40 private:
41 int size;
42 int front;
43 int rear;
44 node *listArray;
45 public:
46 AQueue(int sz) {
47 size = sz + 1;
48 rear = 0;front = 1;
49 listArray = new node[size];
50 }
51 ~AQueue() { delete[] listArray; };
52 bool enqueue(node it) {
53 if (((rear + 2) % size) == front)return false;
54 rear = (rear + 1) % size;
55 listArray[rear] = it;
56 return true;
57 }
58 bool dequeue(node &it) {
59 if (length() == 0) return false;
60 it = listArray[front];
61 front = (front + 1) % size;
62 return true;
63 }
64 int length() {
65 return ((rear + size) - front + 1) % size;
66 }
67 };
68 void input(AStack &parking1, AQueue &wait,node s) { //进停车场
69 if (parking1.push(s)) {
70 cout << "在停车场第" <<parking1.length()<<"位"<< endl;
71 return;
72 }
73 else {
74 cout << "在便道第" << wait.length()+1 << "位" << endl;
75 wait.enqueue(s);
76 }
77 }
78 int output(AStack &parking1, AStack &parking2,AQueue &wait, node s) { //出停车场
79 node temp;int time;
80 while ((parking1.topValue(temp))&&(temp.num!=s.num)) {
81 parking1.pop(temp);
82 parking2.push(temp);
83 }
84 if (parking1.topValue(temp)) { //判断该车是否存在于停车场中
85 parking1.pop(temp);
86 time = s.time - temp.time;
87 }
88 else time = -1;
89 while (parking2.pop(temp))
90 parking1.push(temp);
91 if (time) {
92 if (wait.length()) {
93 wait.dequeue(temp);
94 temp.time = s.time;
95 parking1.push(temp);
96 }
97 }
98 return time;
99 }
100 int main() {
101 cout << "请输入停车场容量和每分钟的停车费:" << endl;
102 int maxSize, money,parkTime;
103 cin >> maxSize >> money;
104 AStack parking1(maxSize), parking2(maxSize);
105 AQueue wait(100);
106 char a; node s;
107 while (1) {
108 cout << "输入命令:" << endl;
109 cin >> a >> s.num >> s.time;
110 while (!((a == 'A' || a == 'D' || a == 'E') && s.num >= 0 && s.time >= 0)){
111 cout << "输入错误请重新输入:" << endl;
112 cin >> a >> s.num >> s.time;
113 };
114 if (a == 'E') break;
115 else if (a == 'A') {
116 input(parking1, wait,s);
117 continue;
118 }
119 else {
120 parkTime = output(parking1, parking2,wait,s);
121 if (parkTime == -1)
122 cout << "该车不在本停车场,请重新输入!" << endl;
123 else
124 cout << "停车时间为:" << parkTime << ends << "应缴纳费用为:" << parkTime*money << endl;
125 }
126 }
127 system("pause");
128 return 0;
129 }