第五周做题总结_数据结构_队列与应用
id:43 A. DS队列之银行排队
题目描述
银行营业大厅共服务3种客户，类型为A\B\C，大厅分别设置了3个窗口分别服务三种客户，即每个窗口只服务一种客户。现有一批客户来银行办理业务，每个客户都有类型和办理业务时间。每个窗口按照客户到来的顺序进行服务。
编程实现它们的办理流程，请使用C++自带的queue必须使用队列实现，其他方法0分！
队列queue的用法如下：
-
包含头文件：#include
-
定义一个整数队列对象：queue myQe;
-
定义一个整数队列对象数组：queue myQA[10];
-
入队操作：myQe.push(itemp); //把整数itemp进入队列
-
出队操作：myQe.pop(); //把队头元素弹出队列，注意本操作不获取队头元素
-
获取队头元素： itemp = myQe.front(); // 把队头元素放入itemp中，注意本操作不弹出元素
-
判断队列是否为空：myQe.empty();//队列空则返回true，不空则返回false
输入
第一行输入先输入n表示客户数量
第二行输入每个客户的类型，数据之间用用空格隔开
第三行输入每个客户的办理时间，数据之间用用空格隔开
输出
第一行输出A类客户的平均办理时间
第二行输出B类客户的平均办理时间
第三行输出C类客户的平均办理时间
输入样例
8
A B C B C A A A
10 20 30 40 50 60 70 80
输出样例
55
30
40
题解
题目的数据是先将类型输入进来，然后后面再输入按顺序的类型的客户办理时间，一 一对应，思考的就是怎么将后面输入进来的办理时间与早已输入进来的类型对应，找到关系，因为栈的特点是后进先出，所以第一个输入进来的时间不与第一个输入进来的类型对应，所以不能用栈，而队列的特点就是先进先出，所以第一个输入进来的时间能与第一个输入进来的类型对应，所以我们只需要把类型都压进队列中，当输入进来一个时间后，从队列弹出一个类型，按照这个类型将时间累加进这个类型的时间总和
代码实现
#include <iostream>
#include <queue>
using namespace std;
int main()
{
int n, i, item, aveA, aveB, aveC, m, cntA, cntB, cntC;
char type, ch;
queue<char> myQB;
cin >> n;
ch = getchar();
aveA = 0;
aveB = 0;
aveC = 0;
cntA = 0;
cntB = 0;
cntC = 0;
for (i = 0; i < n; i++)
{
cin >> type;
myQB.push(type);
}
while (!myQB.empty())
{
cin >> item;
m = myQB.front();
if (m == 'A')
{
aveA += item;
cntA++;
}
else if (m == 'B')
{
aveB += item;
cntB++;
}
else if (m == 'C')
{
aveC += item;
cntC++;
}
myQB.pop();
}
cout << aveA / cntA << endl;
cout << aveB / cntB << endl;
cout << aveC / cntC << endl;
return 0;
}
id:44 B. DS队列+堆栈–数制转换
题目描述
对于任意十进制数转换为k进制，包括整数部分和小数部分转换。整数部分采用除k求余法，小数部分采用乘k取整法例如x=19.125，求2进制转换
整数部分19
19 / 2 = 9 … 1
9 / 2 = 4 … 1
4 / 2 = 2 … 0
2 / 2 = 1 … 0
1 / 2 = 0 … 1
小数部分0.125
0.125 * 2 = 0.25 … 0
0.25 * 2 = 0.5 … 0
0.5 * 2 = 1 … 1
所以整数部分转为 10011，小数部分转为0.001，合起来为10011.001
提示整数部分可用堆栈，小数部分可用队列实现
注意：必须按照上述方法来实现数制转换，其他方法0分
输入
第一行输入一个t，表示下面将有t组测试数据。
接下来每行包含两个参数n和k，n表示要转换的数值，可能是非整数；k表示要转换的数制，1<k<=16
输出
对于每一组测试数据，每行输出转换后的结果，结果精度到小数点后3位
输入样例
2
19.125 2
15.125 16
输出样例
10011.001
F.200
提示
例如：十进制数254.3879转换为6进制数。
整数部分254，
254 / 6 = 42 … 2
42 / 6 = 7 … 0
7 / 6 = 1 … 1
1 / 6 = 0 … 1
小数部分0.3879，
0.3879 * 6 = 2.3274 … 2
0.3274 * 6 = 1.9644 … 1
0.9644 * 6 = 5.7864 … 5
所以整数部分转为 1102，小数部分转为0.215，转换后的6进制数合起来为1102.215
题解
- 第一步要思考的是如何从一个浮点数中提取出它的整数部分和小数部分，整数部分就是用一个整数类型的变量，让这个浮点数直接赋值给这个变量，做强制类型转换，这样就得到了这个浮点数的整数部分，再让这个浮点数减去它的整数就得到了小数部分
- 第二步就是思考转换，将整数除k求余得到的数压入堆栈，将小数部分乘k取得的整数压入队列，这个过程用循环实现，由于我们要输出小数点后三位，所以对于小数部分的循环，我们的循环条件是这个队列的
size要小于3，因为16进制的输出格式特殊，所以我们使用cout << uppercase; // 设置为大写字母，cout << nouppercase; // 重置格式以防影响后续输出，<< hex来控制格式的输出
代码实现
#include <iostream>
#include <queue>
#include <stack>
#include <iomanip> // 用于设置小数精度
using namespace std;
int main()
{
int t, i, k, x, m;
double n, y;
stack<int> s; // 整数
queue<int> myQA; // 小数
cin >> t;
for (i = 0; i < t; i++)
{
cin >> n >> k;
x = n; // 整数部分
y = n - x; // 小数
// 把值压进去
while (x > 0) // 整数
{
m = x % k; // 余数
x /= k;
s.push(m);
}
while (myQA.size() < 3) // 小数
{
m = y * k; // 积
y *= k;
y -= m;
myQA.push(m);
}
// 弹出值
cout << uppercase; // 设置为大写字母
while (!s.empty()) // 若不为空
{
cout << hex << s.top();
s.pop();
}
cout << ".";
while (!myQA.empty())
{
cout << hex << myQA.front();
myQA.pop();
}
cout << endl;
// 重置格式以防影响后续输出
cout << nouppercase;
}
return 0;
}
id:45 C. DS队列–组队列
题目描述
组队列是队列结构中一种常见的队列结构，在很多地方有着广泛应用。组队列是是指队列内的元素分组聚集在一起。组队列包含两种命令：
-
ENQUEUE，表示当有新的元素进入队列，首先会检索是否有同一组的元素已经存在，如果有，则新元素排在同组的最后，如果没有则插入队列末尾。
-
DEQUEUE，表示队列头元素出队
-
STOP，停止操作
建议使用C++自带的队列对象queue，编程更方便
输入
第1行输入一个t(t<=10)，表示1个队列中有多少个组
第2行输入一个第1组的元素个数和数值
第3行输入一个第2组的元素个数和数值
以此类推输入完t组以定义同组元素之后，开始输入多个操作命令(<200)，对空的组队列进行操作，例如输入ENQUEUE 100，表示把元素100插入队列
输出
DEQUEUE出队的元素
输入样例
2
3 101 102 103
3 201 202 203
ENQUEUE 101
ENQUEUE 201
ENQUEUE 102
ENQUEUE 202
ENQUEUE 103
ENQUEUE 203
DEQUEUE
DEQUEUE
DEQUEUE
STOP
输出样例
101 102 103
提示
可以看到队列分组，先入队的组在队列中靠前，出队也靠前：
DEQUEUE 输出 201，队列变为 | 203 | 301 302 | 102 101 | …
题解
主要的是要注意输入进来的数要按照分组依据压进新的队列，而且是先进先出，而不是按之前的队列的分组进不同的位置，因为是队列，如果该元素不属于任何现有组，插入到最后一位
代码实现
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main()
{
int t, i, n, j, item, num, f, k;
string type;
queue<int> myQA[10]; // 存储原始组
vector<queue<int>> myQB; // 用于按组存储已插入的元素
cin >> t;
f = 0; // 第一次DEQUEUE输出标志
// 读取每个组的元素
for (i = 0; i < t; i++)
{
cin >> n;
for (j = 0; j < n; j++)
{
cin >> item;
myQA[i].push(item); // 将元素插入原始组
}
}
while (cin >> type)
{
if (type == "STOP")
{
break;
}
else if (type == "ENQUEUE")
{
cin >> num;
bool inserted = false;
// 遍历每个组，检查该元素是否属于该组
for (i = 0; i < t; i++)
{
queue<int> temp = myQA[i]; // 复制组队列
while (!temp.empty())
{
if (temp.front() == num) // 找到该元素所属的组
{
// 查找是否已经存在该组的队列
for (auto& q : myQB) // 遍历myQB中的每个队列q
{
if (!q.empty() && q.front() == myQA[i].front())
{
q.push(num); // 将元素插入对应组的队列
inserted = true;
break;
}
}
}
temp.pop();
}
if (inserted)
{
break;
}
}
// 如果该元素不属于任何现有组，插入到新的队列
if (!inserted)
{
queue<int> newGroupQueue;
newGroupQueue.push(num);
myQB.push_back(newGroupQueue);
}
}
else if (type == "DEQUEUE")
{
k = 0;
// 查找第一个非空队列并出队
while (k < myQB.size() && myQB[k].empty())
{
k++;
}
if (k < myQB.size())
{
if (f == 0)
{
cout << myQB[k].front(); // 首次输出
f = 1; // 标记首次输出
}
else
{
cout << " " << myQB[k].front(); // 后续输出
}
myQB[k].pop(); // 出队
// 如果队列已空，移除该队列
if (myQB[k].empty())
{
myQB.erase(myQB.begin() + k);
}
}
}
}
cout << endl;
return 0;
}
id:50 D. DS队列----银行单队列多窗口模拟
题目描述
假设银行有K个窗口提供服务，窗口前设一条黄线，所有顾客按到达时间在黄线后排成一条长龙。当有窗口空闲时，下一位顾客即去该窗口处理事务。当有多个窗口可选择时，假设顾客总是选择编号最小的窗口。
本题要求输出前来等待服务的N位顾客的平均等待时间、最长等待时间、最后完成时间。
输入
输入第1行给出正整数N（≤1000），为顾客总人数；随后N行，每行给出一位顾客的到达时间T和事务处理时间P，并且假设输入数据已经按到达时间先后排好了顺序；最后一行给出正整数K（≤10），为开设的营业窗口数。
输出
在一行中输出平均等待时间（输出到小数点后1位）、最长等待时间、最后完成时间，之间用1个空格分隔，行末不能有多余空格。
输入样例
9
0 20
1 15
1 61
2 10
10 5
10 3
30 18
31 25
31 2
3
输出样例
6.2 17 62
题解
- 主要的思路是算好窗口的结束时间，知道结束时间后，就能算出等待时间
- 最先初始化窗口的结束时间是0，然后列出每个人的开始办理的时间，完成办理的时间和等待时间，每列好一个人就更新等待时间
- 主函数是，将输入进来的顾客到达时间和事务处理时间都压入队列，然后初始化窗口结束时间，接着执行操作，用一个循环找到结束时间最小的窗口号和最短的结束时间，如果这个顾客到达的时间大于等于窗口的最短结束时间，则表示不用等待，然后更新窗口的结束时间，如果顾客到达时间小于窗口的最短结束时间，则表示需要等待，则计算等待时间，并判断是否要更新最长等待时间，然后更新窗口的结束时间，最后遍历窗口的结束时间，找到最后完成时间，最后输出结果
代码实现
#include <iostream>
#include <queue>
#include <iomanip>
using namespace std;
int main()
{
int N, T, P, K, i, max, finish, min_k, m;
double sum;
queue<int> myQe;
cin >> N;
sum = 0.0; // 顾客总的等待时间
max = 0; // 最长等待时间
for (i = 0; i < N; i++)
{
// 顾客的到达时间T和事务处理时间P
cin >> T >> P;
myQe.push(T);
myQe.push(P);
}
// 开设的营业窗口数
cin >> K;
int *arr = new int[K];
// 初始化窗口结束时间都是0
for (i = 0; i < K; i++)
{
arr[i] = 0;
}
// 执行操作
while (!myQe.empty())
{
min_k = 100;
m = 0; // 窗口数
// 找到结束时间最小的窗口
for (i = 0; i < K; i++)
{
if (min_k > arr[i])
{
min_k = arr[i]; // 最短结束时间
m = i; // 此时窗口数
}
}
// 顾客不用等待
if (myQe.front() >= min_k)
{
arr[m] = myQe.front(); // 更新窗口结束时间为开始时间
myQe.pop(); // 到处理时间
arr[m] += myQe.front(); // 更新窗口结束时间加上处理时间
myQe.pop(); // 到下一个顾客
}
// 需要等待
else
{
// 更新最长等待时间
if (max < (min_k - myQe.front()))
{
max = min_k - myQe.front();
}
sum += min_k - myQe.front(); // 减的是到达时间
myQe.pop(); // 到处理时间
arr[m] += myQe.front(); // 更新窗口结束时间加上处理时间
myQe.pop(); // 到下一个顾客
}
}
// 更新完全部的顾客，窗口结束时间，找到最后完成时间
finish = 0;
for (i = 0; i < K; i++)
{
if (finish < arr[i])
{
finish = arr[i];
}
}
cout << fixed << setprecision(1) << sum / N << " ";
cout << max << " " << finish << endl << endl;
delete[] arr;
return 0;
}