火车车厢重排问题（栈）

问题描述：原文
一列货运列车共有n节车厢，每节车厢将停放在不同的车站。假定n个车站的编号分别为1~n,货运列车按照第n站至第1站的顺序经过这些车站。车厢编号与他们的目的地一样。为了便于从列车上卸掉相应的车厢，必须重排车厢顺序，使得各车厢从前往后按编号1到n的次序排列。当所有车厢按照这种次序排列时，在每个车站只需卸掉最后一个车厢即可。我们在一个转轨站里完成重排的工作，在转轨站有一个入轨，一个出轨和k个缓冲轨（位于入轨和出轨之间）。下面的图示就是一个转轨站，其中有3个缓冲轨，H1,H2,H3。
开始的时候，n节车厢从入轨处进入转轨站，转轨结束时各车厢从右往左按编号1到n的次序离开转轨站。如上图所示。

算法描述：为了重排车厢，需从前往后依次检查入轨上的所有车厢。如果正在检查的车厢就是下一个满足要求的车厢，可以直接把它放到出轨上。否则，则把它移动到缓冲轨上，直到按输出顺序要求轮到它的时候才可以将他放到出轨上。缓冲轨是按照栈的方式使用的，因为车厢的进出都是在缓冲轨的顶端进行的。
在重排车厢过程中，仅允许以下活动：

1、车厢可以从入轨的前部移动到一个缓冲轨的顶部或者是出轨的左端
2、车厢可以从一个缓冲轨的顶部移动到出轨的左端

代码实现：

    class Program
    {
        static bool RailRoad(int[] p, int k)//p指原来车厢的顺序，k是缓冲轨的数量。
        {
            LinkStack<int>[] BufferRail = new LinkStack<int>[k];
            for (int i = 0; i < k; i++)
            {
                BufferRail[i] = new LinkStack<int>();//分配存储空间
            }

            int NowOut = 1;//NowOut指的是现在轮到几号车厢出轨
            int minH = int.MaxValue;//minH指的是在缓冲轨内的车厢的最小编号。
            int minS = -1;//minS指的是minH对应的BufferRail里面的哪条缓冲轨

            for (int i = 0; i < p.Length; i++)
            {
                if (p[i] == NowOut)
                {
                    Console.WriteLine("移动车厢：{0}从入轨到出轨", p[i]);
                    NowOut++;

                    while (minH == NowOut)//若全部的缓冲轨均为空的话，则不会进入到该循环。
                    {
                        Console.WriteLine("移动车厢：{0}从缓冲轨{1}到出轨", minH, minS);
                        OutStack(ref minH, ref minS, BufferRail);//最主要的作用就是更新minH和minS                        
                        NowOut++;
                    }
                }
                else
                {
                    bool result = EnterStack(p[i], ref minH, ref minS, BufferRail);
                    if (result == false)
                    {
                        return false;
                    }
                }
            }

            return true;
        }

        static void OutStack(ref int minH, ref int minS, LinkStack<int>[] BufferRail)
        {
            BufferRail[minS].Pop();//出栈

            minH = int.MaxValue;
            minS = -1;
            for (int i = 0; i < BufferRail.Length; i++)
            {
                if (BufferRail[i].IsEmpty() == false)
                {
                    if (BufferRail[i].StackTop < minH)
                    {
                        minH = BufferRail[i].StackTop;
                        minS = i;
                    }
                }
            }
        }

        static bool EnterStack(int c, ref int minH, ref int minS, LinkStack<int>[] BufferRail)
        {
            //参数c代表要进入的车厢的编号。
            int bestTrack = -1;//c号车厢能进入的最优缓冲轨
            int bestTop = int.MaxValue;//c号车厢进出前，bestTrack对应的栈顶元素。
            for (int i = 0; i < BufferRail.Length; i++)
            {
                if (BufferRail[i].IsEmpty())
                {
                    bestTrack = i;
                    break;
                }
                else
                {
                    int x = BufferRail[i].StackTop;
                    if (c < x && x < bestTop)
                    {
                        bestTop = x;
                        bestTrack = i;
                    }
                }
            }

            if (bestTrack == -1)//说明c号车厢无轨可进
            {
                return false;
            }
            else
            {
                BufferRail[bestTrack].Push(c);
                Console.WriteLine("移动车厢：{0}从入轨到缓冲轨{1}", c, bestTrack);
                if (c < minH)
                {
                    minH = c;
                    minS = bestTrack;
                }
                return true;
            }
        }
        static void Main(string[] args)
        {
            int[] p = { 3, 6, 9, 2, 4, 7, 1, 8, 5 };
            int k = 1;
            bool result = RailRoad(p, k);
            while (result == false)
            {
                Console.WriteLine("需要更多的缓冲轨，请输入增加的数量：");
                k = k + Convert.ToInt32(Console.ReadLine());
                result = RailRoad(p, k);
            }
        }
    }
移动车厢：3从入轨到缓冲轨0
需要更多的缓冲轨，请输入增加的数量：
2
移动车厢：3从入轨到缓冲轨0
移动车厢：6从入轨到缓冲轨1
移动车厢：9从入轨到缓冲轨2
移动车厢：2从入轨到缓冲轨0
移动车厢：4从入轨到缓冲轨1
移动车厢：7从入轨到缓冲轨2
移动车厢：1从入轨到出轨
移动车厢：2从缓冲轨0到出轨
移动车厢：3从缓冲轨0到出轨
移动车厢：4从缓冲轨1到出轨
移动车厢：8从入轨到缓冲轨0
移动车厢：5从入轨到出轨
移动车厢：6从缓冲轨1到出轨
移动车厢：7从缓冲轨2到出轨
移动车厢：8从缓冲轨0到出轨
移动车厢：9从缓冲轨2到出轨
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131