DS博客作业03--栈和队列

目录

• 1.本周学习总结
• 2.PTA实验作业
• 2.1 题目1：jmu-报数游戏
  • 2.1.1设计思路
  • 2.1.2代码截图
  • 2.1.3本题PTA提交列表说明
• 2.2 题目2：银行排队问题之单队列多窗口服务
  • 2.2.1设计思路
  • 2.2.2代码截图
  • 2.2.3本题PTA提交列表说明
• 2.3 题目3：符号配对
  • 2.3.1设计思路
  • 2.3.2代码截图
  • 2.3.3本题PTA提交列表说明
• 2.4 题目4：银行排队问题之单窗口“夹塞”版
  • 2.4.1设计思路
  • 2.4.2代码截图
  • 2.4.3本题PTA提交列表说明
• 3、栈和队列上机考试
  • 列车调度
    • 我的错误做法：
    • 改进后的正确做法：
  • 表达式求解
    • 我的错误做法：
    • 改进后的正确做法：

1.本周学习总结

越发深入学习C++后，发现里面有的容器是越发好用，很多时候都不用自己去编写STL中容器类型的数据，而且有的容器查找数据的话也特别快，对于不善于排序法的我可谓是非常的福利了。但是有的时候题目又比较刁钻，你不能直接套用容器，需要特殊定制一下，又或者使用容器查找效率还是太慢，这就需要另寻一种骚套路了。所以这一章的学习可谓是欢喜参半吧。

2.PTA实验作业

2.1 题目1：jmu-报数游戏

报数游戏是这样的：有n个人围成一圈，按顺序从1到n编好号。从第一个人开始报数，报到m（m<n）的人退出圈子；下一个人从1开始报数，报到m的人退出圈子。如此下去，直到留下最后一个人。其中n是初始人数；m是游戏规定的退出位次（保证为小于n的正整数）。要求用队列结构完成。输出数字间以空格分隔，但结尾不能有多余空格。

输入样例1：

5 3

输出样例1：

3 1 5 2 4

输入样例2：

3 5

输出样例2：

error!

2.1.1设计思路

利用for循环，循环m次，踢一个人，知道队列里面没有人为止。虽然说起来很简单，但是一开始我也没想到可以这么做，可以说也是很巧妙地利用了for循环的特点

2.1.2代码截图

2.1.3本题PTA提交列表说明

WA:看漏了题目m>n的情况，找了好久。。。坏习惯什么时候能改呢

2.2 题目2：银行排队问题之单队列多窗口服务

假设银行有K个窗口提供服务，窗口前设一条黄线，所有顾客按到达时间在黄线后排成一条长龙。当有窗口空闲时，下一位顾客即去该窗口处理事务。当有多个窗口可选择时，假设顾客总是选择编号最小的窗口。
本题要求输出前来等待服务的N位顾客的平均等待时间、最长等待时间、最后完成时间，并且统计每个窗口服务了多少名顾客。

输入样例：

9
0 20
1 15
1 61
2 10
10 5
10 3
30 18
31 25
31 2
3

输出样例：

6.2 17 61
5 3 1

2.2.1设计思路

将重心放在顾客的到达时间和窗口最早的空闲时间上面

1. 如果窗口的最早空闲时间小于顾客到达时间说明这个窗口在顾客到达时是可用的，把顾客安排进去，并且把窗口的最早空闲时间更新为顾客到达时间加上办理所需时间
2. 如果所有的窗口在顾客到达时都是不可用的，那么就取里面最快结束的窗口，将窗口的最快空闲时间加上顾客办理时间，也就是说这个窗口办理完上个顾客，就马上来办理当前顾客的业务
3. 过程中记录等待时间数据，统计，方便最后输出

2.2.2代码截图

2.2.3本题PTA提交列表说明

WA:这里的错误是因为我最大等待时间初始化为-1了。。应该初始化为0的，不应该存在负数情况

2.3 题目3：符号配对

请编写程序检查C语言源程序中下列符号是否配对：/与/、(与)、[与]、{与}。

输入样例1：

void test()
{int i, A[10];for (i=0; i<10; i++) /*/A[i] = i;
}
.

输出样例1：

NO
/*-?

输入样例2：

void test()
{int i, A[10];for (i=0; i<10; i++) /**/A[i] = i;
}]
.

输出样例2：

NO
?-]

2.3.1设计思路

刚开始写这道题时，脑子很沉，写了一堆傻子一样的代码，很多代码块都是没用的，经常忘记出栈之前要判断栈是否为空，以下为修改过后的版本
这道题目我将/*与其他字符分开考虑。

1. 当遇见左字符时，统统直接入栈。
2. 当遇见右字符时，首先判断栈是否为空，为空就说明这个字符有问题，进入裁决函数判断输出结果。
   然后再判断他前面的栈顶的符号是否和他匹配，不匹配就说明有问题，进入裁决函数输出结果。
3. 在整个过程中，将/*替换成<，将*/替换成>，简化出栈入栈

2.3.2代码截图

2.3.3本题PTA提交列表说明

WA1:全部判断完后忘记了栈内仍有剩余的情况
WA2:在判断/*这些类型的字符是，数组下标应该移动两次。否则判断 /*/ 这种的时候可能会出错，卡了好久

2.4 题目4：银行排队问题之单窗口“夹塞”版

排队“夹塞”是引起大家强烈不满的行为，但是这种现象时常存在。在银行的单窗口排队问题中，假设银行只有1个窗口提供服务，所有顾客按到达时间排成一条长龙。当窗口空闲时，下一位顾客即去该窗口处理事务。此时如果已知第i位顾客与排在后面的第j位顾客是好朋友，并且愿意替朋友办理事务的话，那么第i位顾客的事务处理时间就是自己的事务加朋友的事务所耗时间的总和。在这种情况下，顾客的等待时间就可能被影响。假设所有人到达银行时，若没有空窗口，都会请求排在最前面的朋友帮忙（包括正在窗口接受服务的朋友）；当有不止一位朋友请求某位顾客帮忙时，该顾客会根据自己朋友请求的顺序来依次处理事务。试编写程序模拟这种现象，并计算顾客的平均等待时间。

输入样例：

6 2
3 ANN BOB JOE
2 JIM ZOE
JIM 0 20
BOB 0 15
ANN 0 30
AMY 0 2
ZOE 1 61
JOE 3 10

输出样例：

JIM
ZOE
BOB
ANN
JOE
AMY
75.2

2.4.1设计思路

一开始是想利用vector类来写这道题，因为vector可以直接删除指定元素，但是后来不管怎么样都超时了，可能是使用姿势不对，所以后来又改用数组，一遍就过了
思路如下

1. 建立map型的朋友圈，将姓名与姓名对应的键值存储起来。建立flag数组，用于判断当前客户是否已经办理过
2. 然后开始读入正式的队列顺序
3. 判断当前用户是否未办理，如果是，先将当前用户的flag置为1，代表已办理。并对等待时间进行记录。否则跳过
4. 向后进行查找，如果遇见朋友并在当前用户离开之前到达，就帮这位朋友办理，记录数据
5. 输出结果

2.4.2代码截图

2.4.3本题PTA提交列表说明

3、栈和队列上机考试

列车调度

火车站的列车调度铁轨的结构如下图所示。

两端分别是一条入口（Entrance）轨道和一条出口（Exit）轨道，它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入，最后从出口离开。在图中有9趟列车，在入口处按照{8，4，2，5，3，9，1，6，7}的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开，则至少需要多少条平行铁轨用于调度？

我原以为这题非常简单，因为我上机考试最后几分钟没提交上去，但是后来复现时发现我错了，我那时的做法根本得不到一分。

我的错误做法：

设计思想：相当于纸牌游戏，取数组保存每条轨道的最后一个，因为要保证所有的轨道都是有序的，所以只有当当前要进入的列车temp的序号小于轨道上的最后一节车时才能进入。都不满足条件就给他一条新的轨道。
错误一：一开始我是用栈去实现，发现内存被限制了，开辟的stack太大了，后来就改用数组，只记录栈顶
错误二：改用数组，判断是否能插入时，应该判断轨道中的尾车厢序号是否比要进入的小，截图中判断为大。（即使这点改对了，有的点也会超时）

改进后的正确做法：

后来我发现可以用set容器来做，而且用这个做的话巨容易，因为可以直接找到一组元素中和要查找元素最接近的元素，也可以删除，而且往一个set容器插入元素是自动排序的，查找是set也会利用二分法进行查找，会比较快
设计思想：利用upper_bound(num)函数查找和num最接近的比它大的数，如果找到了，说明可以必定可以接在现有轨道的后面，将刚好比num大的元素找到，删除，num代替之。没有的话就直接插入，也就是建立一条新轨道

先贴一下set的成员

c++ stl容器set成员函数:begin()--返回指向第一个元素的迭代器c++ stl容器set成员函数:clear()--清除所有元素c++ stl容器set成员函数:count()--返回某个值元素的个数c++ stl容器set成员函数:empty()--如果集合为空，返回truec++ stl容器set成员函数:end()--返回指向最后一个元素的迭代器c++ stl容器set成员函数:equal_range()--返回集合中与给定值相等的上下限的两个迭代器c++ stl容器set成员函数:erase()--删除集合中的元素c++ stl容器set成员函数:find()--返回一个指向被查找到元素的迭代器c++ stl容器set成员函数:get_allocator()--返回集合的分配器c++ stl容器set成员函数:insert()--在集合中插入元素c++ stl容器set成员函数:lower_bound()--返回指向大于（或等于）某值的第一个元素的迭代器c++ stl容器set成员函数:key_comp()--返回一个用于元素间值比较的函数c++ stl容器set成员函数:max_size()--返回集合能容纳的元素的最大限值c++ stl容器set成员函数:rbegin()--返回指向集合中最后一个元素的反向迭代器c++ stl容器set成员函数:rend()--返回指向集合中第一个元素的反向迭代器c++ stl容器set成员函数:size()--集合中元素的数目c++ stl容器set成员函数:swap()--交换两个集合变量c++ stl容器set成员函数:upper_bound()--返回大于某个值元素的迭代器c++ stl容器set成员函数:value_comp()--返回一个用于比较元素间的值的函数

总结：果然C++的容器是个好东西啊，这种好东西应该多了解一点。终究还是太年轻

上机考试只有一题代码题没做出来，所以下面就把做错过的一题贴出来好了，顺便吐槽一下机房的dev，找了半天的大小写错误

表达式求解

输入一个后缀表达式，程序求出表达式值。

我的错误做法：

设计思想上课老师已经讲了，我这里就不复述了。
错误:忘记考虑负数情况。//可以直接看正确代码，这张图片没注释。。就是多了个判断负数的代码块

改进后的正确做法：

终于写完了。。lay了