【数据结构】使用队列实现循环调度法

现有名称为namei且处理时间为timei的n个任务按照顺序排成一列，CPU通过循环调度法逐一处理这些任务，每个任务最多处理q ms(这个时间称为时间片)。如果q ms之后任务尚未处理完毕，那么该任务将被移动至队伍最末尾，CPU随即开始处理下一个任务。举个例子，假设q是100，然后有如下任务队列。
A(150) – B(80) – C(200) – D(200)
首先A被处理100 ms，然后带着剩余的50 ms移动至队尾
B(80) – C(200) – D(200) – A(50)
随后B被处理80 ms，在总计第180 ms时完成处理，从队列中消失
C(200) – D(200) – A(50)
接下来C被处理100 ms，然后带着剩余的100 ms移动至队尾。
D(200) – A(50) – C(100)
之后同理，一直循环到处理完所有任务。
请编写一个程序，模拟循环调度法。
输入
输入形式如下
n q
name1 time1
name2 time2
…
namen timen
第一行输入表示任务数的整数n与时间片的整数q，用一个空格隔开
接下来n行输入各任务的信息。字符串namei与timei用一个空格隔开。
输出
按照任务完成的先后顺序输出各任务名以及结束时间，任务名与对应结束时间用空格隔开，
每一对任务名与结束时间占一行。
限制
1 ≤n ≤100 000
1 ≤q ≤1000
1 ≤timei ≤50 000
1 ≤字符串namei的长度 ≤10
1 ≤timei的和 ≤1 000 000

输入示例				输出示例 
5 100					p2 180 
p1 150					p5 400
p2 80					p1 450
p3 200					p3 350
p4 350					p4 800
p5 20 

#include 
#include 
#define LEN 100005
//代表任务的结构体 
typedef struct pp {
	char name[100];	//任务名 
	int t;			//任务时间 
}P;
P Q[LEN];//顺序表 
int head, tail, n;

void enqueue(P x) {
	Q[tail] = x;
	tail = (tail + 1) % LEN;
}//入队 
P dequeue() {
	P x = Q[head];
	head = (head + 1) % LEN;
	return x;
}//出队 
int min(int a, int b) {
	return a < b ? a : b;
}
int main() {
	int elaps = 0, c;
	int i, q;
	P u;
	scanf("%d %d", &n, &q);
	for (i = 1; i <= n; i++) {
		scanf("%s", Q[i].name);
		scanf("%d", &Q[i].t);
	}
	head = 1; tail = n + 1;
	while (head != tail) {
		u = dequeue();	//出队 
		c = min(q, u.t);	//执行时间片q或所需时间u.t处理 
		u.t -= c;			//计算剩余的所需时间 
		elaps += c;		//累计已经过的时间 
		if (u.t > 0)	enqueue(u);//如果处理尚未结束则重新添加至队列 
		else {
			printf("%s %dn", u.name, elaps);
		}
	}
	return 0;
}

我们也可以用C++中STL的queue来解该题。

#include 
#include 
#include  
#include 
using namespace std;
int main() {
	int n, q, t;
	string name;
	//使用标准库中的queue 
	queue > Q;
	//pair是保存成对数值的结构体模板，声明时需要在 < >中指令两个数据类型。
	//make pair用于生成一对数值,第 1个元素通过first访问,第 2个元素通过second访问
	cin >> n >> q;
	for (int i = 0; i < n; i++) {
		cin >> name >> t;
		Q.push(make_pair(name, t));
	}
	pairu;
	int elaps = 0, a;
	while (!Q.empty()) {
		u = Q.front(); Q.pop();
		a = min(u.second, q);
		u.second -= a;
		elaps += a;
		if (u.second > 0) {
			Q.push(u);
		}
		else {
			cout << u.first << " " << elaps << endl;
		}
	}
	return 0;
}