我试图理解使用递归对堆栈元素进行排序http://www.geeksforgeeks.org/sort-a-stack-using-recursion/ http://www.geeksforgeeks.org/sort-a-stack-using-recursion/不允许使用任何循环结构,如 while、for...等。我们只能在Stack S上使用以下ADT函数:
is_empty(S) :测试堆栈是否为空。
push(S) :将新元素添加到堆栈中。
pop(S) :从堆栈中删除顶部元素。
top(S) :返回顶部元素的值。请注意,这
函数不会从堆栈中删除元素。
我尝试了下面但出现错误
var stack = [-3, 14, 18, -5, 30];
function sortStack() {
if (stack.length > 0) {
temp = stack.pop();
sortStack();
sortedInsert(temp, stack);
}
}
function sortedInsert(element, stack) {
if (stack.length > 0 || element > stack[stack.length - 1]) {
stack.push(element);
} else {
temp = stack.pop();
sortedInsert(element, stack);
stack.push(temp);
}
}
sortStack();
console.log(stack);
RangeError: Maximum call stack size exceeded
at sortedInsert:12:22
at sortedInsert:21:5
at sortedInsert:21:5
at sortedInsert:21:5
at sortedInsert:21:5
at sortedInsert:21:5
使用 javascript,局部(作用域)变量需要声明为 var,否则它们是静态的。如果 sortStack() 中 t 之前没有 var,t 将是一个静态变量,并且每次弹出都会被覆盖,从而在 sortStack() 的所有返回上留下 t == -3。 SortedInsert() 中的 x 也会出现同样的问题。
var stack = [-3, 14, 18, -5, 30];
function sortStack(s) {
if (s.length > 0) {
var t = s.pop();
sortStack(s);
sortedInsert(s, t);
}
}
function sortedInsert(s, e) {
if (s.length == 0 || e > s[s.length - 1]) {
s.push(e);
} else {
var x = s.pop();
sortedInsert(s, e);
s.push(x);
}
}
sortStack(stack);
console.log(stack);
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)