0%

用一个栈实现另一个栈的排序

题目

有一个待排序的栈,现在想将该栈从顶到底按照从大到小的顺序排序,只允许申请一个栈。除此之外,可以申请新的变量,但不能申请新的数据结构。

实现

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

/**
* 使用一个帮助栈对传入的栈进行拍戏
*
* @param stack 待排序的 stack
* @param <T> 泛型
*/
/**
* 使用一个帮助栈对传入的栈进行拍戏
*
* @param stack 待排序的 stack
* @param <T> 泛型
*/
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());
}
}