DS|队列
题目一：DS队列 -- 银行排队
题目描述：
在银行营业大厅共服务3种客户，类型为A\B\C，大厅分别设置了3个窗口分别服务三种客户，即每个窗口只服务一种客户。现有一批客户来银行办理业务，每个客户都有类型和办理业务时间。每个窗口按照客户到来的顺序进行服务。
输入要求：
第一行输入先输入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<stack>
#include<string>
#include<cstdlib>
#include<cstring>
#include<iomanip>
#include<queue>
using namespace std;
int main(){
int n, average_time, size;
cin >> n;
queue<int> A, B, C;
queue<char> type;
int time;
char ch;
for (int i = 0; i < n; i++){
cin >> ch;
type.push(ch);
}
for (int i = 0; i < n; i++){
cin >> time;
if (type.front() == 'A') A.push(time);
else if (type.front() == 'B') B.push(time);
else C.push(time);
type.pop();
}
average_time = 0, size = A.size();
for (int i = 0; i < size; i++) {
average_time += A.front();
A.pop();
}
cout << average_time / size << endl;
average_time = 0, size = B.size();
for (int i = 0; i < size; i++) {
average_time += B.front();
B.pop();
}
cout << average_time / size << endl;
average_time = 0, size = C.size();
for (int i = 0; i < size; i++) {
average_time += C.front();
C.pop();
}
cout << average_time / size << endl;
return 0;
}题目二：DS队列 -- 数制转换
题目描述：
对于任意十进制数转换为k进制，包括整数部分和小数部分转换。整数部分采用除k求余法，小数部分采用乘k取整法例如x=19.125，求2进制转换
整数部分19， 小数部分0.125
19 / 2 = 9 … 1 0.125 * 2 = 0.25 … 0
9 / 2 = 4 … 1 0.25 * 2 = 0.5 … 0
4 / 2 = 2 … 0 0.5 * 2 = 1 … 1
2 / 2 = 1 … 0
1 / 2 = 0 … 1所以整数部分转为 10011，小数部分转为0.001，合起来为10011.001
提示整数部分可用堆栈，小数部分可用队列实现
输入要求：
第一行输入一个t，表示下面将有t组测试数据。
接下来每行包含两个参数n和k，n表示要转换的数值，可能是非整数；k表示要转换的数制，1<k<=16
输出要求：
对于每一组测试数据，每行输出转换后的结果，结果精度到小数点后3位
输出小数点后几位的代码如下：
#include <iostream>
#include <iomanip>
using namespace std;
int main() {
double r = 123.56789;
cout<<fixed<<setprecision(4)<<r<<endl;?? //输出小数点后4
return 0;
}
输入样例：
2
19.125 2
15.125 16
输出样例：
10011.001
F.200代码示例：
#include<iostream>
#include<stack>
#include<string>
#include<cstring>
#include<iomanip>
#include<queue>
using namespace std;
int main(){
int t;
cin >> t;
double n;
int k;
stack<int> integer;//整数
queue<int> decimal;//小数
while (t--) {
cin >> n >> k;
int it = (int)n;
double dc = n - it;
while (it) {
integer.push(it % k);
it /= k;
}
for (int i = 0; i < 3; i++) {//只要小数点后三位
decimal.push((int)(dc * k));
dc *= k;
dc -= (int)dc;
}
int size1 = integer.size();
for (int i = 0; i < size1; i++) {
if (integer.top() >= 10) {
char c = 'A' + integer.top() - 10;
cout << c;
}
else cout << integer.top();
integer.pop();
}
cout << ".";
int size2 = decimal.size();
if (size2 <= 3) {
for (int i = 0; i < size2; i++) {
if (decimal.front() >= 10){
char c = 'A' + decimal.front() - 10;
cout << c;
}
else cout << decimal.front();
decimal.pop();
}
for (int i = 3 - size2; i > 0; i--) cout << "0";
}
else {
for (int i = 0; i < 3; i++) {
if (decimal.front() >= 10) {
char c = 'A' + decimal.front() - 10;
cout << c;
}
else cout << decimal.front();
decimal.pop();
}
}
cout << endl;
}
return 0;
}题目三：DS队列 --?银行业务简单模拟
题目描述：
设某银行有A、B两个业务窗口，且处理业务的速度不一样，其中A窗口处理速度是B窗口的2倍 —— 即当A窗口每处理完2个顾客时，B窗口处理完1个顾客。给定到达银行的顾客序列，请按业务完成的顺序输出顾客序列。假定不考虑顾客先后到达的时间间隔，并且当不同窗口同时处理完2个顾客时，A窗口顾客优先输出。
输入要求：
输入为一行正整数，其中第1个数字N(≤1000)为顾客总数，后面跟着N位顾客的编号。编号为奇数的顾客需要到A窗口办理业务，为偶数的顾客则去B窗口。数字间以空格分隔。
输出要求：
按业务处理完成的顺序输出顾客的编号。数字间以空格分隔，但最后一个编号后不能有多余的空格。
输入样例：
8 2 1 3 9 4 11 13 15输出要求：
1 3 2 9 11 4 13 15代码示例：
#include<iostream>
#include<queue>
using namespace std;
const int N = 1010;
int main(){
int t;
cin >> t;
int size = t;
queue<int>A, B, sum;//一个总队列，两个窗口
int num;
while (t--) {
cin >> num;
if (num % 2) A.push(num);
else B.push(num);
}
while (A.size() >= 2 && B.size() >= 1) {
cout << A.front() << " ";
A.pop();
cout << A.front() << " ";
A.pop();
cout << B.front() << " ";
B.pop();
}
//如果A的等待不足两个或者B中不足一个，依次遍历A，B队列
while (A.size()) {
if (A.size() == 1 && B.size() == 0) cout << A.front();//A只剩1个客户，B不剩客户，则不用输出“ ”
else cout << A.front() << " ";//如果A还剩两个，则倒数第二个需要后带“ ”
A.pop();
}
while (B.size()) {
if (B.size() == 1) cout << B.front();B只剩1个客户，则不用输出“ ”
else cout << B.front() << " ";
B.pop();
}
return 0;
}题目四：DS队列 --?银行排队问题之单队列多窗口加VIP服务
题目描述：
假设银行有K个窗口提供服务，窗口前设一条黄线，所有顾客按到达时间在黄线后排成一条长龙。当有窗口空闲时，下一位顾客即去该窗口处理事务。当有多个窗口可选择时，假设顾客总是选择编号最小的窗口。
有些银行会给VIP客户以各种优惠服务，例如专门开辟VIP窗口。为了最大限度地利用资源，VIP窗口的服务机制定义为：当队列中没有VIP客户时，该窗口为普通顾客服务；当该窗口空闲并且队列中有VIP客户在等待时，排在最前面的VIP客户享受该窗口的服务。同时，当轮到某VIP客户出列时，若VIP窗口非空，该客户可以选择空闲的普通窗口；否则一定选择VIP窗口。
本题要求输出前来等待服务的N位顾客的平均等待时间、最长等待时间、最后完成时间，并且统计每个窗口服务了多少名顾客。
输入要求：
输入第1行给出正整数N（≤1000），为顾客总人数；随后N行，每行给出一位顾客的到达时间T、事务处理时间P和是否VIP的标志（1是VIP，0则不是），并且假设输入数据已经按到达时间先后排好了顺序；最后一行给出正整数K（≤10）—— 为开设的营业窗口数，以及VIP窗口的编号（从0到K?1）。这里假设每位顾客事务被处理的最长时间为60分钟。
输出要求：
在第一行中输出平均等待时间（输出到小数点后1位）、最长等待时间、最后完成时间，之间用1个空格分隔，行末不能有多余空格。
在第二行中按编号递增顺序输出每个窗口服务了多少名顾客，数字之间用1个空格分隔，行末不能有多余空格。
输入样例：
10
0 20 0
0 20 0
1 68 1
1 12 1
2 15 0
2 10 0
3 15 1
10 12 1
30 15 0
62 5 1
3 1输出样例：
15.1 35 67
4 5 1代码示例：
#include<iostream>
#include<cmath>
#include<iomanip>
using namespace std;
const int MAXN = 2000;
const int INF = 0x3f3f3f3f;
struct Banker {
int T; // 到达时间
int P; // 事务处理时间
int VIP; // 是否是VIP
};
Banker queueBank[MAXN];
bool used[MAXN], itime[11][MAXN * 60];
int total_serve[MAXN];
int main() {
int n;
cin >> n;
// 输入每个顾客的到达时间、事务处理时间和VIP状态
for (int i = 0; i < n; i++) {
cin >> queueBank[i].T >> queueBank[i].P >> queueBank[i].VIP;
if (queueBank[i].P > 60) queueBank[i].P = 60; // 限制事务处理时间不超过60分钟
}
int k, v;
cin >> k >> v;
int cnt = n, sum_waitime = 0, max_waitime = 0, finish = 0;
// 模拟银行业务处理过程
for (int t = 0; cnt; t++) {
// 处理VIP客户
if (itime[v][t] == false) {
for (int i = 0; i < n; i++) {
if (used[i] || !queueBank[i].VIP) continue;
if (queueBank[i].T > t) break;
total_serve[v]++;
max_waitime = max(max_waitime, t - queueBank[i].T);
finish = max(finish, t + queueBank[i].P);
sum_waitime += (t - queueBank[i].T);
cnt--;
used[i] = true;
for (int j = 0; j < queueBank[i].P; j++) itime[v][t + j] = true;
break;
}
}
// 处理普通客户
for (int i = 0; i < k; i++) {
if (itime[i][t] == false) {
for (int j = 0; j < n; j++) {
if (used[j]) continue;
if (queueBank[j].T > t) break;
total_serve[i]++;
max_waitime = max(max_waitime, t - queueBank[j].T);
sum_waitime += (t - queueBank[j].T);
cnt--;
used[j] = true;
finish = max(finish, t + queueBank[j].P);
for (int h = 0; h < queueBank[j].P; h++) itime[i][t + h] = true;
break;
}
}
}
}
// 输出结果
cout << fixed << setprecision(1) << sum_waitime * 1.0 / n << " "; // 平均等待时间
cout << max_waitime << " " << finish << endl; // 最长等待时间和处理结束时间
for (int i = 0; i < k; i++) {
if (i) cout << " ";
cout << total_serve[i]; // 每个窗口的服务客户数量
}
return 0;
}问题五：DS队列 -- 排队游戏
题目描述：
在幼儿园中，老师安排小朋友做一个排队的游戏。首先老师精心的把数目相同的小男孩和小女孩编排在一个队列中，每个小孩按其在队列中的位置发给一个编号（编号从0开始）。然后老师告诉小朋友们，站在前边的小男孩可以和他后边相邻的小女孩手拉手离开队列，剩余的小朋友重新站拢，再按前后相邻的小男孩小女孩手拉手离开队列游戏，如此往复。由于教师精心的安排，恰好可以保证每两个小朋友都能手拉手离开队列，并且最后离开的两个小朋友是编号最小的和最大的两个小朋友。（注：只有小男孩在前，小女孩在后，且他们两之间没有其他的小朋友，他们才能手拉手离开队列）。请根据老师的排队，按小女孩编号从小到大的顺序，给出所有手拉手离开队列的小男孩和小女孩的编号对。
输入要求：
用一个字符串代表小朋友队列。字符串中只会出现两个字符，分别代表小男孩和小女孩，首先出现的字符代表小男孩，另一个字符代表小女孩。小孩总数不超过2000。
输出要求：
按小女孩编号顺序，顺序输出手拉手离开队列的小男孩和小女孩的编号对，每行一对编号，编号之间用一个空格分隔。
输入样例：
((()(())())(()))输出样例：
2 3
5 6
4 7
8 9
1 10
12 13
11 14
0 15代码示例：
#include<iostream>
#include<stack>
#include<string>
#include<cstring>
#include<queue>
using namespace std;
struct group {
int boy;
int girl;
};
int main(){
string str;
cin >> str;
int lenth = str.size();
stack<int> index;
queue<group> ultimate;
char boy = str[0];
index.push(0);
for (int i = 1; i < lenth; i++) {
if (str[i] == boy) index.push(i);
else {
ultimate.push({ index.top(),i });
index.pop();
}
}
while (ultimate.size()) {
cout << ultimate.front().boy << " " << ultimate.front().girl << endl;
ultimate.pop();
}
cout << endl;
return 0;
}问题六：DS队列 -- 组队列
题目描述：
组队列是队列结构中一种常见的队列结构，在很多地方有着广泛应用。组队列是是指队列内的元素分组聚集在一起。组队列包含两种命令：
1、 ENQUEUE，表示当有新的元素进入队列，首先会检索是否有同一组的元素已经存在，如果有，则新元素排在同组的最后，如果没有则插入队列末尾。
2、 DEQUEUE，表示队列头元素出队
3、 STOP，停止操作
输入要求：
第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
3
3 101 102 103
3 201 202 203
3 301 302 303
ENQUEUE 201
ENQUEUE 301
ENQUEUE 102
DEQUEUE
DEQUEUE
DEQUEUE
ENQUEUE 101
ENQUEUE 203
ENQUEUE 302
ENQUEUE 301
DEQUEUE
DEQUEUE
DEQUEUE
STOP
输出样例：
101 102 103201 301 102 101 203 302代码示例：
#include<iostream>
#include<stack>
#include<string>
#include<cstring>
#include<iomanip>
#include<queue>
#include<map>
using namespace std;
const int N = 1010;
int main()
{
map<int, int> maplive;
int n, t, num;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> t;
for (int j = 0; j < t; j++) {
cin >> num;
maplive[num] = i;
}
}
queue<int> my_queue[11];
queue<int> out_queue;
queue<int> markindex;
bool mark[11] = { 0 };
string opertion;
while (1) {
cin >> opertion;
if (opertion == "STOP") break;
else if (opertion == "ENQUEUE") {
cin >> num;
my_queue[maplive[num]].push(num);
if (!mark[maplive[num]]) {
markindex.push(maplive[num]);
mark[maplive[num]] = true;
}
}
else
{
out_queue.push(my_queue[markindex.front()].front());
my_queue[markindex.front()].pop();
if (my_queue[markindex.front()].empty()) {
mark[markindex.front()] = false;
markindex.pop();
}
}
}
while (out_queue.size()) {
cout << out_queue.front();
if (out_queue.size() == 1) cout << endl;
else cout << " ";
out_queue.pop();
}
}本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！