问题描述 给定一个存有整形数的堆栈,你能使用的操作有,peek 获得堆栈顶部元素的值但不把元素弹出堆栈,pop 把堆栈顶部的元素出栈,push 压入一个堆栈,empty 判断堆栈是否为空,要求你只能使用这几种操作,同时在不分配新内存的情况下,将堆栈中的元素从大到小排列,假定堆栈中,元素由栈底到栈顶如下: stack: 1 3 5 4 2 排序后为: stack: 5 4 3 2 1
public class StackSorter { public Stack<Integer> sortByRecursion(Stack<Integer> s) { if (s.empty() == true) { return s; } int v = s.pop(); s = sortByRecursion(s); s = insert(s, v); return s; } private Stack<Integer> insert(Stack<Integer> s, int v) { if (s.empty() == true || v <= s.peek()) { s.push(v); return s; } int t = s.pop(); insert(s, v); s.push(t); return s; } }思路 写递归程序重要的四点是:输入参数、输出结果、函数的功能、终止条件。**递归本身就是完成一种功能的形式化描述。**递归的思维方式是将复杂的问题简单化。 第一个函数sortByRecursion(Stack<Integer> s)对栈中的元素进行排序,但是根据题目要求,不能分配新的内存,采用递归,将所有元素出栈,保存在调用堆栈上,当栈空时,这时栈里面的元素已经排好序了(没有任何元素),向栈中插入元素。 不要去解析程序执行的每一个步骤来理解递归,递归并不是算法,是一种思想。 第二个函数insert(Stack<Integer> s, int v)在排好序的栈中插入元素,也是采用递归,当栈空时或当插入元素小于等于栈顶元素的值时,将元素压入栈中,否则将栈顶元素弹出,将元素插入,在将刚才的元素压栈。 总结 递归程序没有想的那么难,只是我们总要从每一步去理解递归,我一开始也是如此,这让我很没有头绪。递归是一种思想,请好好理解这些话。