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

实验题目

火车车厢重排问题

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

火车车厢重排过程如下：

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

解题思路

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

        一共需要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;
}

 运行结果

输入我采用的是题目给的数据，当输入0时就代表输入停止。

以上是运行结果截图，按照要求输出了正确的顺序。