数据结构8.5.3 列车车厢重排

#include 
#include "arrayStack.h"
#include "myExceptions.h"
using namespace std;

arrayStack* track;     // 缓冲轨道数组
int numberOfCars;           // 车厢数量
int numberOfTracks;         // 轨道数量
int smallestCar;            // 在缓冲轨道中编号最小的车厢
int itsTrack;               // 停靠着最小编号车厢的缓冲轨道

bool railroad(int inputOrder[], int theNumberOfCars, int theNumberOfTracks)
{// 从初始顺序开始重排车厢
	// 如果重排成，返回 true，否则返回 false

	numberOfCars = theNumberOfCars;     // 车厢数量
	numberOfTracks = theNumberOfTracks; // 轨道数量

	// 创建用于缓冲轨道的栈
	track = new arrayStack [numberOfTracks + 1];

	int nextCarToOutput = 1;     // 下一个实时输出
	smallestCar = numberOfCars + 1;    // 缓冲轨道中无车厢

	// 重排车厢
	for (int i = 1; i <= numberOfCars; i++)
		if (inputOrder[i] == nextCarToOutput)
		{// 将车厢 inputOrder[i] 直接移到出轨道
			cout << "Move car " << inputOrder[i] << " from input track to output track" << endl;
			numberOfCars++;

			// 从缓冲轨道移到出轨道
			while (smallestCar == nextCarToOutput)
			{
				putputFromHoldingTrack();
				nextCarToOutput++;
			}
		}
		else
		{// 将车厢 inputOrder[i] 移到一个缓冲轨道
			//if (!putInHoldingTack(inputOrder[i]))
				return false;
		}
	return true;
}

void putputFromHoldingTrack()
{// 将编号最小的车厢从缓冲轨道移到出轨道

	// 从栈 itsTrack 中删除元素编号最小的车厢
	track[itsTrack].pop();
	cout << "Move car " << smallestCar << " from holding" << "track " << itsTrack << " to output track" << endl;

	// 检查所有栈的栈顶，寻找编号最小的车厢和他所属的栈 itsTrack
	smallestCar = numberOfCars + 2;
	for (int i = 1; i <= numberOfTracks;)
		if (!track[i].empty() && (track[i].top() < smallestCar))
		{
			smallestCar = track[i].top();
			itsTrack = i;
		}
}

bool putInHoldingTrack(int c)
{// 将车厢 c 移到一个缓冲轨道。返回 false，当且仅当没有可用的缓冲轨道

	// 为车厢 c 寻找最适合的缓冲轨道
	// 初始化
	int bestTrack = 0,    // 目前最合适的缓冲轨道
		bestTop = numberOfCars + 1;   // 取 bestTrack 中顶部的车厢

	// 扫描缓冲轨道
	for (int i = 1; i <= numberOfTracks; i++)
		if (!track[i].empty())
		{// 缓冲轨道 i 不空
			int topCar = track[i].top();
			if (c < topCar && topCar < bestTop)
			{// 缓冲轨道 i 的栈顶具有编号更小的车厢
				bestTop = topCar;
				bestTrack = i;
			}
		}
		else    // 缓冲轨道为空
			if (bestTrack == 0)
				bestTrack = i;
	// 把车厢 c 移到轨道 bestTrack
	track[bestTrack].push(c);
	cout << "Move car" << c << " from input track " << "to holding track " << bestTrack << endl;

	// 如果需要，更新 smallestCar 和 itsTrack
	if (c < smallestCar)
	{
		smallestCar = c;
		itsTrack = bestTrack;
	}
}