用栈和队列实现虚拟停车场系统

学校的数据结构课程实验之一。

用到的数据结构：栈、队列

需求分析

　　设停车场内只有一个可停放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 };

Stack.h

队列类模板（链表实现，同样参考了经典教材"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 };

Queue.h

时间类（为停车场计时而设计）

 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 }

Time.h

汽车离开、到达的流程图

汽车类

 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 };

测试结果

 

时间： 2024-11-02 05:17:06

用栈和队列实现虚拟停车场系统的相关文章

数据结构实践——停车场模拟(栈和队列综合)

本文是针对数据结构基础系列网络课程(3):栈和队列的实践项目. 设停车场是一个可停放n辆汽车的狭长死胡同,南边封口,汽车只能从北边进出(这样的停车场世间少有).汽车在停车场内按车辆到达时间的先后顺序,最先到达的第一辆车停放在车场的最南端,依次向北排开.若车场内已停满n辆汽车,则后来的汽车只能在门外的候车场上等候,一旦有车开走,则排在候车场上的第一辆车即可开入.当停车场内某辆车要离开时,在它之后进入的车辆必须先退出车场为它让路(假定停车场内设有供车辆进出的便道,所有的司机也必须在车内随时待命),待

栈和队列的一个应用

    我是一个初学者,这是我的一个拙作,里面有很多不恰之处,让高手见笑了,请指教.联系我QQ 358271030.     这是用栈和队列模拟的一个停车场管理系统.进来一辆车登记后进入车场,如车场满则进来的车进入便道等候,一旦有车开走则便道自动进入车场.    用一个栈模拟停车场,用一个队列模拟车场外的便道. #include "stdio.h"#define NULL 0#define ERROR 0#define OK 1#define OVERFLOW 0#define STA

kangle虚拟主机系统easypanel使用教程

最近一直在弄有关虚拟主机管理系统,前一段时间也介绍过可以通过使用N点虚拟主机系统实现各种功能.但是,通过本人的实际操作发现,kangle的easypanel系统要比N点的强多了. 今天,我们先在这大致介绍一下kangle的easypanel在安装.使用及配置过程中需要注意的一些问题. 首先.在此我需要说明的是我现在所处的环境是windows下的,linux的环境及服务器我这边暂时没有.所有最近一段时间介绍的基本上都是windows下的操作. 我们要先到kangle的官网去下载easypanel软

迷宫求解非递归 DFS BFS(应用栈和队列)

栈和队列的应用对迷宫问题求解 没有递归 自己手动建的栈和队 并且输出路径 DFS的路径就是 栈中的坐标 BFS的路径在队又开了一个域存上一层的base值 语言还是用的C++ 感觉比C的封装性好很多 充分体会了一下DFS一边比BFS快 但是BFS是最优解而DFS可能不是最优解   #include <iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace

用PHP编程开发“虚拟域名”系统

编程 如果自己的服务器也能够实现简记域名就好了.其实这并不复杂.你也可以做一个简记域名系统. 简记域名系统的关键技术在于:实现Web页面的重定向(Redirctory).在本质上,简 记域名系统和虚拟机系统完全不同.虚拟机的虚拟域名和IP是存在一一对应关系的.而简记域名系统不需要将域名和IP做一一映射.也就是说,它根本不需要复杂的域名解析机制和虚拟机来完成,它所做的事情就是当你在请求yourname.somedomain时,将你的浏览器重新定向到你本来存放Html页面的地方. 本程序运行环境是:

数据结构――栈、队列和树(Java)

数据|数据结构 数据结构――栈.队列和树 开发者可以使用数组与链表的变体来建立更为复杂的数据结构.本节探究三种这样的数据结构:栈.队列与树.当给出算法时,出于简练,直接用Java代码. 栈 栈是这样一个数据结构,其数据项的插入和删除(获取)都只能在称为栈顶的一端完成.因为最后插入的数据项就是最先要删除的数据项,开发者往往将栈称为LILO(last-in, first-out)数据结构. 数据项压入(插入)或者弹出(删除或取得)栈顶.图13示例了一个有三个String数据项的栈,每个数据项压入栈顶

浅谈算法和数据结构 一 栈和队列

最近晚上在家里看Algorithems,4th Edition,我买的英文版,觉得这本书写的比较浅显易懂,而且"图码并茂",趁着这次机会打算好好学习做做笔记,这样也会印象深刻,这也是写这一系列文章的原因.另外普林斯顿大学在Coursera 上也有这本书同步的公开课,还有另外一门算法分析课,这门课程的作者也是这本书的作者,两门课都挺不错的. 计算机程序离不开算法和数据结构,本文简单介绍栈(Stack)和队列(Queue)的实现,.NET中与之相关的数据结构,典型应用等,希望能加深自己对这

数据结构学习(C++)之栈和队列

栈和队列是操作受限的线性表,好像每本讲数据结构的数都是这么说的.有些书按照这个思路给出了定义和实现:但是很遗憾,本文没有这样做,所以,有些书中的做法是重复建设,这或许可以用不是一个人写的这样的理由来开脱. 顺序表示的栈和队列,必须预先分配空间,并且空间大小受限,使用起来限制比较多.而且,由于限定存取位置,顺序表示的随机存取的优点就没有了,所以,链式结构应该是首选. 栈的定义和实现 #ifndef Stack_H #define Stack_H #include "List.h" tem

数据结构：栈和队列的定义和操作

一.栈和队列定义 1).栈 定义: 栈(Stack)是一个后进先出(Last in first out,LIFO)的线性表,它要求只在表尾进行删除和插入操作. 图如下: 特点: 一.栈特殊的线性表(顺序表.链表),它在操作上有一些特殊的要求和限制:栈的元素必须"后进先出". 三.栈的表尾称为栈的栈顶(top),相应的表头称为栈底(bottom) 二.栈的操作只能在这个线性表的表尾进行. 2).队列 定义: 队列是限定只能在表的一端进行插入,在表的另一端进行删除的特殊的线性表. 图如下: