编写程序以按升序对堆栈进行排序

有人可以帮忙查看我的代码吗？ 非常感谢你的帮助。 输入堆栈是[5,2,1,9,0,10]，我的代码给出了输出堆栈[0,9,1,2,5,10]，9不在正确的位置。

import java.util.*; public class CC3_6 { public static void main(String[] args) { int[] data = {5, 2, 1, 9, 0, 10}; Stack myStack = new Stack(); for (int i = 0; i < data.length; i++){ myStack.push(data[i]); } System.out.println(sortStack(myStack)); } public static Stack sortStack(Stack origin) { if (origin == null) return null; if (origin.size() < 2) return origin; Stack result = new Stack(); 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; } 

}

Answer 1

  public static Stack sort(Stack s) { if (s.isEmpty()) { return s; } int pivot = s.pop(); // partition Stack left = new Stack(); Stack right = new Stack(); while(!s.isEmpty()) { int y = s.pop(); if (y < pivot) { left.push(y); } else { right.push(y); } } sort(left); sort(right); // merge Stack tmp = new Stack(); while(!right.isEmpty()) { tmp.push(right.pop()); } tmp.push(pivot); while(!left.isEmpty()) { tmp.push(left.pop()); } while(!tmp.isEmpty()) { s.push(tmp.pop()); } return s; } 

Answer 2

 /** the basic idea is we go on popping one one element from the original * stack (s) and we compare it with the new stack (temp) if the popped * element from original stack is < the peek element from new stack temp * than we push the new stack element to original stack and recursively keep * calling till temp is not empty and than push the element at the right * place. else we push the element to the new stack temp if original element * popped is > than new temp stack. Entire logic is recursive. */ public void sortstk( Stack s ) { Stack temp = new Stack(); while( !s.isEmpty() ) { int s1 = (int) s.pop(); while( !temp.isEmpty() && (temp.peek() > s1) ) { s.push( temp.pop() ); } temp.push( s1 ); } // Print the entire sorted stack from temp stack for( int i = 0; i < temp.size(); i++ ) { System.out.println( temp.elementAt( i ) ); } } 

Answer 3

 public class ReverseStack { public static void main(String[] args) { Stack stack =new Stack(); stack.add(3);stack.add(0);stack.add(2);stack.add(1); sortStack(stack); System.out.println(stack.toString()); } public static void sortStack(Stack stack){ int tempElement=stack.pop(); if(!stack.isEmpty()){ sortStack(stack); } insertStack(stack,tempElement); } private static void insertStack(Stack stack, int element) { if(stack.isEmpty()){ stack.push(element); return; } int temp=stack.pop(); //********* For sorting in ascending order******** if(element 

Answer 4

这是我的代码版本，非常简单易懂。

 import java.util.Stack; public class StackSorting { public static void main(String[] args) { Stack stack = new Stack(); stack.push(12); stack.push(100); stack.push(13); stack.push(50); stack.push(4); System.out.println("Elements on stack before sorting: "+ stack.toString()); stack = sort(stack); System.out.println("Elements on stack after sorting: "+ stack.toString()); } private static Stack sort(Stack stack) { if (stack.isEmpty()) { return null; } Stack sortedStack = new Stack(); int element = 0; while(!stack.isEmpty()) { if (stack.peek() <= (element = stack.pop())) { if (sortedStack.isEmpty()) { sortedStack.push(element); } else { while((!sortedStack.isEmpty()) && sortedStack.peek() > element) { stack.push(sortedStack.pop()); } sortedStack.push(element); } } } return sortedStack; } } 

Answer 5

 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 stack1, Stack 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 stack1, Stack 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 TwoStackSorter(Stack stack1, Stack stack2){ StackSort(stack1, stack2, stack1.size()+stack2.size()); return (stack1.empty())? stack2:stack1; } public static void main(String[] args) { Stack 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 emptyStack = new Stack<>(); Stack res = TwoStackSorter(stack, emptyStack); System.out.println("The sorted stack is: "); System.out.print(res); } } 

这是我在一个小时的头脑风暴后昨天晚上提出的代码。 当我解决这个问题的一个版本时，我有一个限制，最多只能使用一个额外的堆栈。 这是对这个问题的强烈递归解决方案。 我使用了2个私有方法来获取我从堆栈中所需的东西。 我非常喜欢递归在这里工作的方式。 基本上我正在解决的版本需要通过使用最多一个额外的堆栈以升序/降序对堆栈进行排序。 请注意，不应使用其他数据结构。