[求高手们来看看]四个栈排序

Question

问题是这样的,要求用户输入1到n个数.这个数列必须是连续的,也就是1,2,3,4....n这样的，现在有四个栈，三个栈作为辅助栈，有一个栈看作是输出栈。目标是要把输入的数列排序好，进入输出栈中，最终令到输出栈一个个pop出来是9 8 7 6 5 4 3 2 1 这样子的。此外，我用了一个ArrayList来用来存储用户输入的数。

1）入辅助栈的数字要比这个辅助栈的栈顶的数字要小，而且是最适合的，这个适合的意思是栈顶的数字跟输入的数字的距离是最少的。
2）如果输入的数字比辅助栈和其他的数字中的全部数字都要小,就要可以直接出输出栈,例如是如果输入数组中的数是1,可以直接去输出栈中。假如输出栈的栈顶的数是1的话，如果在辅助栈的栈顶或者在输入数组中找到2的话，2是可以直接到输出栈中的。
3）如果栈是空的话，数字可以直接进入。
4）如果没有任何适合的辅助栈，这表示没有任何办法来排序。

以下是例子：用户输入 3 6 9 2 4 7 1 8 5 （此处按0是退出输入）
step1:因为各个栈是空的，而3的前面有1和2，所以3放到H1（辅助栈）中
Step2:6也是放到辅助栈中，因为6比H1栈顶中的3要大，所以不能放到H1中，所以放到H2（辅助栈中）
Step3:同理9比H1中的3要大，要比H2中的6要大，所以放到H3中
Step4:2可以push去H1 H2 H3，不过push去H1是最合适的，因为H1栈顶的数减以2是最小的（距离最小）。故此应该push入H1当中
Step5:4应该push去H2当中，因为4比H1中的2要大，比H2中的6要小而且H2栈顶的数减以4（距离最小），故此应该push入H2当中。
如下是理解图

因为没有足够的辅助栈去排序，有些数列是不能够排序的，例如3 2 1 9 8 7 6 5 4.

谢谢！

Answer 1

答案做出来了，大概是这样的。
https://www.cise.ufl.edu/~sahni/dsaaj/en...
这里是完整的题目和答案

import java.util.Stack;

public class RailroadWithStacks
{
   // data members
   private static Stack [] track; // array of holding tracks
   private static int numberOfCars;
   private static int numberOfTracks;
   private static int smallestCar; // smallest car in any holding track
   private static int itsTrack;    // holding track with car smallestCar

   /** output the smallest car from the holding tracks */
   private static void outputFromHoldingTrack()
   {
      // remove smallestCar from itsTrack
      track[itsTrack].pop();
      System.out.println("Move car " + smallestCar + " from holding "+ "track " + itsTrack + " to output track");
   
      // find new smallestCar and itsTrack by checking top of all stacks
      smallestCar = numberOfCars + 2;
      for (int i = 1; i <= numberOfTracks; i++)
         if (!track[i].empty() &&
             ((Integer) track[i].peek()).intValue() < smallestCar)
         {
            smallestCar = ((Integer) track[i].peek()).intValue();
            itsTrack = i;
         }
   }
   
  /** put car c into a holding track @return false iff there is no feasible holding track for this car */
  private static boolean putInHoldingTrack(int c)
   {
      // find best holding track for car c
      // initialize
      int bestTrack = 0,               // best track so far
          bestTop = numberOfCars + 1;  // top car in bestTrack
   
      // scan tracks
      for (int i = 1; i <= numberOfTracks; i++)
         if (!track[i].empty())
         {// track i not empty
             int topCar = ((Integer) track[i].peek()).intValue();
             if (c < topCar && topCar < bestTop)
             {
                // track i has smaller car at top
                bestTop = topCar;
                bestTrack = i;
             }
         }
         else // track i empty
            if (bestTrack == 0) bestTrack = i;
         
      if (bestTrack == 0) return false; // no feasible track
   
      // add c to bestTrack
      track[bestTrack].push(new Integer(c));
      System.out.println("Move car " + c + " from input track "+ "to holding track " + bestTrack);
   
      // update smallestCar and itsTrack if needed
      if (c < smallestCar)
      {
          smallestCar = c;
          itsTrack = bestTrack;
      }
   
      return true;
   }
   
  /** rearrange railroad cars beginning with the initial order inputOrder[1:theNumberOfCars] @return true if successful, false if impossible. */
   public static boolean railroad(int [] inputOrder,
                         int theNumberOfCars, int theNumberOfTracks)
   {
      numberOfCars = theNumberOfCars;
      numberOfTracks = theNumberOfTracks;

      // create stacks track[1:numberOfTracks] for use as holding tracks
      track = new Stack [numberOfTracks + 1];
      for (int i = 1; i <= numberOfTracks; i++)
         track[i] = new Stack();
   
      int nextCarToOutput = 1;
      smallestCar = numberOfCars + 1;  // no car in holding tracks
   
      // rearrange cars
      for (int i = 1; i <= numberOfCars; i++)
         if (inputOrder[i] == nextCarToOutput)
         {// send car inputOrder[i] straight out
             System.out.println("Move car " + inputOrder[i] + " from input track to output track");
             nextCarToOutput++;
    
             // output from holding tracks
             while (smallestCar == nextCarToOutput)
             {
                outputFromHoldingTrack();
                nextCarToOutput++;
             }
         }
         else
         // put car inputOrder[i] in a holding track
            if (!putInHoldingTrack(inputOrder[i]))
               return false;

      return true;
   }
   
   /** test program */
   public static void main(String [] args)
   {
       int [] p = {0, 5, 8, 1, 7, 4, 2, 9, 6, 3};
      //int [] p = {0, 3, 6, 9, 2, 4, 7, 1, 8, 5};
      System.out.println("Input permutation is 369247185");
      railroad(p, 9, 3);
   }
}