首页 > 代码库 > 【16】双栈排序
【16】双栈排序
【题目】
请编写一个程序,按升序对栈进行排序(即最大元素位于栈顶),要求最多只能使用一个额外的栈存放临时数据,但不得将元素复制到别的数据结构中。
给定一个int[] numbers(C++中为vector<int>),其中第一个元素为栈顶,请返回排序后的栈。请注意这是一个栈,意味着排序过程中你只能访问到第一个元素。
测试样例:
[1,2,3,4,5]
返回:[5,4,3,2,1]
【代码】
import java.util.*; public class TwoStacks { public ArrayList<Integer> twoStacksSort(int[] numbers) { ArrayList<Integer> list = new ArrayList<Integer>(); //构建栈,并初始化栈 Stack<Integer> initStack = new Stack<>(); for (int i = 0 ; i < numbers.length; i++){ initStack.push(numbers[i]); } //构建辅助栈,用来存放排好序的数 Stack<Integer> tempStack = new Stack<>(); while(!initStack.isEmpty()){ if (tempStack.isEmpty()){ tempStack.push(initStack.pop()); }else { //新建变量,存储原始栈中待排序的栈 int tmp = initStack.pop(); //将辅助栈中的排好序中的大于tmp的数放入原始栈中 while (!tempStack.isEmpty() && tempStack.peek() > tmp){ initStack.push(tempStack.pop()); } //辅助栈存储之前保存的变量 tempStack.push(tmp); } } while(!tempStack.isEmpty()){ list.add(tempStack.pop()); } return list; } }
解析:
【16】双栈排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。