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

本文介绍了编写程序以按升序对堆栈进行排序的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

有人可以帮助查看我的代码吗？非常感谢你的帮助。 输入堆栈是[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.