[求高手们来看看]四个栈排序
问题是这样的,要求用户输入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.
谢谢！
回答：
答案做出来了，大概是这样的。
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);
}
}
以上是 [求高手们来看看]四个栈排序 的全部内容， 来源链接： utcz.com/p/173929.html
