编写程序以按升序对堆栈进行排序 [英] Write a program to sort a stack in ascending order
问题描述
有人可以帮助查看我的代码吗?非常感谢你的帮助。
输入堆栈是[5,2,1,9,0,10],我的代码给出了输出堆栈[0,9,1,2,5,10],9不在正确的位置。
Can someone help look at my code, please? Thank you so much for your help. The input stack is [5, 2, 1, 9, 0, 10], my codes gave output stack [0, 9, 1, 2, 5, 10], 9 is not in the right position.
import java.util.*;
public class CC3_6 {
public static void main(String[] args) {
int[] data = {5, 2, 1, 9, 0, 10};
Stack<Integer> myStack = new Stack<Integer>();
for (int i = 0; i < data.length; i++){
myStack.push(data[i]);
}
System.out.println(sortStack(myStack));
}
public static Stack<Integer> sortStack(Stack<Integer> origin) {
if (origin == null)
return null;
if (origin.size() < 2)
return origin;
Stack<Integer> result = new Stack<Integer>();
while (!origin.isEmpty()) {
int smallest = origin.pop();
int remainder = origin.size();
for (int i = 0; i < remainder; i++) {
int element = origin.pop();
if (element < smallest) {
origin.push(smallest);
smallest = element;
} else {
origin.push(element);
}
}
result.push(smallest);
}
return result;
}
}
推荐答案
package TwoStackSort;
import java.util.Random;
import java.util.Stack;
public class TwoStackSort {
/**
*
* @param stack1 The stack in which the maximum number is to be found.
* @param stack2 An auxiliary stack to help.
* @return The maximum integer in that stack.
*/
private static Integer MaxInStack(Stack<Integer> stack1, Stack<Integer> stack2){
if(!stack1.empty()) {
int n = stack1.size();
int a = stack1.pop();
for (int i = 0; i < n-1; i++) {
if(a <= stack1.peek()){
stack2.push(a);
a = stack1.pop();
}
else {
stack2.push(stack1.pop());
}
}
return a;
}
return -1;
}
/**
*
* @param stack1 The original stack.
* @param stack2 The auxiliary stack.
* @param n An auxiliary parameter to keep a record of the levels of recursion.
*/
private static void StackSort(Stack<Integer> stack1, Stack<Integer> stack2, int n){
if(n==0){
return;
}
else{
int maxinS1 = MaxInStack(stack1, stack2);
StackSort(stack2, stack1, n-1);
if(n%2==0){
stack2.push(maxinS1);
}
else{stack1.push(maxinS1);}
}
}
/**
*
* @param stack1 The original stack that needs to be sorted.
* @param stack2 The auxiliary stack.
* @return The descendingly sorted stack.
*/
public static Stack<Integer> TwoStackSorter(Stack<Integer> stack1, Stack<Integer> stack2){
StackSort(stack1, stack2, stack1.size()+stack2.size());
return (stack1.empty())? stack2:stack1;
}
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
Random random = new Random();
for (int i = 0; i < 50; i++) {
stack.push(random.nextInt(51));
}
System.out.println("The original stack is: ");
System.out.print(stack);
System.out.println("\n" + "\n");
Stack<Integer> emptyStack = new Stack<>();
Stack<Integer> res = TwoStackSorter(stack, emptyStack);
System.out.println("The sorted stack is: ");
System.out.print(res);
}
}
这是我昨天晚上提出的代码经过一个小时的头脑风暴。当我解决这个问题的一个版本时,我有一个限制,最多只能使用一个额外的堆栈。这是对这个问题的强烈递归解决方案。我使用了2个私有方法来获取我从堆栈中需要的东西。我非常喜欢递归在这里工作的方式。基本上我正在解决的版本需要通过使用最多一个额外的堆栈以升序/降序对堆栈进行排序。请注意,不应使用其他数据结构。
This is a code that I came up with yesterday night after an hour of brainstorming. When I was solving a version of this problem, I had a restriction that at most only one additional stack can be used. This is an intense recursive solution to this problem. I've used 2 private methods to get me the stuff that I required from the stack. I really love the way that recursion worked here. Basically the version that I was solving required to sort a stack in ascending/descending order by using at most one additional stack. Note that no other data structures should be used.
这篇关于编写程序以按升序对堆栈进行排序的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!