火车车厢重排问题，C++详解

实验题目

解题思路

1先看缓冲队列队头是否符合要求

2看队头元素是否符合要求

完整代码

运行结果

实验题目

火车车厢重排问题

实验说明：转轨站示意图如下：

火车车厢重排过程如下：

火车车厢重排算法伪代码如下：

解题思路

这是一看就是一道模拟题，主要是根据题目给出的伪代码实现对应的过程，要求比较强的代码复现能力与调试能力。

一共需要4个队列，一个是入轨的队列。还有三个缓冲队列，具体过程为先拿出入轨队列的第一个元素，如果是1的话就说明要出队作为结果，如果不是就要放入缓冲队列，然后再从入轨里拿队员。

关键来了，后面要找出缓冲队列中队尾元素小于我们拿出来的这个值的元素，然后找到这几个元素的最大值，然后把从入轨中拿出的那个元素放入那个队列中

这么说有点抽象，看我的代码即可（有详细注释）。

我采用的是一个纯暴力的做法，直接用一个大小为3的数组初始值为0。

	//如果不是要出列的考虑放入某个缓冲队列的队尾//方法是找到这三个缓冲队列中队尾小于x的数，这些数里最大的那个数所在的队列就是x要入的队列int a[4];a[0] = 0,a[1] = 0,a[2] = 0,a[3] = 0;//初始化都为0,这里a【0】是多余的if(!line1.empty() && line1.back() < x) {a[1] = line1.back();}if(!line2.empty() && line2.back() < x) {a[2] = line2.back();}if(!line3.empty() && line3.back() < x) {a[3] = line3.back();}//再找这三个数里最大的那个if(a[1] > a[2] && a[1] > a[3]) {line1.push(x);}if(a[2] > a[1] && a[2] > a[3]) {line2.push(x);}if(a[3] > a[1] && a[3] > a[2]) {line3.push(x);}//如果都为0随便找个空队列放着if(a[1] == 0 && a[2] == 0 && a[3] == 0) {if(line1.empty()) {line1.push(x);}else if(line2.empty()) line2.push(x);else if(line3.empty()) line3.push(x);}

具体顺序为

1先看缓冲队列队头是否符合要求

	//第一步开始考察每一个缓冲队列//如果队列不为空并且头元素恰好是要出列的那个就出列if(!line1.empty() && line1.front() == nowout) {cout << line1.front();nowout++;line1.pop();continue;//满足条件就直接进行下一次循环}if(!line2.empty() && line2.front() == nowout) {cout << line2.front();nowout++;line2.pop();continue;}if(!line3.empty() && line3.front() == nowout) {cout << line3.front();nowout++;line3.pop();continue;}

2看队头元素是否符合要求

	if(x == nowout) {cout << x;nowout++;continue;//此时入轨的那个数满足条件了，直接进行下一次循环}

3如果队头元素不符合就按照上面的要求放入缓冲队列

完整代码

#include<iostream>
#include<queue>
using namespace std;void renewline(queue<int> line)
{queue<int> line1, line2, line3;//三个缓冲轨道int nowout = 1;//表示要出列的车厢，也表示排好的车厢数目，总共9个车厢排到第9个表示排完了while (nowout != 10){//这里nowout是要不为10，是因为当它为9时9还在缓冲队列里，等9出列后nowout变为10，此时才代表队列都为空了//第一步开始考察每一个缓冲队列//如果队列不为空并且头元素恰好是要出列的那个就出列if(!line1.empty() && line1.front() == nowout) {cout << line1.front();nowout++;line1.pop();continue;//满足条件就直接进行下一次循环}if(!line2.empty() && line2.front() == nowout) {cout << line2.front();nowout++;line2.pop();continue;}if(!line3.empty() && line3.front() == nowout) {cout << line3.front();nowout++;line3.pop();continue;}//第二步再看入轨的队头元素是不是要出列的//要注意入轨不能为空int x;if(!line.empty()) {x = line.front();line.pop();}if(x == nowout) {cout << x;nowout++;continue;//此时入轨的那个数满足条件了，直接进行下一次循环}else {//如果不是要出列的考虑放入某个缓冲队列的队尾//方法是找到这三个缓冲队列中队尾小于x的数，这些数里最大的那个数所在的队列就是x要入的队列int a[4];a[0] = 0,a[1] = 0,a[2] = 0,a[3] = 0;//初始化都为0,这里a【0】是多余的if(!line1.empty() && line1.back() < x) {a[1] = line1.back();}if(!line2.empty() && line2.back() < x) {a[2] = line2.back();}if(!line3.empty() && line3.back() < x) {a[3] = line3.back();}//再找这三个数里最大的那个if(a[1] > a[2] && a[1] > a[3]) {line1.push(x);}if(a[2] > a[1] && a[2] > a[3]) {line2.push(x);}if(a[3] > a[1] && a[3] > a[2]) {line3.push(x);}//如果都为0随便找个空队列放着if(a[1] == 0 && a[2] == 0 && a[3] == 0) {if(line1.empty()) {line1.push(x);}else if(line2.empty()) line2.push(x);else if(line3.empty()) line3.push(x);}}}
}int main()
{queue<int> line;int x;while (1){cin >> x;if(x == 0) break;//当输入为0时输入停止line.push(x);//入轨道时的车厢编号顺序}cout << "排好后的车厢顺序为：";renewline(line);return 0;
}