队列的应用——火车重排（java实现）

队列的应用——火车重排（java实现）"/>

队列的应用——火车重排（java实现）

队列的应用——火车重排（java实现）

问题描述

一列火车有n节车厢，每节车厢将停放在不同的车站。假定n个车站的编号为1~n，为了使一列火车在行驶途中每经过一个车站，就将车厢编号与车站编号一致的车厢卸下，所以给定一个乱序的车厢序列应配合缓冲轨道按车厢号从1-n顺序排放。

程序伪代码

1.初始化k个缓冲轨道;
2.初始化即将要输出的火车编号 nowOut = 1;
3.依次取出入轨的车厢号now;3.1 如果now等于nowOut;3.1.1 输出该车厢号; 3.1.2 nowOut++;3.2 否则考察每个缓冲轨道的队头元素trackFirst3.2.1 如果trackFirst等于nowOut3.2.1.1 输出队头元素;3.2.1.2 nowOut++;3.2.1.3 继续处理now。3.3 如果now和trackFirst不等于nowOut3.3.1 考察每个缓冲轨道求出存在小于now的最大队尾元素的轨道号index3.3.2 如果index存在，则将now放入index号队列3.3.3 如果index不存在但是存在空轨道那么把now放入空轨道，否则输出无法重新排列。

火车重排过程

代码

package com.SimpleSort;import java.util.ArrayList;
import java.util.LinkedList;public class TrainResort {// 对k个队列进行初始化public static ArrayList<LinkedList<Integer>> initTrackList(int k) {ArrayList<LinkedList<Integer>> trackList = new ArrayList<LinkedList<Integer>>();for (int i = 0; i < k; i++) {trackList.add(new LinkedList<Integer>());}return trackList;}// 考察每个队列的对头元素public static boolean testTrackFirst(int nowOut,ArrayList<LinkedList<Integer>> trackList) {for (int i = 0; i < trackList.size(); i++) {LinkedList<Integer> track = trackList.get(i);if (track.isEmpty()) {continue;}int firstEle = track.getFirst();if (firstEle == nowOut) {System.out.print("输出" + nowOut);track.removeFirst();return true;}}return false;}// 考察每个队列的队尾元素public static boolean testTrackLast(int now,ArrayList<LinkedList<Integer>> trackList) {int maxLast = 0;int index = -1;for (int i = 0; i < trackList.size(); i++) {LinkedList<Integer> track = trackList.get(i);if (track.isEmpty()) {continue;}int lastEle = track.getLast();if (maxLast < lastEle && lastEle < now) {maxLast = lastEle;index = i;}}if (index != -1) {trackList.get(index).add(now);return true;}return false;}// 判断是否存在空轨道public static boolean testEmptyTrack(int now,ArrayList<LinkedList<Integer>> trackList) {for (int i = 0; i < trackList.size(); i++) {LinkedList<Integer> track = trackList.get(i);if (track.isEmpty()) {track.add(now);return true;}}return false;}public static void main(String[] args) {int[] arr = { 3, 6, 9, 2, 4, 7, 1, 8, 5 };ArrayList<LinkedList<Integer>> trackList = initTrackList(2);int nowOut = 1;//依次处理待排项for (int i = 0; i < arr.length; i++) {System.out.println();int now = arr[i];//如果当前项与即将输出的相符if (now == nowOut) {System.out.print("输出" + nowOut);nowOut++;continue;}//如果缓冲轨道中有队头元素与待输出项相符if (testTrackFirst(nowOut, trackList)) {nowOut++;//继续判断缓冲轨道中是否有队头元素与待输出项相符while(testTrackFirst(nowOut, trackList)){nowOut++;}//判断当前项与待输出项是否相符if (now == nowOut) {System.out.print("输出" + nowOut);nowOut++;continue;}//将当前项插入合适的队尾if (testTrackLast(now, trackList)) {continue;}//将当前项插入合适的空队。if (testEmptyTrack(now, trackList)) {continue;} else {System.out.println("无法重排");}}if (testTrackLast(now, trackList)) {continue;}if (testEmptyTrack(now, trackList)) {continue;} else {System.out.println("无法重排");}}//处理好待排项之后处理缓冲while(nowOut <= arr.length){testTrackFirst(nowOut, trackList) ;nowOut++;}}
}

欢迎学习，如有错误请及时联系本人修改。
希望指出本人不足共同进步
LLY19960418