TwoStackSort
cc150
请编写一个程序,按升序对栈进行排序(即最大元素位于栈顶
),要求最多只能使用一个额外的栈存放临时数据,但不得将元素复制到别的数据结构中。
给定一个int[] numbers(C++中为vector<int>),其中第一个元素为栈顶,请返回排序后的栈。请注意这是一个栈,意味着排序过程中你只能访问到第一个元素。
测试样例:
[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;
}
}
本文作者:Author: 寒光博客
文章标题:[java]Stack 用临栈对栈排序
本文地址:https://dxoca.cn/java/308.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
本文地址:https://dxoca.cn/java/308.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。