实验二 栈和队列
- 掌握栈和队列的逻辑结构定义和各种存储结构的实现。
- 熟练运用栈和队列的各种存储结构以及各种基本操作。
- 根据实际问题的需要，选择栈和队列适合的存储结构解决问题。
- 定义一个结构体，描述停车场中车辆的信息。车辆信息包括：车牌号（8 个字符）、进场时间（年、月、日、时、分、秒）。用描述车辆信息的结构体作为栈的数据元素类型测试顺序栈的实现。
- 修改顺序栈的入栈成员函数 push（x），要求当栈满时，执行私有成员函数 stackfull()进行栈满处理。其功能是：动态创建一个比原来的栈数组大一倍的新数组，代替原来的栈数组，原来栈数组中的元素占据新数组的前半部分的位置。
- 定义一个结构体，描述停车场中车辆的信息。车辆信息包括：车牌号（8 个字符）、进场时间（年、月、日、时、分、秒）。用描述车辆信息的结构体作为栈的数据元素类型测试链式栈的实现。
- 修改链式栈模板类，用带头结点的单链表作为栈的存储结构。
- 修改教材中循环队列模板类，把成员数据 rear 改为 length 表示队列长度，并完成各成员函数的修改。
- 修改教材中循环队列模板类，增加成员数据 tag，原有成员数据不变，改变队空和队满的判断条件为：
front == rear && tag == 0表示队空；front == rear && tag == 1表示队满，并完成各成员函数的修改。
- 定义一个结构体，描述航空订票系统中的航班信息。航班信息包括：航班号、起飞时间（年、月、日、时、分、秒）、起飞地点（8 个字符）、抵达时间（年、月、日、时、分、秒）、抵达地点（8 个字符）、座位数、空位数、票价等。用描述航班信息的结构体作为队列的数据元素类型测试链队列的实现。
- 修改教材中的链队列模板类，用一个不带头结点的单循环链表来表示队列（也称为循环链队列），其中只设一个队尾指针 rear，不设队头指针，队尾指针 rear 指向队尾元素结点。
根据教材介绍的 2 个顺序栈共享存储空间的内容。设计相应的类模板，并实现所定义的成员函数。其中，入栈操作 push（k，e）有两个参数，其中 k（取 1 或 2）表示入栈的编号，e 表示入栈的元素；出栈操作 pop（k，e）有两个参数，其中 k（取 1 或 2）表示出栈的编号，e 表示出栈的元素；其他成员函数也作相应修改，需要用参数指明所操作栈的编号。
所谓双端队列就是在两个端点（队头和队尾）都可以进行插入和删除的队列。设计相应的类模板，并实现所定义的成员函数（具体成员函数参照一般队列）。其中，入队操作EnQueue（k，e）有两个参数，其中 k 表示入队的位置（取 0 或 1；0 表示在队头入队，1 表示在队尾入队），e 表示入栈的元素；出队操作 DelQueue（k，e）有两个参数，其中k 表示出队位置（含义同入队操作），e 表示出队的元素；其他成员函数也作相应修改，需要用参数指明所操作的位置。
设计一个团队队列的类模板。在团队队列中每个元素属于一个团队，同一团队中的元素在队列中的位置是连续排列的。当一个元素入队时，如果队列中已经有它同团队的元素，则该元素入队并排在它所在团队的最后；否则把该元素排在整个队列的最后。出队操作同一般队列一样，把整个队列的队头元素出队列。构造团体队列时需要指出团队的数目 n，团队编号从 0 到 n-1。入队时需要两个参数，其一表示入队元素值，其二表示所在团队编号。
设停车场内只有一个可停放 n 辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满 n 辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为该停车场编制模拟程序进行管理。
以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括 3 个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据执行如下操作：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表实现。
例如：设 n＝2，输入数据为：（＇A＇，1,5），（＇A＇，2,10），（＇D＇，115），（＇A＇，3，20），（＇A＇，4,25），（＇A＇， 5， 30），（＇D＇， 2， 35），（＇D＇， 4， 40）， （＇E＇，0,0）。每一组输入数据包括 3 个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，＇A＇表示到达，＇D＇表示离去，＇E＇表示输入结束。
- 两个栈共享空间，思考应开辟数组的空间是多少。
- 汽车可以有不同种类，则它们的占地面积不同，收费标准也不同，如 1 辆客车和1.5 辆小汽车的占地面积相同，1 辆十轮卡车占地面积相当于 3 辆小汽车的占地面积。
- 汽车可以直接从便道上开走，此时排在它前面的汽车要先开走让路，然后再依次排到队尾。
- 停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修改结构以满足这种要求。
有一个“丁”字型铁路调度系统，它由相互垂直的 2 条铁轨组成，水平方向的为主铁轨，竖直方向的为辅助铁轨。辅助铁轨用于对车厢次序进行调整，它在主铁轨中间，把主铁轨分成左、右两部分。主铁轨左边的车厢只能从左边开到右边；或者从主铁轨左边进入辅助铁轨；辅助铁轨上的车厢只可以进入主铁轨右边。现在有 n 节火车车厢，编号为 1、2、…、n，在主铁轨的左边以任意的顺序排列，要求通过这个调度系统，在主铁轨的右边以 1、2、…、n 的次序开出（例如：有 5 节车厢以5、3、1、2、4 的次序进入，要求以 1、2、3、4、5 的顺序出站）。请编程求解调度过程。
输入共 2 行，第 1 行一个正整数 n 表示车厢数目；第 2 行是 1-n 的任意排列，表示 n节车厢在主铁轨左边的排列顺序。
如果能完成调度，则输出调度过程，否则输出调度失败信息。
随着银行业务量的快速发展，银行柜台业务承受的压力越来越大，排队等待现象屡见不鲜，银行排长队现象成为困扰银行和用户的难题。为了解决这一难题，目前大部分银行的营业厅都使用了取号系统来改善银行窗口排长队的现象，提高银行的服务效率。本题目要求实现银行排队模拟系统，模拟银行取号排队的整个过程，系统功能包括：取号、排队、服务及管理等。取号：客户进入银行首先从系统的取号机获取客户编号，包括：客户编号、客户类型（企业客户、VIP 客户、普通客户）、到达时间（年、月、日、时、分、秒）等。
排队：客户获取客户编号后，如果服务窗口空闲，就直接去办理业务，否则进入大厅等待。
服务：当服务窗口完成一笔业务后，如果有客户在大厅等待，就根据其到达时间的先后顺序让最先到的客户办理业务。
管理：能根据需要统计服务窗口办理的业务数、统计客户的等待时间、业务办理时间等。
系统中设一个服务窗口，不区分客户类型，完成银行排队模拟系统的实现，能进行取号、排队、服务、管理等操作。
系统提供一个菜单，让操作员选择不同的功能，进行不同的操作，能显示在大厅等待的客户信息、已经在服务窗口办完业务的客户信息。
- 在系统中设置多个服务窗口进行工作。
- 设置服务窗口的类型（企业客户窗口、VIP 客户窗口、普通客户窗口），分别为 不同的客户人群服务。
- 设置大厅座位数，当大厅坐满时，再进来的客户只能在过道里等待，大厅有空位 时先到过道里等待的客户再进大厅等待。