[java]Stack 用临栈对栈排序
TwoStackSort cc150 请编写一个程序，按升序对栈进行排序（即最大元素位于栈顶），要求最多只能使用一...

26
2019/10

# [java]Stack 用临栈对栈排序

## TwoStackSort

cc150

[1,2,3,4,5]

[5,4,3,2,1]

### 代码

package _09_Linear.Stack_QueuePractice;

import java.util.ArrayList;
import java.util.Stack;

public class TwoStackSort {
public static void main(String[] args) {
int[] arr = {80, 2, 3, 14, 5, 19, 4, 70};
ArrayList<Integer> res = new TwoStackSort().twoStackSort(arr);
for (int a : res) {
System.out.println(a);
}
}

public ArrayList<Integer> twoStackSort(int[] number) {
// 初始化原始栈
Stack<Integer> source = new Stack<>();

for (int i = 0; i < number.length; i++) {
source.push(number[i]);
}
Stack<Integer> target = twoStackSort(source);

ArrayList<Integer> list = new ArrayList<>();

while (!target.empty()) {
list.add(target.pop());//从栈顶取出 从大大小 --> list
}
return list;

}

public Stack<Integer> twoStackSort(Stack<Integer> source) {
Stack<Integer> target = new Stack<>();
while (!source.empty()) {
int v1 = source.pop();//揭开 盖子
if (target.empty()) {
target.push(v1);
} else {//比较
if (v1 >= target.peek())//比盖子大 就 压进去 大的在栈顶
target.push(v1);
else {
while (!target.empty() && v1 < target.peek()) {//逆序 装回去
source.push(target.pop());
}
target.push(v1);
}
}
}
return target;
}
}


百度已收录

Last modification：October 26th, 2019 at 09:36 pm