Write a program to sort a stack in ascending order. You should not make any assumptions about how the stack is implemented. The following are the only functions that should be used to write this program: push | pop | peek | isEmpty.
import java.util.Stack; public class stackText { public static void main(String[] args){ Stack stack1 = new Stack(); Stack stack2 = new Stack(); stack1.push("1"); stack1.push("2"); stack1.push("3"); while(!stack1.empty()){ stack2.push(stack1.pop()); } while(!stack2.empty()){ System.out.print(stack2.pop()); } Stack<Integer> stack = new Stack<Integer>(); stack.push(1); stack.push(3); stack.push(4); stack.push(2); System.out.print( sort(stack)); } public static Stack<Integer> sort(Stack<Integer> s){ Stack<Integer> r = new Stack<Integer>(); while(!s.empty()){ int tmp = s.pop(); while(!r.empty() && r.peek() > tmp ){ s.push(r.pop()); } r.push(tmp); } return r; }
public static Stack<Integer> sort2(Stack<Integer> s){ Stack<Integer> r = new Stack<Integer>(); while(!s.empty()){ int tmp = s.pop(); while(!r.empty() && r.peek() < tmp ){ s.push(r.pop()); } r.push(tmp); } return r; }//descending order }
mistake: r.peek() > tmp 在比较的时候发现只有 Stack<Integer> 能比较，要不及时 int tmp = （int）s.pop() ; 也不可以
learned: two stack O(n^2), tmp is extra space