题目描述
请编写一个程序，按升序对栈进行排序（即最大元素位于栈顶），要求最多只能使用一个额外的栈存放临时数据，但不得将元素复制到别的数据结构中。
给定一个int[] numbers(C++中为vector<int>)，其中第一个元素为栈顶，请返回排序后的栈。请注意这是一个栈，意味着排序过程中你只能访问到第一个元素。
<pre name="code" class="java">package com.mianshi;
import java.util.ArrayList;
import java.util.Stack;
public class jingdian_16 {
public static void main(String[] args) {
int[] numbers =new int[]{2,1,5,3,4};
ArrayList<Integer> list =jingdian_16.twoStacksSort(numbers);
for(int i=0;i<list.size();i++){
System.out.print(list.get(i)+" ");
}
}
public static ArrayList<Integer> twoStacksSort(int[] numbers) {
//栈1存储数据
Stack<Integer> stack1 =new Stack<Integer>();
//栈2临时存储
Stack<Integer> stack2 =new Stack<Integer>();
ArrayList<Integer> list =new ArrayList<Integer>();
for(int i=0;i<numbers.length;i++){
stack1.push(numbers[i]);
}
//isEmpty()判断是否为空，是空返回true，不是返回false
while(!stack1.isEmpty()){
//stack1中最上边的元素出栈
int a =stack1.pop();
//判断stack2中是否已经有数据，并且如果里面顶上的数据大于stack1中刚弹出的a，则需要换位置
//stack2.peek()表示得到栈顶的值但不需要弹出
while(!stack2.isEmpty() && stack2.peek()>a){
//如果成立则有,将stack2中的栈顶数据弹出放到stack1
stack1.push(stack2.pop());
//继续循环判断是否还有符合条件的
}
//循环之后就需要将stack1弹出的数据放到stack2中
stack2.push(a);
}
//遍历输出
while(!stack2.isEmpty()){
list.add(stack2.pop());
}
return list;
}
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
