题目
有一个待排序的栈,现在想将该栈从顶到底按照从大到小的顺序排序,只允许申请一个栈。除此之外,可以申请新的变量,但不能申请新的数据结构。
实现
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
|
public static <T extends Comparable<T>> void sort(Stack<T> stack) { Stack<T> helpStack = new Stack<>(); while (!stack.isEmpty()) { T currentElement = stack.pop(); while (!helpStack.isEmpty() && currentElement.compareTo(helpStack.peek()) > 0) { stack.push(helpStack.pop()); } helpStack.push(currentElement); }
while (!helpStack.isEmpty()) { stack.push(helpStack.pop()); } }
|