javascript - 使用javascript对堆栈元素进行排序

Question

我试图理解使用递归对堆栈元素进行排序 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

Answer 1

使用 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);