1、问题描述 一列货运列车有n节车厢，每节车厢要停靠在不同的车站。假设n个车站从1到n编号，而且货运列车按照从n到1的顺序经过车站，车厢的编号与它们要停靠的车站编号相同。为了便于从列车上卸掉相应的车厢，必须按照从前至后、从1到n的顺序把车厢重新排列。
2、具体代码
// 列车车厢重排问题 #include <iostream> #include <stack> using namespace std; // 定义全局变量 stack<int> *track; // 缓冲轨道数组 int numberOfCars; // 车厢数 int numberOfTracks; // 缓冲轨道数 int smallestCar; // 在缓冲轨道中编号最小的车厢 int itsTrack; // 停靠着最小编号车厢的缓冲轨道 // 将编号最小的车厢从缓冲轨道移到出轨道 void outputFromHoldingTrack() { // 从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; i++) { if(!track[i].empty() && (track[i].top() < smallestCar)) { smallestCar = track[i].top(); itsTrack = i; } } } // 将车厢c移到一个缓冲轨道。返回false，当且仅当没有可用的缓冲轨道 bool putInHoldingTrack(int c) { // 为车厢c寻找最合适的缓冲轨道 // 初始化 int bestTrack = 0; // 目前最合适的缓冲轨道 int 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 { // 缓冲轨道i为空 if(bestTrack == 0) bestTrack = i; } } // 没有可用的缓冲轨道 if(bestTrack == 0) return false; // 把车厢c移动到轨道bestTrack track[bestTrack].push(c); cout<<"Move car "<<c<<" from input track to holding track "<<bestTrack<<endl; // 如果需要，更新samllestCar和itsTrack if(c < smallestCar) { smallestCar = c; itsTrack = bestTrack; } return true; } // 从初始顺序开始重排车厢，如果重排成功，返回true，否则返回false bool railroad(int inputOrder[], int theNumberOfCars, int theNumberOfTracks) { numberOfCars = theNumberOfCars; numberOfTracks = theNumberOfTracks; // 创建用于缓冲轨道的栈 track = new stack<int> [numberOfTracks + 1]; int nextCarToOutput = 1; smallestCar = numberOfCars + 1; // 缓冲轨道中无车厢 // 重排车厢 for(int i = 1; i <= numberOfCars; i++) { if(inputOrder[i-1] == nextCarToOutput) { // 将车厢inputOrder[i-1]直接移动出轨道 cout<<"Move car "<<inputOrder[i-1]<<" from input track to output tarck"<<endl; nextCarToOutput++; // 从缓冲轨道移到出轨道 while(smallestCar == nextCarToOutput) { outputFromHoldingTrack(); nextCarToOutput++; } } else { // 将车厢inputOrder[i-1]移到一个缓冲轨道 if(!putInHoldingTrack(inputOrder[i-1])) return false; } } return true; } int main() { int inputOrder[] = {3,6,9,2,4,7,1,8,5}; if(!railroad(inputOrder, 9, 3)) cout<<"无法重排！"<<endl; return 0; }3、输出实例
