C++队列相关内容（题目+解析）_#include #include #include

队列相关内容

0. 简述

先简述一下queue容器的使用：

队列queue的用法如下：

1.包含头文件：#include

2.定义一个整数队列对象：queue myQe;

3.定义一个整数队列对象数组：queue myQA[10];

4.入队操作：myQe.push(itemp); //把整数itemp进入队列

5.出队操作：myQe.pop(); //把队头元素弹出队列，注意本操作不获取队头元素

6.获取队头元素： itemp = myQe.front(); // 把队头元素放入itemp中，注意本操作不弹出元素

7.判断队列是否为空：myQe.empty();//队列空则返回true，不空则返回false

在理解以上内容之后就可以开始使用queue了。

1. 银行大厅排队

描述：

在银行营业大厅共服务3种客户，类型为A\B\C，大厅分别设置了3个窗口分别服务三种客户，即每个窗口只服务一种客户。现有一批客户来银行办理业务，每个客户都有类型和办理业务时间。每个窗口按照客户到来的顺序进行服务。

输入：

第一行输入先输入n表示客户数量
第二行输入每个客户的类型，数据之间用用空格隔开
第三行输入每个客户的办理时间，数据之间用用空格隔开

/*示例*/
8
A B C B C A A A
10 20 30 40 50 60 70 80
1
2
3
4

输出：

第一行输出A类客户的平均办理时间
第二行输出B类客户的平均办理时间
第三行输出C类客户的平均办理时间

/*示例*/
55
30`在这里插入代码片`
40
1
2
3
4

解题思路：

为了算出各类客户的平均办理时间，首先要知道的是各类客户花费的总时间。

3种窗口服务三种客户，也就是算出每个窗口的时间。通过将每个窗口抽象成一个队列，将时间作为内容填入队列，即可算出总时间。

除了每个窗口的队列以外，我们还需要将输入的顺序进行存储，因此总共需要4条队列。

#include<iostream>
#include<queue>
using namespace std;

int main() {
	int t;  //次数
	int m;  //待输入的时间
	char ch;  //待输入的客户类型
	queue<int> myQe, myQa[3];  // Qe代表次序，Qa代表窗口
	cin >> t;
    
    // 输入部分
	while (t--) {
		cin >> ch;
		myQe.push(ch -65);  //注意此处push进去的是一个数字，为了查找方便，当ch=A时，把0给push进去，以此类推。
	}
    
    //输入部分
	while (!myQe.empty()) {
		cin >> m;
		int num = myQe.front();  //根据顺序获取窗口
		myQe.pop();
		myQa[num].push(m);
	}
    
    //输出部分
	for (int i = 0; i < 3; i++) {
		int n = myQa[i].size();  //计算平均数时需要的分母
		int sum = 0;
		while (!myQa[i].empty()) {
			sum += myQa[i].front();
			myQa[i].pop();
		}
		cout << sum / n << endl;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

2. 数制转换

描述：

对于任意十进制数转换为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
1
2
3
4
5
6

整数部分转为 10011，小数部分转为0.001，合起来为10011.001

整数部分可用堆栈，小数部分可用队列实现。

输入：

第一行输入t，表示有t组测试数据。
接下来每行包含两个参数n和k，n表示要转换的数值，可能是非整数；k表示要转换的数制，1<k<=16

4
19.125 2
15.125 16
84.7866 3
325.9999 13
1
2
3
4
5

输出：

每行输出转换后的结果，结果精度到小数点后3位.

10011.001
F.200
10010.210
1C0.CCC
1
2
3
4

解题思路：

这道题实际上已经不需要什么解题思路了，整数部分用栈来实现，小数部分则用队列。

在输入数据时，不要将变量定义为float类型。

float：2^23 = 8388608，一共七位，这意味着最多能有7位有效数字，但绝对能保证的为6位，也即float的精度为6~7位有效数字；
double：2^52 = 4503599627370496，一共16位，double的精度为15~16位。

对于超过十进制的数字，需要输出字母而非数字，但在定义栈或队列时依然可以使用int类型，只需要在输出时进行转换。此处使用的方法为数组，当变量12输出时，并不输出本身，而是输出一个数组的值：arr[12]，这样就可以实现字母的输出了。

#include<iostream>
#include<stack>
#include<queue>
using namespace std;

int main() {
	int t;
	char outPut[] = "0123456789ABCDEF";
    
	cin >> t;
	while (t--) {
		double r;  // 需要转换的数字
		int k;     // 进制
		int num;   // 整数部分
		stack<int> myS;
		cin >> r >> k;
		num = r;   // C4244	“=”: 从“double”转换到“int”，可能丢失数据，这正是我们的目的，只需要整数。

		r = r - num;  // 此时的r只剩小数部分
        
		while (num) {
			myS.push(num % k);
			num /= k;
		}
        
		while (!myS.empty()) {
			int count = myS.top();
			cout << outPut[count];
			myS.pop();
		}
        
		cout << ".";

 //********************************************************************************
		int i = 3;  //只需要三位，那么循环找三遍就好了
		queue<int> myQ;
		while (i--) {
			r *= k;
			num = r;
			myQ.push(num);
			r -= num;
		}
        
		while (!myQ.empty()) {
			int count = myQ.front();
			cout << outPut[count];
			myQ.pop();
		}
        
		cout << endl;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

3. 组队列

描述:

组队列是队列结构中一种常见的队列结构，意思是队列内的元素分组聚集在一起。组队列包含两种命令：

1、 ENQUEUE，表示当有新的元素进入队列，首先会检索是否有同一组的元素已经存在，如果有，则新元素排在同组的最后，如果没有则插入队列末尾。

2、 DEQUEUE，表示队列头元素出队

3、 STOP，停止操作

输入：

第1行输入一个t(t<=10)，表示组数。

第2行输入一个第1组的元素个数和数值。

第3行输入一个第2组的元素个数和数值。

以此类推输入完t组以定义同组元素之后，开始输入多个操作命令(<200)，对空的组队列进行操作，例如输入ENQUEUE 100，表示把元素100插入队列

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
1
2
3
4
5
6
7
8
9
10
11
12
13

输出：

DEQUEUE出队的元素

101 102 103
1

解题思路

这道题理解起来似乎很难，但通过例子应该很容易明白：

 3 101 102 103
 3 201 202 203
 3 301 302 303 
 ENQUEUE 201  ==>>> | 201 |
 ENQUEUE 301  ==>>> | 201 | 301 |
 ENQUEUE 102  ==>>> | 201 | 301 | 102 |
 ENQUEUE 101  ==>>> | 201 | 301 | 102 101 |
 ENQUEUE 203  ==>>> | 201 203 | 301 | 102 101 |
 ENQUEUE 302  ==>>> | 201 203 | 301 302 | 102 101 |
1
2
3
4
5
6
7
8
9

此时连续DEQUEUE会输出201->203->301->302->102->101

在进行DEQUEUE操作后，还会有ENQUEUE操作插入新的组（如果该组为空）。

1. 在一开始的初始化操作中，我们采用二维数组存储数据，每一行的第一位存储长度，后面存储数据。

2. 创建一个存储输出组的顺序的队列Qa，在创建与组数相同的队列Qb[n]，每个队列分别存储对应组的内容（按一定顺序）。

3. 当开始ENQUEUE操作后，需要将内容插入Qb，如果该组不存在与Qa，则要把组插入Qa。

4. 当我们输入一个数字时，需要判断该数字所在的组，我们写一个函数，参数为二维数组、组数、输入数，让它返回组数编号（没有时返回-1）。

5. 如何判断一个组是否在Qa中出现过呢？需要遍历Qa队列吗？答案是不一定。如果一个Qb队列为空，相当于这个组没有在Qa出现过或者出现过，但已经清理掉了。

6. 在判断ENQUEUE、DEQUEUE时，不需要完全匹配，配对第一个字符即可。

#include<iostream>
#include<queue>
#include<string>
using namespace std;

// 寻找组数的函数
int getGroupid(int arr[][100], int t, int data) {
	for (int i = 0; i < t; i++) {
		int len = arr[i][0];
		for (int j = 1; j <= len; j++) {
			if (arr[i][j] == data) {
				return i;
			}
		}
	}
	return -1;
}


int main() {
	int t;
	cin >> t;
	int group[100][100];  //这里为了省事就不从堆中new论文

    //填充数组
	for (int i = 0; i < t; i++) {
		int len;
		cin >> len;
		group[i][0] = len;
		for (int j = 1; j <= len; j++) {
			cin >> group[i][j];
		}
	}
    
    
	queue<int> Qa, Qb[10];  // 也是为了省事，不new了
	int brr[100];  //储存输出结果
	int pos = 0;   //brr的序号
    
	string opt;
	cin >> opt;
	while (opt[0] != 'S') {
		if (opt[0] == 'E') {
			int data;
			cin >> data;
            //获取组序号
			int id = getGroupid(group, t, data);
			if (Qb[id].empty()) {
				Qa.push(id);
			}
			Qb[id].push(data);
		}
		else {
			int id = Qa.front();
			int num = Qb[id].front();
			brr[pos++] = num; //放入数组
			Qb[id].pop();
		}
		cin >> opt;
	}
	for (int i = 0; i < pos; i++) {
		cout << brr[i] << " ";
	}
	cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

4. 银行单队列多窗口模拟

描述：

假设银行有K个窗口提供服务，窗口前设一条黄线，所有顾客按到达时间在黄线后排成一条长龙。当有窗口空闲时，下一位顾客即去该窗口处理事务。当有多个窗口可选择时，假设顾客总是选择编号最小的窗口。

本题要求输出前来等待服务的N位顾客的平均等待时间、最长等待时间、最后完成时间。

输入：

输入第1行给出正整数N（≤1000），为顾客总人数；随后N行，每行给出一位顾客的到达时间T和事务处理时间P，并且假设输入数据已经按到达时间先后排好了顺序；最后一行给出正整数K（≤10），为开设的营业窗口数。

9
0 20
1 15
1 61
2 10
10 5
10 3
30 18
31 25
31 2
3
1
2
3
4
5
6
7
8
9
10
11

输出：

在一行中输出平均等待时间（输出到小数点后1位）、最长等待时间、最后完成时间，之间用1个空格分隔，行末不能有多余空格。

6.2 17 62
1

解题思路

这道题更重要的是学习思想而非具体的算法，遇到这类问题时我们以什么样的一个角度去分析？

客户是按时间顺序来的，也是按时间顺序走的，那在处理问题时是不是从时间角度会更好呢？

如何知道哪个客户选择哪个窗口便是最核心的问题。

对于一个客户来说，其身上的属性包括到达时间和处理时间。这时可以把一个客户抽象成一个类或是一个结构体，这里使用类。

由于客户已经按时间先后顺序进行输入，我们只需要一个队列，把客户类实例push进queue中。

再来看题目要求，要求输出平均等待时间、最长等待时间、最后完成时间，那么需要获取的东西就包括每个人的等待时间，每个人的完成时间。

这个时候再来思考，每个窗口需要用什么类型去定义？我们先要确定窗口表示的含义。

窗口的功能是：在合适的时间开始处理事件；以及合适的时间结束事件。那么什么时候开始处理事件呢？答案1：刚开门的时候，答案2：上一个事件结束时。这个时候仅仅需要考虑结束时间就行了，相当于用一个数表示窗口状态，即int型。注意我们先把窗口初始化为0，即离开时间。

以三个窗口为例：

当第一位客户到达时，把窗口1的值改为客户1的离开时间；
当第二位客户到达时，把窗口2的值改为客户2的离开时间；
当第三位客户到达时，把窗口2的值改为客户2的离开时间；
当第四位客户到达时，会找到所有窗口中离开时间最早的那个，将里面的值改为自己的离开时间。
…

在这个过程中，可以获取到

等待时间：

waitTime = dp[id] - ss.arrivalTime; // 任务结束时间-下一个任务到达时间
1

最长等待时间：

if (waitTime > maxWaitTime) {
	maxWaitTime = waitTime;
}
1
2
3

最后完成时间：

if (dp[id] > lastFinish) {  //dp[id]表示任务结束时间，说白了就是求最大任务结束时间
	lastFinish = dp[id];
}
1
2
3

离开时间：

dp[id] = dp[id] + ss.occurTime; // 任务结束时间 + 任务处理时间
dp[id] = ss.arrivalTime + waitTime + ss.occurTime;  // 任务到达时间 + 等待时间 + 任务处理时间
1
2

这里写了两种算法，但有一种是错误的。来看看下图：

如果是这种情况，对于两种算法都是通用的。

再看看这一张图：

如果所处的情况属于上图，那么算法1就失效了。

dp[id] = dp[id] + ss.occurTime; // 失效
dp[id] = ss.arrivalTime + waitTime + ss.occurTime;  // 生效
1
2

所以在编写程序时要特别注意。

以下是代码实现：

#include<iostream>
#include<queue>
#include<iomanip>

using namespace std;

// 客户类
class Custom {
public:
	int arrivalTime;
	int occurTime;
	Custom(int a, int o) {
		arrivalTime = a;
		occurTime = o;
	}
};

int main() {
	int cusNum;
	int arrivalTime;
	int occurTime;
	queue<Custom> crr;
	cin >> cusNum;
    
    //将客户存入队列
	for (int i = 0; i < cusNum; i++) {
		cin >> arrivalTime >> occurTime;
		Custom cc(arrivalTime, occurTime);
		crr.push(cc);
	}

	int windows;
	int totalWaitTime = 0;
	int maxWaitTime = 0;
	int lastFinish = 0;


	cin >> windows;
	int* dp = new int[windows];
    // 初始化窗口为0
	for (int i = 0; i < windows; i++) {
		dp[i] = 0;
	}

	while (!crr.empty()) {
		Custom ss = crr.front();
		crr.pop();

        // 寻找合适的窗口
		int id = 0;
		for (int i = 0; i < windows; i++) {
			if (dp[i] < dp[id]) {
				id = i;
			}
		}
        
        // 求等待时间
		int waitTime = 0;
		if (dp[id] > ss.arrivalTime) {
			waitTime = dp[id] - ss.arrivalTime;
		}
        
        //总等待时间
		totalWaitTime += waitTime;
        
        //最大等待时间
		if (waitTime > maxWaitTime) {
			maxWaitTime = waitTime;
		}
        
        //结束时间
		dp[id] = ss.arrivalTime + waitTime + ss.occurTime;
        
        //最后结束时间
		if (dp[id] > lastFinish) {
			lastFinish = dp[id];
		}
	}
	cout << fixed << setprecision(1) << totalWaitTime * 1.0 / cusNum << ' ' 
        << maxWaitTime << ' ' << lastFinish << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

文章结束。